We have two players. Each player has a marker in one of the colored regions in the picture above. The second player chooses the initial positions of the markers. The players take turns, the first player going first. During each player's turn, the player may either move his marker into an adjacent region or choose to do nothing. If the first player ever moves his marker into the same region as the second player's marker, then the first player wins. If the first player doesn't win after twenty of his turns, the second player wins.Which of the two players can always win? I do not require a proof, but you get extra points for showing reasoning.
Now, if I may digress a bit, have you ever heard of the four color theorem? The four color theorem states that if I have any group of regions like in the picture above, and I want to color each region such that no two adjacent regions are the same color, then I only need four different colors. Interesting, huh? I am told that the proof is highly nontrivial.
ETA: my thoughts on the solution here
10 comments:
Seems trivial that the second player could always avoid the first player, but perhaps I'm missing something. Are you sure you've stated it correctly? You're clearly hinting at something with the four-color theorem.
It's not trivial, though it's not too difficult either.
And no, the four-color theorem has nothing to do with anything. It wasn't even meant as a red herring, though I suppose it could function that way.
The second player always wins as they can remain at the same distance from the first player as they started out?
The proof of the four colour theorem is non-trivial, although it's quite easy to state. All possible maps on flat surfaces fall into 1 of just less than 2000 cases. All of those cases can be coloured using only 4 colours. It's one of the first theorems to be proved using a computer.
If the second player get chased into a dead-end, the first player will win. How do we know whether there are any "dead-ends" here?
I would suggest that player 1 would allways win since each ring has a piece that connects to 3 pieces on the outer ring and so the first player just has to chase the second player on the outskirts, but if he can do so within 20 moves I am not so sure.
I originally meant twenty to be a really large number, but I guess I'm cutting it very close.
Replacing 20 with 1000...
Call the middle "ring 0", the next "ring 1", the outer is "ring 4".
If player 2 is in ring N, player 1 wants to be in ring N-1, always moving to a place that is adjacent to player 2's position. Player 2 can race around and around in ring N, with player 1 chasing in ring N-1, only until it gets to the point where player 1 is in the N-1 region that is adjacent to 3 N regions. That forces player 2 to go to ring N+1.
To start, player 1 goes to ring 0, from there heading out to get adjacent to player 2. To finish, player 1 traps player 2 in ring 4, at the bottom.
New question: what's the maximum number of moves that player 2 can survive? I believe it would have player 1 on ring 4 to begin with, and player 2 playing in a way that player 1 has to chase player 2 all the way around every ring. I've not counted, but I place my bets on player 2 if player 1 only gets 20 moves.
It feels similar, in principle, to checkmating a king using a king and a rook. ;)
Ah, because player 1 gets to choose which direction to chase player 2 (clockwise or anti-clockwise), 2 only needs to be chased half-way around every ring. I believe I can keep 2 alive for 19 moves. (On 1's 19th move, 2 gets caught.) I suspect that's the best... can anyone do better?
Awesome. I couldn't have said it better myself.
Currently, though, I suspect that player 2 wins. Remember that player 2 can jump to the next ring prematurely.
Post a Comment