A Solitaire game below is played with a number of counters arranged in a circular pattern. One of the faces of each counter is red, the other is green. A move consists in clicking on a green counter. When you do, the counter is removed. At the same time, its neighbors (if any but at most 2 of course) are flipped over. The goal is to remove all the counters. Beware though that the puzzle is not always solvable. There is a simple condition to check in advance whether it is.
Explanation
Two solutions to this puzzle appear in The American Mathematical Monthly, November, 1997 (104, no 9, p 876.) I'll consider the simpler of the two.
The puzzle is not always solvable. It's solvable iff the initial pattern has a nonzero even number of green counters. Note that the first move (including the flips) changes the parity of the number of green counters. Hence it suffices to prove that contiguous counters with a gap at each end can all be removed if and only if the line has an odd number of green counters or is empty.
The statement is trivial for the empty line; we proceed by induction on n. Suppose first that the number of green counters is odd. We may choose a green counter D having an even number (possibly zero) of green counters to each side. Removing D creates two (possibly empty) shorter lines of counters. If either side is nonempty, completing the move by flipping the neighbor of D creates a line on that side with an odd number of green counters. By the induction hypothesis, the remaining counters on both sides can be removed.
Now suppose that the nonempty line has an even number of green counters. If it has no green counters, then nothing can be removed. Otherwise, each green counter D has an odd number of green counters to one of its sides. Removing D and flipping its neighbor on that side creates a smaller line with an even number of green counters which, by the induction hypothesis, cannot be removed. Thus there is no first counter to remove that permits success.
References
- A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008, p. 160-161
