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$ 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$
    – DrunkWolf
    Dec 20 '15 at 12:06

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):

enter image description here

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.

  • $\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$
    – Lawrence
    Dec 20 '15 at 12:22

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.