Color Switching Games

Gregory P. Tollisen^{∗} AND Tamás Lengyel^{∗} Mathematics Department, Occidental College 1600 Campus Road, Los Angeles, CA 90041

ABSTRACT. In this paper the authors study one- and two-dimensional color switching problems by applying methods ranging from linear algebra to parity arguments, invariants, and generating functions. The variety of techniques offers different advantages for addressing the existence and uniqueness of minimal solutions, their characterizations, and lower bounds on their lengths. Useful examples for reducing problems to easier ones and for choosing tools based on simplicity or generality are presented. A novel application of generating functions provides a unifying treatment of all aspects of the problems considered.

1 Introduction The motivation for this paper is to illustrate several approaches to solving color switching games. At its most general, a color switching game is a one-person game played on a set of locations (e.g., squares on a chessboard or the vertices of a graph) each colored black or white, which we call the “coloring pattern.” The player makes a move by changing the color of the location of her choice. However, each location is associated with a set of neighbors in a predetermined way. By changing the color of one location, the colors in the associated locations also are changed automatically. Given initial and final coloring patterns, the game is won if the player successfully “moves” from the one pattern to the other. We begin by focusing on the following two problems found in [9] (Exercises 3.4.25 and 3.4.26, p.117) in a slightly different form.

Problem 1. Consider a row of 2n squares colored alternately black and white. A legal move consists of choosing any set of contiguous squares (one or more squares with no gaps allowed), and inverting their colors. What is the minimum number of moves required to make the entire row of one color?

Problem 2. Answer the same question as above, except now we start with a 2m × 2n checkerboard and a legal move consists of choosing any subrectangle and inverting its colors.

Clearly, in Problem 1, n moves will work, for we can invert the 1st square,

     ∗e-mail: tollisen@oxy.edu and lengyel@oxy.edu.

then the 3rd square, etc. In Problem 2 we can switch all even numbered rows and then all odd numbered columns and thus solve the problem in m + n moves. Not only will we show that these are best possible but we will completely characterize all optimal solutions to Problem 2.

We also generalize these problems to linear and rectangular boards with arbitrary initial colorings and moves of both fixed and arbitrary sizes. In each case, the game is won by attaining one color, say white, throughout the entire board. We are interested in the following questions: Can we win the game? If so, what is the minimum size of a winning set of moves? Is a minimal winning set (a winning set of minimum length) unique? Whether or not a minimal winning set is unique, is there a simple description of a minimal winning set, or if not, is there a simple algorithm that will generate a minimal winning set?

The discussion revolves around various uses of linear algebraic tools, parity arguments, invariants, and generating functions in connection with modular arithmetic. We also illustrate their comparative advantages and inherent limitations. Generating function based techniques have been used for analyzing problems on checkerboard tilings [3], checker-jumping [1] and sumset of multisets [3], among others. Typically, generating functions are used to restate and solve a given problem entirely within an algebraic environment. In contrast, we use generating functions as an intermediate step in exchanging a given game for an equivalent board game whose solutions are almost transparent.

We need some terminology. The game board consists of labeled squares. We use natural labeling: in the linear case, the squares can be labeled from 1 to 2n, and for rectangular boards we label the squares row by row. We call an assignment of colors to the squares a coloring pattern. The block of contiguous squares (in the linear case) or the rectangular block of squares (in the 2-dimensional case) used for inverting colors, we call the switching pattern. We refer to a switching pattern by indicating the position on the board occupied by its leftmost or upper left corner square, respectively, and by its size when needed.

For the linear board consisting of 2n squares, we have the following four theorems. Theorem 1 Suppose the board is colored so that adjacent squares have alternate colors. If the possible moves are switching patterns of arbitrary length, then the game can be won and the minimum number of moves needed is n. Theorem 2 Suppose the board is colored as in Theorem 1, and the possible moves are switching patterns of fixed length r. Then the game can be won if and only if r|n, and the minimum number of moves needed is n. Theorem 3 Suppose the board is arbitrarily colored. If the possible moves are of arbitrary length, then the game can always be won and the minimum number of moves needed is equal to the number of blocks of adjacent black squares on the board. Theorem 4 Suppose the board is arbitrarily colored and the possible moves are switching patterns of fixed length r. Then the game can be won if and only if the parity conditions

∑_{i≡a modr}(c_{i} − c_{i−1}) ≡ 0 mod 2

are met for all 0 ≤ a < r. (Here c_{−1} = 0.) Equivalently, the game can be won if and only if the sums

S_{a} = ∑_{i≡a modr} c_{i}, 0 ≤ a < r,

all have the same parity.

Note: In Theorems 1 and 3, the obvious solutions are minimal solutions, but generally, there will be other minimal solutions as well. Theorem 1 is proved in Section 3, and Theorem 3 can be easily proved in the same fashion. Theorems 2 and 4 can be proved by a single variable version of the generating function arguments applied in Section 4. In both theorems, the minimum solution is unique and is obtained by the greedy algorithm.

The following theorems concern a game board of size 2m × 2n.

Theorem 5 Suppose the board is checkerboard colored and the moves are switching patterns of arbitrary sizes. Then the game can be won and the minimum number of moves needed is m + n. A minimal solution is obtained by switching the colors of the even numbered rows and odd numbered columns. All minimal solutions can be completely characterized by their common structure.

Theorem 6 Suppose the board is checkerboard colored and the moves are of fixed size s × t. Then the game can be won if and only if s|m and t|n, the minimum number of moves needed is \frac{2(s+t−1)}{st} · mn, and the solution is unique.

Theorem 7 Suppose the board is arbitrarily colored and the moves are arbitrarily sized. Then the game can always be won, there is generally no unique minimal solution, and the minimum number of moves needed is bounded above by mn + O( min(m\sqrt{n}, n\sqrt{m})) as m, n → ∞.

Theorem 8 Suppose the board is arbitrarily colored and the moves are of fixed size s × t. Then the game can be won if and only if the parity conditions (7) are met. The minimal solution is unique.

Note: We present two proofs of Theorem 5 in Sections 3 and 4.2. The characterization of the minimal solutions is given in Section 4.2. In Theorems 6 and 8, the greedy algorithm where one goes through the board row by row gives the minimal solution. In Section 4.1 we give the proof for Theorem 8 and a sketch for Theorem 6. We believe that there is no easy way to get a minimal solution in the case of Theorem 7, whose proof is given in Section 4.3.

We discuss the linear algebraic technique in Section 2. In Section 3, we explore parity arguments and generalized invariants to establish lower bounds on the minimum number of moves for alternating and checkerboard colorings. The most general approach is based on various uses of generating functions as explained in Section 4. In the last part of the paper we list further results.

2 Linear algebraic approach

The problems have a flavor similar to that of games like Merlin’s magic squares ([6]-[8]). They can be expressed in terms of 0-1 problems, and often they are analyzed and solved by linear algebraic techniques. In these games, it is common to have a simple association between the N squares of the board and the M potential moves. We define two N dimensional vectors, c_{1} for the starting and c_{2} for the target coloring. The main idea is that an arbitrarily colored board with N squares can be represented by an N-dimensional 0-1 vector where 1 stands for a black square while 0 for a white one. The potential moves can be described by matrix A of size N × M with 0-1 entries by setting a_{ij} = 1 if using the jth potential move switches the value at position i, and 0 otherwise.

Clearly, every move should be used only once or not at all, and the order of the moves is irrelevant. This is a common feature of additive games with objects that alternate states [8]. We can describe the series of moves by a set of 0-1 coordinates: 1 if the potential move is applied and 0 otherwise. The corresponding vector of actual moves will be denoted by x. Therefore, we can find the solution to any problem getting from coloring c_{1} to c_{2} by solving

c_{2} ≡ c_{1} + Ax mod 2.  (1)

Note that the same solution will take us from c_{2} to c_{1}. In many situations we have M = N. For instance, for Merlin’s game we get M = N = 9. In this case, the necessary and sufficient condition for solving the problem of getting from any c_{1} to any c_{2} by applying matrix A is that A be invertible mod 2.

For example, in Theorem 8, for the board of size 2m × 2n with fixed rectangular switching pattern of size s × t, we note that the problem can be reduced to a truncated version of the board consisting of the upper left hand portion of size N = (2m − (s − 1)) × (2n − (t − 1)). For the moment we only care about how the moves affect this portion of the board. By labeling the squares row by row and defining the jth potential move as the switching pattern positioned at the jth square, we get a lower triangular matrix with ones on the diagonal. This fact guarantees a unique solution on the truncated board which uniquely extends to the original. If it matches the original coloring then we have the solution. The truncated version forces conditions on the entire board captured by parity restrictions which we will derive in Section 4. Note that the number of ones in the solution vector x gives us the number of moves used.

Particular solutions to the games and sometimes even their uniqueness can be derived by this technique, e.g., in the cases of Theorems 6 and 8, although without much insight into the size of the minimal solution. One limitation to the linear algebraic restatement is that the 2-dimensional structure of the original problem is reduced to a linear one which does not reflect adjacency. Another concern is that while setting the problem in matrix form seems fairly easy when there is a unique move associated with every position, it becomes more complicated when M is larger than N.

We note that Lovász [5, Exercise 5.17] discusses color switching games in graphs with N vertices. In this case A can be set to be a symmetric 0-1 matrix of size N × N with all ones in its diagonal. It is proven that there is always a solution to equation (1) with c_{1} and c_{2} being the all zero and all one vectors, respectively (cf. [4] and [2]).

3 Parity arguments and invariants

If we are asking questions regarding existence or non-existence, parity and invariance may first come to mind. The conditions alluded to in the previous example with fixed size switching patterns are equivalent to a set of parity conditions. Later on we will see how the parity conditions fall out as a by-product of the generating function approach. For switching patterns of arbitrary sizes, parity arguments do not seem to help. Of course, for these problems existence is not an issue. Even more, a greedy approach provides a direct solution. The question is whether this is best possible in the sense that it requires the minimum number of moves. One might suspect that parity based invariants may not advance our efforts to answer this question. Fortunately, a slight generalization of the concept of invariance comes to the rescue.

We consider an invariant to be an aspect of a given problem–usually a numerical quantity–that does not change, even if many other properties do change (cf. [9]). On the other hand, a pseudo-invariant is a quantity which may or may not change at each step of a problem but when it does change, it does so in a limited way.

For Problem 1, by setting c_{i} = 1 if square i is black and 0 otherwise, we use the following pseudo-invariant. Let

g(c_{1}, c_{2}, ..., c_{N}) = ∑_{i=1}^{N−1} |c_{i} − c_{i+1}|  (2)

which changes only by -2, -1, 0, 1, or 2 for any legal move. In Problem 1 we have N = 2n and note that the initial value of g is 2n − 1. It shows that it takes at least n moves to reach 0.

We now show that Problem 2 reduces to Problem 1, and that the checkerboard coloring of a 2m × 2n board with the upper left hand corner colored black, and with arbitrary switching patterns needs at least m + n moves. The proof follows from Problem 1 once we find a “linearizable obstacle” that is long enough. This will also work for many “mutilated boards” derived from a checkerboard. A sufficient condition for this lower bound is that the remaining board has a particular subset of squares called a “NW-SE snake.” We call a sequence of contiguous squares a “NW-SE snake” if it starts and ends at the NW and SE corners respectively, and always goes from North to South and from West to East. If a board has a “NW-SE snake” then reduction to Problem 1 works. As a matter of fact, we have a structure with N = 2n + 2m − 1 squares. Notice that any rectangular color switching pattern will only change neighboring squares of the snake. Function g has the initial value 2n + 2m − 2 and the game ends with the value 0, so while it initially appears that we need n + m − 1 moves we actually need one more, for a black end requires a color switch that decreases g by at most 1. A similar argument can be used to obtain a lower bound on the minimum number of moves for an arbitrarily colored mutilated board by finding a NW-SE snake of maximum length which has a black square on at least one end.

4 Generating functions

In this section, our strategy is to use generating functions to translate our games into an algebraic description. We develop two equations (5) and (6) for arbitrary and fixed size switching patterns, respectively. For arbitrarily sized switching patterns, we reinterpret the result as another similar game through which we may gain some insight into the first game. All theorems of this paper can be proven by this technique.

A coloring pattern (or coloring) of a 2m×2n game board is a (0, 1) matrix C = [c_{ij}]_{{0≤i<2m \atop 0≤j<2n}} where c_{ij} = 1 if and only if the square at position (i, j) is colored black. Its generating function is

Φ_{C}(x, y) = ∑ c_{ij}x^{i}y^{j}.

(For convenience, we specify that c_{ij} = 0 outside of the game board, unless otherwise indicated.) For example, the checkerboard coloring with the upper left-hand square colored black has generating function

Φ_{C}(x, y) = ∑_{{i<2m,j<2n \atop i+j even}} x^{i}y^{j} = (1 + xy)(\frac{1 − x^{2m}}{1 − x^{2}} )(\frac{1 − y^{2n}}{1 − y^{2}} ). (3)

Solving a coloring C = [c_{ij}], i.e., finding a sequence of rectangular moves that takes us between C and the all white board is equivalent to finding values for the coefficients m_{klst} that solve the polynomial equation

∑ m_{klst}x^{k}y^{l}(\frac{1 − x^{s}}{1 − x} )(\frac{1 − y^{t}}{1 − y} ) ≡ ∑ c_{ij}x^{i}y^{j}  (4)

where the indices in the sum on the left are restricted to 0 ≤ k < 2m, 0 ≤ l < 2n, 0 < s ≤ 2m − k and 0 < t ≤ 2m − l. (This congruence and all others are understood to be modulus 2, unless otherwise indicated. As a consequence, we can freely change the sign of any additive terms.) Then m_{klst} = 1 if and only if the move of size s×t with upper left corner occupying position (k, l) on the game board is included in the winning sequence.

If we multiply both sides of equation (4) by (1 − x)(1 − y) and collect equal powers of x and y on the right, we get the equivalent equation

∑ m_{klst}x^{k}y^{l}(1 − x^{s})(1 − y^{t}) ≡ ∑_{{0≤i≤2m \atop 0≤j≤2n}} x^{i}y^{j}[c_{ij} − c_{i,j−1} − c_{i−1,j} + c_{i−1,j−1}],

(5)

which will lead to a new game discussed in Sections 4.2 and 4.3.

Moreover, Section 4.1 will employ the result that, if the size of the moves permitted in the original game is fixed, then m_{klst} = m_{kl} with 0 ≤ k ≤ 2m − s and 0 ≤ l ≤ 2n − t, and we can formally multiply both sides of (4) by the factor (\frac{1−x}{1−x^{s}} )(\frac{1−y}{1−y^{t}} ), expand the denominators into geometric series, and collect equal powers of x and y on the right to get

∑ m_{kl}x^{k}y^{l} ≡ ∑_{{k≥0 \atop l≥0}} x^{k}y^{l}[ ∑_{{i≤k,i≡kmods \atop j≤l,j≡lmodt}} (c_{ij} − c_{i,j−1} − c_{i−1,j} + c_{i−1,j−1})]. (6)

Equations (5) and (6) yield a surprisingly diverse array of consequences for the original game, several of which we will now explore in the next three subsections.

4.1 When the permissible moves are fixed in size Equation (6) applies when the moves permitted in our game are fixed in size. On the left side of (6) the indices range over 0 ≤ k ≤ 2m − s and 0 ≤ l ≤ 2n − t. Consequently, a solution exists if and only if the parity conditions

∑_{{i≤k,i≡kmods \atop j≤l,j≡lmodt}} (c_{ij} − c_{i,j−1} − c_{i−1,j} + c_{i−1,j−1}) ≡ 0  (7)

are met for all k and l with k > 2m − s or l > 2n − t. Furthermore, the solution must be unique, and is specified precisely by the coefficients of x^{k}y^{l} in the right hand sum of (6). Because c_{ij} = 0 outside of the game board, this seemingly infinite set of conditions can be narrowed to those where k ≤ 2m and l ≤ 2n, which are the parity conditions promised in Section 2.

When we apply the above to the checkerboard coloring (3), the parity conditions can be shown to imply that a solution exists if and only if s|m and t|n. Moreover, in Z_{2}, the right side of (6) simplifies to

∑_{ij} x^{2si}y^{2tj}[1 + x^{s}y^{t} + (1 + x^{s})( ∑_{1≤k≤t−1} y^{k}) + (1 + y^{t})( ∑_{1≤l≤s−1} x^{l})]

where the outside sum is taken over 0 ≤ i < \frac{m}{s} and 0 ≤ j < \frac{n}{t}. By counting monomials, we conclude that the unique winning sequence of minimum length requires exactly \frac{2(s+t−1)}{st} · mn moves.

4.2 When the permissible moves vary in size: the checkerboard coloring pattern We apply equation (5) when the moves permitted can be of any size. In the case of the checkerboard coloring (3), equation (5) simplifies to

\begin{matrix}∑ m_{klst}x^{k}y^{l}(1 − x^{s})(1 − y^{t}) ≡ \\ ≡ 1 + x^{2m}y^{2n} + (1 + x^{2m})( ∑_{1≤i≤2m−1} x^{i}) + (1 + y^{2n})( ∑_{1≤j≤2n−1} y^{j}). \end{matrix}

(8)

We can interpret this equation as a new game played on a game board of size (2m + 1) × (2n + 1). According to the right hand side, the squares on the border are colored black except for the squares at positions (2m, 0) and (0, 2n), which are white as well as all of the interior squares. By reinterpreting the left hand sum of (8), the moves are “corner moves” where the colors of four squares are switched per move, namely those occupying positions (k, l), (k, l + t), (k + s, l) and (k + s, l + t).

Now, there is a simple solution to the original checkerboard game, already mentioned in Theorem 5, consisting of m+n moves. We can easily see from our new game that this is a minimal solution, for our new coloring has exactly 4m+4m−2 black squares, which will require at least ⌈\frac{4m+4n−2}{4}⌉ = m + n corner moves.

Furthermore, we can characterize all minimal solutions. Given any solution consisting of m+n corner moves, at least m+n−2 of these moves must account for four each of the 4m+4n−2 black squares. The black squares at positions (0, 0) and (2m, 2n) must be divided between the last two moves; for otherwise, if one of the moves accounts for both black squares, and thus changes the colors of the squares at (0, 2n) and (2m, 0) from white to black, then the other must perform the impossible task of restoring the original colors at (0, 2n) and (2m, 0) while allowing the colors at (0, 0) and (2m, 2n) to remain unchanged. The last two moves must then account for exactly three each of the remaining black squares, and thus share a common white square. If the common square is a corner white square then each of the m + n corner moves (including the last two) is composed of border squares, and in the original game, corresponds to a rectangular move that spans the board either horizontally or vertically. If the shared square is in the interior of the board, say at (k, l), then the last two moves correspond to two rectangular moves in the original game, the one with corners at (0, 0) and (k − 1, l − 1), the other with corners at (k, l) and (2m − 1, 2n − 1).

4.3 When the permissible moves vary in size: arbitrary coloring patterns

One might suspect that once restrictions are lifted on the variety of coloring patterns considered and on the sizes of the rectangular moves used, the generality would preclude anything of real interest from being said. Clearly, any coloring on a 2m × 2n game board can be solved and requires no more than 4mn moves. But can this upper bound be improved? We refer once again to equation (5), and interpret it as a new game with corner moves, as described in the previous subsection. Call the new coloring C′ and let ν be the number of black squares in C′. Now clearly, a minimal solution to the new game with coloring C′ must have length at least \frac{1}{4}ν. On the other hand, we now describe a winning strategy for C′ that requires no more than \frac{1}{2}ν moves. First, note that the multiplication of (4) by (1 − x) and (1 − y) guarantees an even number of black squares in each row and each column of C′. Divide into pairs the black squares in each row except the last. Then to each pair, apply the corner move consisting of two squares to account for the pair and the other two squares applied to the last row. The black squares in the last row will be handled automatically. We conclude that l, the length of a minimal solution for C, has the same order of magnitude as ν, because \frac{1}{4}ν ≤ l ≤ \frac{1}{2}ν.

If ν is large, for instance of the order of mn, then the upper bound on l can be tightened by creating a two phase winning strategy for the new game with coloring C′. Let S be a maximal set of disjoint corner moves that each account for four black squares in coloring C′. Clearly |S| ≤ \frac{1}{4}ν. We play the moves in S. Next, let C” = [c_{kl}”] be the new configuration consisting of the remaining black squares in C′ unaccounted for by S. C” inherits from C′ the property that each of its rows and columns contains an even number of black squares. Furthermore, C” has the delimiting property that any two of its columns must contain at most one pair of black squares occupying the same row. We use this property to bound the number of black squares in C”. Partition the columns of C” as evenly as possible into q = ⌊\frac{2n+1}{⌊\sqrt{m}⌋}⌋ subsets, so that each contains no more than ⌊\sqrt{m}⌋+1 columns. The black squares in each of the subsets can be divided between sets T_{1} containing each of the black squares that shares its row with another black square in the subset, and T_{2} containing the remaining black squares in the subset. By the delimiting property of C” no pair of columns can contain more than one pair of black squares from T_{1} in the same row, and thus |T_{1}| ≤ 2\binom{⌊\sqrt{m}⌋+1}{2}. Clearly, |T_{2}| ≤ 2m + 1 since each row contains at most one square from T_{2}. Thus, an upper bound on the number of black squares in C” is

q(2\binom{⌊\sqrt{m}⌋ + 1}{2} + 2m + 1) = ⌊\frac{2n + 1}{⌊\sqrt{m}⌋}⌋(2\binom{⌊\sqrt{m}⌋ + 1}{2} + 2m + 1)
≤ Kn\sqrt{m}

for some constant K that serves for all m and n. In fact, we can choose K = 15. We combine this argument with the same argument on the rows of C” to find that 15 min(m\sqrt{n}, n\sqrt{m}) is an upper bound on the number of black squares in C” for all m and n. Then, applying the argument used in the previous paragraph, we win C” in no more than \frac{15}{2} min(m\sqrt{n}, n\sqrt{m}) additional moves. Thus, we also have the inequality \frac{1}{4}ν ≤ l ≤ \frac{1}{4}ν + \frac{15}{2} min(m\sqrt{n}, n\sqrt{m}), i.e., l = \frac{1}{4}ν + O( min(m\sqrt{n}, n\sqrt{m})). Now Theorem 7 follows. For any coloring pattern C, since ν ≤ min (2m(2n+1), 2n(2m+1)), we conclude that l ≤ mn + O( min(m\sqrt{n}, n\sqrt{m})) as m, n → ∞.

Finally, the inequality is in some sense best possible, for by beginning with an entirely black pattern for C′ except for the last row and column, and tracing back to the corresponding coloring for C, one can find that the 2m × 2n game beginning with coloring C = [c_{ij}] defined by c_{ij} = 1 if and only if i and j are both even, requires exactly mn moves for a minimal solution.

5 Conclusion In this section we state some results that highlight the versatility of the techniques presented in this paper, and suggest further directions that the reader may wish to pursue. Theorems 9 and 11 follow directly by the techniques used in Sections 4.3 and 4.2, respectively, and are left for the reader as exercises. Roughly speaking, for board colorings generated by tiles, the former one bridges the gap between Theorems 5 and 7 by the degree of complexity imposed on the tiles. In fact, Theorem 9 extends Theorem 5 to colorings defined by simple tiles, and it refines Theorem 7 by allowing complex tiles. Theorem 10 relies on a more extensive argument rooted in Section 4.1. We will present the proof in a forthcoming paper.

Theorem 9 Let M = [m_{ij}] be a (0, 1) matrix of size s × t. For any m and n with s|m and t|n let C_{mn} be a 2m × 2n matrix consisting of \frac{2m}{s} · \frac{2n}{t} block copies of matrix M, and interpret C_{mn} as a coloring configuration in a game of size 2m × 2n, where the moves are arbitrarily sized rectangular patterns.

(i) If the matrix M has the property that each row of M is either equal to or the binary complement of the first row, then the number of moves in a minimal solution for C_{mn} is asymptotic to \frac{c}{s} ·m+ \frac{d}{t} ·n as m, n → ∞, where

c = |{i | m_{i,0} + m_{i+1,0} ≡ 1 mod 2, 0 ≤ i < s}|

and

d = |{j | m_{0,j} + m_{0,j+1} ≡ 1 mod 2, 0 ≤ j < t}|

are the number of color switches in all rows and columns of M, respectively. (ii) Otherwise, the number of moves in a minimal solution for C_{mn} is asymptotic to \frac{k}{st} · mn as m, n → ∞, where

k = |{(i, j) | m_{ij} + m_{i,j+1} + m_{i+1,j} + m_{i+1,j+1} ≡ 1 mod 2, 0 ≤ i < s,
0 ≤ j < t}|.

Here we let m_{sj} = m_{0j}, m_{it} = m_{i0} and m_{st} = m_{00}.

Theorem 10 Suppose the board is an arbitrarily colored circular one with n squares, and the moves are arcs of adjacent squares of length r. Let g = gcd(n, r) and S_{a} = ∑_{i≡amodg} c_{i}, for all 0 ≤ a < g. If \frac{r}{g} is even then the game can be won if and only if S_{a} ≡ 0 mod 2 for all a. On the other hand, if \frac{r}{g} is odd then it can be won if and only if all S_{a}, 0 ≤ a < g, have the same parity.

Theorem 11 If the board is a 2n × 2n checkerboard and the moves are arbitrarily sized squares then a minimal solution has length 4n − 2 and can be easily described.

References

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, vol. 2, Academic Press, London–New York, 1982

[2] F. Galvin, Solution to Problem 88-8, Math. Intelligencer 11 (1989), 31–32.

[3] R. Honsberger, In Pólya’s Footsteps, Mathematical Association of America, 1997

[4] O.P. Lossers, An all-ones problem, Amer. Math. Monthly 100 (1993), 806–807.

[5] L. Lovász, Combinatorial Problems and Exercises, North-Holland, New York, 1979

[6] D. H. Pelletier, Merlin’s magic square, Amer. Math. Monthly 94 (1987), 143–150.

[7] D. L. Stock, Merlin’s magic square revisited, Amer. Math. Monthly 96 (1989), 608–610.

[8] K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (1989), 49–53.

[9] P. Zeitz, The Art and Craft of Problem Solving, Wiley, 1999