Solitaire on a Circle

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.

The applet allows you to take a move back (Back button) and to return to the same starting arrangement (Repeat button.)


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Solitaire on a Circle


What if applet does not run?

Explanation

|Contact| |Front page| |Contents| |Eye opener| |Games| |Store|

Copyright © 1996-2017 Alexander Bogomolny

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

  1. A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008, p. 160-161

Related material
Read more...

  • Chessboard
  • Changing Colors, an Interactive Activity
  • Plus or Minus Game
  • Squares, Circles, and Triangles
  • Calendar Magic
  • Counting Diagonals in a Convex Polygon
  • The Game of Fif
  • Nim
  • |Contact| |Front page| |Contents| |Games| |Eye opener| |Up| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62351248

    Search by google: