Reverse & Clean
April 17th, 2010The game of Reverse & Clean is a one player game, played on an N by M board, filled with Reversi pieces. Each Reversi piece has a black side and a white side. The game starts with all pieces showing their white side, except for the piece in the lower right corner, which shows its black side. See the figure for a 3 by 3 example.
In each turn of the game, you remove one of the black pieces and flip all of its (remaining) neighbours (the pieces up, down, left and right of it). The figures below demonstrate 2 possible first moves (note that the very first move of the game is always to remove the bottom right piece, which is the only black piece).
The goal of the game is to clean the board (i.e. remove all pieces). Note that if the board is 1 by N, you can always win, while if the board is 2 by 2, winning is impossible (make sure you see why).
For what numbers, N and M, is a win possible?
Extra Credit: What about 3-dimensions? D-dimensions?
Thanks to Liron Raz for giving me this one.
April 18th, 2010 at 11:13 pm
Solution: if not both N and M are even, it is possible
Proof:
Part 1:
If for example N is odd, the following algorithm should work:
for row = 1:
for col = 1 to N:
take peice
# now we’ve cleaned the first row, and the second row is all black
for row = 2 to M:
for every odd col between 1 to N (including both):
take peice
# all even cols are still black
for every even col between 2 to N – 1:
take peice
Part 2:
Let S be the strategy (IE – order of squares)
We denote f(S) as: the total number of flips during the process.
On the one hand, every peice we move, was black, therefore all the peices were flipped an odd number of times, except for the first peice. there is an odd number of peices besides the first one, therefore f(S) is odd.
On the other hand, if we look at the neighbours-graph G=(V,E) (V = all places, E = are those two places neighbours), we can notice that for every edge, one of its sides was moved first, and by that, causing the other side to flip. Therefore f(S) = |E|.
however, |E| = M*(N-1) + N*(M-1) = 0 (mod 2)
Contradiction.
April 19th, 2010 at 1:55 pm
I have a somewhat different solution for part 2, but I think Nadav’s is nicer.
First surround the board with another 2(M+N) pieces, so that every pebble from the original MxN board has exactly 4 neighbors (just for simplification of the computations). Paint the table like a chess board, with light and dark places. Note that whenever a piece other than the first is removed, the parity of the number of black pieces on both colours changes: Say that we remove a piece on a light square. Obviously the number of black pebbles on light squares simply decreases by one, and the parity changes. Because the piece was black, it had an odd number of neighbors still on the board, each on a dark square, so an odd number of pieces on dark squares will change their colour, and the number of black pebbles on dark squares will change its parity. After the first move, there is an even number of black pebbles on both light and dark squares (0 and 4). In the end, when the board is clear, all of the fictional border will be black, so there will be M+N black pieces on both light and dark (actually, if both M and N are odd, there will be M+N+2 on dark squares and M+N-2 on light squares, but the parity is the same). On the other hand MN-1 moves were made after the first, so
MN – 1 = M +N (mod 2) => MN + M + N +1 = 0 (mod 2) => (M+1)(N+1) = 0 (mod 2), thus either M or N must be odd.
Both solutions reach the conclusion that MN-1 = M+N (mod 2), but this is really just equivalent to the necessary and sufficient condition for the game to be winnable, so I don’t really know if there’s a deep connection between the two. It seems to me that the objects counted are profoundly different.
April 20th, 2010 at 10:22 pm
Great riddle, great proofs!