mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   January 2021 (https://www.mersenneforum.org/showthread.php?t=26358)

Kebbaj 2021-02-05 01:45

[QUOTE=dg211;569731]Has anyone made any progress on the second bonus question?

My initial attempts have been largely computational, without really doing any clever analysis of the problem. I found a heuristic which has worked pretty well so far for finding 2-bot placements while searching a very small section of the problem space. That is giving me values of N up to several hundred with 2-bot solutions (assuming my code is correct - I've submitted a solution but it hasn't been verified yet). But if there is a value of N for which 2 bots won't work, I don't see any purely computation-based way to verify it other than exhaustively testing every possible pair of placements, which would take days for N that large with my current code (which I think is reasonably optimized).

That all leads me to the conclusion that there must be some clever way to analyse the problem mathematically rather than just brute forcing it with compute, but I don't really see any way to get to grips with the problem that way. Has anyone had any luck with a more analytical approach?[/QUOTE]

I had seen something like that solution: there will always a solution with 2 rebots. A point that is repeated by a modulo, by visualizing the abandoning solutions that you are kind enough to publish. I am not pushing the question any further. I was waiting for a continuation of the question or a definitive answer when the solution will guiven. We had neither.
In French we says "Domage"! I dont know how to say it in English.

SmartMersenne 2021-02-05 01:59

[QUOTE=Kebbaj;570893]I had seen something like that solution: there will always a solution with 2 rebots. A point that is repeated by a modulo, by visualizing the abandoning solutions that you are kind enough to publish. I am not pushing the question any further. I was waiting for a continuation of the question or a definitive answer when the solution will guiven. We had neither.
In French we says "Domage"! I dont know how to say it in English.[/QUOTE]

What a pity!

Shame!

What the ...?!

Kebbaj 2021-02-05 08:53

[QUOTE=SmartMersenne;570894]What a pity!

Shame!

What the ...?![/QUOTE]
In any case.
For "**". I think the question was phrased well, but it is the solution that was not. Per what if me or many of us had answered "there is always a solution with 2 antibiot" without any prouven. Believe you that would be accepted. I would not accept it for me.
Opned question like many others.

Zoozie 2021-02-09 21:29

[QUOTE=dg211;570266]In case it's any help to anyone trying to tackle the second bonus question, I've shared what I think are 2-bot solutions for N up to 762 (excluding N = 50 and N = 100 to avoid spoiling the other parts of the puzzle).

[url]https://drive.google.com/file/d/1oU1Hwj7Yb4lxHNJt4n_Lls474hSbqe45/view?usp=sharing[/url]

Maybe someone can spot a pattern which will lead to a more elegant way to approach the problem.

Note that these aren't a complete set of all possible 2-bot solutions, as my search would stop trying new placements for the first bot after it had found at least one solution (but it doesn't stop until after it has tried every possible second bot placement, so some values of N have multiple solutions, all with the same first bot placement).[/QUOTE]

Besides looking for solutions with 2 bots in first column, did you use other tricks?
Seems only like 80% of the solutions has 2 bots in first column and finding a solution then takes much longer.

Here are some high solutions with 2 bots in first column:

1000: [(556,0),(569, 0)]
1500: [(484, 0),(852, 0)]
2000: [(892, 0), (1014, 0)]]

The simulation for the 2000*2000 takes almost 3.6M moves to complete.


All times are UTC. The time now is 06:09.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.