Problem of the Week 1174

Chessboard Solitaire

Solution

The problem as stated was solved by the people mentioned below, and also by Rob Pratt, John Guilford, and Joseph DeVincentis. Several new results have been obtained, notably by Michael Schweitzer and Derek Smith.

Let R(n) refer to the assertion (invented by Moshe Rosenfeld) that an n × n board can be filled with 2k marks, where we start with one mark, and then duplicate the array into open squares, and where k is as large as possible:

k = Floor[log2[n²]]

For example, when n is 7, there are 32 marks, so k = 5.

When I posted the problem, the following cases (for n ≤ 100) were open: 12, 23, 24, 46, 47, 48, 91, 92, 93, 94, 95, 96. Now all these are resolved except for n = 96.

Problem 1174 asked about R(7); R(7) is true, and there is a unique answer, as proved some time ago by Raphael Robinson. This picture shows the solution for R(7):

The solution can be described, assuming the board consists of [0, 6] × [0, 6], by saying: Start with the seed = {0,4}, and then use the sequence of duplications given by the translation vectors T = {(1, 0), (1, 1), (1, -1), (0, -3), (3, 1)}.

In characters, the solutions starts with A below, and duplicates to B, C, D, E, and F.

|-------|
|    FF |
| CCFFFF|
|ABDDFF |
| DD FF |
| EEFFFF|
|EEEEFF |
| EE    |
|-------|

Let's use the term "trivial solution" for the 2(2n) collection of marks on a 2n × 2n grid obtained by starting with the lower left corner and filling a row, and then using that to fill the columns, thus filling the whole grid.

Because of how the boundary behaves, one can use the 7 × 7 solution to duplicate two more times and get a solution for R(13), and again to R(25) and R(49) and so on. Here is a picture of this inductive derivation:

Note also that the solution for R(7) arises by a similar recursive construction used on an 8-mark solution for the 4 × 4 grid. Of course, that grid admits a trivial 16-mark solution.

Alternatively, to get the 13 × 13 solution, just append (6, 0) and (0, 6) to the translation vectors above:

{(1, 0), (1, 1), (1, -1), (0, -3), (3, 1)}

To get the 25 × 25 solution, append (12, 0) and (0, 12); and so on.

In looking at the general case, the situation is trivial for cases where k is the square of a power of 2. For example, 64 marks are easily placed on an 8 × 8 board, and that settles R(8), R(9), R(10), R(11). Similarly, R(16), R(17), R(18), R(19), R(20), R(21), R(22) are all true.

So the interesting cases are 3, 6, 12, 13, 14, 15, 23, 24, and so on. These are the intervals from Ceiling[Sqrt[2(2s + 1)]] to 3*2(s - 1), inclusive.

Thus, [12], [23, 24], [46, 48], [91, 96], [182, 192], .... It is easy to check that R(3) and R(6) are false.

If all these intervals could be resolved, and resolved negatively, then one could say that the only essential solution to the duplication problem is the 7 × 7 case.

Michael Schweitzer, Kirk Bresniker, and Derek Smith were able, by computer search, to show that R(12) is false. Michael Schweitzer and Derek Smith then, independently, came up with a proof by hand, and that proof extended to 23, 24, 46, 47, and 48.

To go beyond that required some symbolic computation, and Smith set that up and was able to resolve 91 and 92 (and more generally to Ceiling[Sqrt[2(2s + 1)]] and Ceiling[Sqrt[2(2s + 1)]] + 1). To go beyond 92, Schweitzer and Smith employed computer searches using similar methods, resolving 93, 94, and 95. A similar computer search also showed that the solutions for 13, 25, and 49 are unique up to the symmetries of the grid.

For more info on the techniques, or to see a comprehensive set of notes when they are prepared, contact Derek Smith or Michael Schweitzer.

References

Moshe Rosenfeld, A "simple" rectangular puzzle, Electronic Notes in Discrete Mathematics 28 (2007) 409-415.
Moshe Rosenfeld, A dynamic puzzle, Amer. Math. Monthly, 98 (1991) 22-24.

[Back to Problem 1174]

© Copyright 2014 Stan Wagon. Reproduced with permission.


21 February 2014