8 - Checkers on a Circle

Summary

Let n be any positive integer. Place n red and black checkers, in any order, along the circumference of a circle. We define a transformation which maps the n-tuple of red and black checkers into a new n-tuple of red and black checkers: If two adjacent checkers are of the same color, place a red checker between them; if they are of different colors, place a black checker between them. Then remove all the original checkers.

We are interested in what happens when this process is repeated. The answer depends on n in a surprising way.

Problem 8.1. Show that if n = 2^m then after a finite number of transformations all checkers on the circle become red.

This is a reformulation, in nontechnical language, of a problem which has occurred in many competitions and has been discussed in several books and papers.

Vectors and Operators

Before we tackle the problem and its extensions, we shall spend some time presenting algebraic concepts which have many applications. The above transformation can be described algebraically as follows: Assign to each red checker the number 0, and to each black checker the number 1. Denote the initial distribution of checkers by x = (x₁, x₂, …, x_n), where x_i = 0 or 1 for a red or a black checker, respectively. We regard a 1-index array of n 0's and 1's as a vector and denote it by a bold face lower case letter.