A black and a white piece is in two adjacent corners of a 12-gon. In a move, we get to move any piece to any vacant neighboring corners. If both of the pieces returns to a position which they have been before, the game ends. How many moves can we at most do?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Does it stop when a single piece is in a position it has previously been in or when both are in a configuration that has happened before? $\endgroup$– DrunkWolfDec 20, 2015 at 12:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
Let the corners be ordered $1,2...,12$. Starting from (black,white) = $(1,2)$, we can move white (I'm assuming we don't need to move black at the same time)
$(1,2)\rightarrow (1,3)\rightarrow(1,4)\rightarrow...\rightarrow(1,12)$ (10 moves)
and then move the black piece one step in the other direction
$(2,12)\rightarrow(2,11)\rightarrow...\rightarrow(2,4)$ (8 moves)
since we cannot visit $(2,3)$. Next step is to $(3,4)$.
This is how the 12-gon may be traversed (I pretty sure this is optimal):
If I have counted correctly,
there are $9\times 12$ from the cycles with white moves and $11$ moves with the black, so in total $119$. If the last move is counted, then we may do $120$ moves.
answered Dec 20, 2015 at 12:18
-
$\begingroup$ Looks like you're almost there. You can only move to vacant spots, so (1,1) or in general, (x,x) is not a viable move. $\endgroup$– LawrenceDec 20, 2015 at 12:22
$\begingroup$
$\endgroup$
Carl's answer is optimal. Let's say that a position is "odd" if there are an odd number of empty vertices between the two pieces, and "even" otherwise.
The process must alternate between odd and even positions. Since there are only 60 odd positions and we start at an even position, the greatest number of states we path can traverse is 121, which means we can make at most 120 moves.
answered Dec 20, 2015 at 17:15