4
$\begingroup$

I recently downloaded a game to my TI NSPIRE CX called Complete the Square. http://www.ticalc.org/pub/nspire/lua/games/. Players take turns placing stones on a six-by-six board. One player has blue stones, the other player has red stones. Only one stone may be put on a square. Players continue in this fashion, placing stones until one person's stones form the four corners of a square. That player is the winner. My question is this: Is it possible to completely fill up the board so that the game ends in a draw? Clearly this is true for a 2x2 board, and, with a little thought, one can see it is also true for a 3x3 board. Is there and easy way to determine whether or not an non board can be a draw? What about NxM boards? I think this question might have something to do with graph theory, so I shall file it as such, but feel free to move it if you believe it belongs elsewhere. I ask this question because I wanted to find a winning strategy, and one must clearly exist if the game can never end in a draw. Furthermore, it must be a 1st player win, because if there existed a second player winning strategy, the 1st player could make a random move for his first turn and then follow the second player strategy for the rest of the game.

$\endgroup$
  • $\begingroup$ Must a winning square have horizontal and vertical sides? Or do 'tilted' squares also count? $\endgroup$ – paw88789 Nov 21 '17 at 18:09
  • $\begingroup$ A square only requires four corners. A square of any size is acceptable, as long as the sides are parallel to the sides of the board. Tilted squares do not count. $\endgroup$ – William Grannis Nov 21 '17 at 18:31
  • $\begingroup$ You are correct that the second player cannot have a winning strategy. If there are no drawn positions the first player will have a winning strategy. $\endgroup$ – Ross Millikan Nov 21 '17 at 18:56
  • $\begingroup$ I've replaced the graph-theory tag with ramsey-theory; that definitely applies, and I don't think a graph theory connection really exists. $\endgroup$ – Misha Lavrov Nov 21 '17 at 23:31
4
$\begingroup$

We mostly know the answer to this question, but not quite.

I'm going to ignore the condition that in an actual complete-the-square game, the number of red and blue stones at the end should be equal or off by one. Instead, we can just look for an arbitrary coloring of the grid that avoid squares whose corners are the same color. If one exists, then it will generally be balanced or nearly balanced, and we can probably make it balanced by fiddling with it a little. (After all, very unbalanced colorings should have lots more squares whose corners are the same color.)


Here's one result that's relatively easy to prove: if $M + 2N \le 36$ (or, by symmetry, if $N + 2M \le 36$) then a squareless coloring exists on an $M \times N$ board. For example, a squareless coloring exists on a $12 \times 12$ grid.

To create such a coloring, start with the following coloring of the integers $1, 2, \dots, 34$ (found by Chvátal in 1970) $$ \color{blue}{1}\,\color{red}{2}\,\color{blue}{3}\,\color{red}{4}\,\color{red}{5}\,\color{red}{6}\,\color{blue}{7}\,\color{blue}{8}\,\color{blue}{9}\,\color{red}{10}\,\color{blue}{11}\,\color{red}{12}\,\color{red}{13}\,\color{blue}{14}\,\color{red}{15}\,\color{red}{16}\,\color{red}{17}\,\color{blue}{18}\,\color{blue}{19}\,\color{blue}{20}\,\color{red}{21}\,\color{blue}{22}\,\color{blue}{23}\,\color{red}{24}\,\color{blue}{25}\,\color{red}{26}\,\color{red}{27}\,\color{red}{28}\,\color{blue}{29}\,\color{blue}{30}\,\color{blue}{31}\,\color{red}{32}\,\color{blue}{33}\,\color{blue}{34} $$ in which no arithmetic progression of length $4$ has the same color. Next, label the squares of the grid by integers in the following pattern:

\begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & \cdots \\ 3 & 4 & 5 & 6 & 7 & \cdots \\ 5 & 6 & 7 & 8 & 9 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

In this labeling, a $d \times d$ square whose top left corner is labeled $a$ will contain the labels $a+d, a+2d, a+3d$ in its other corners. So if we transfer the coloring of the integers to a coloring of the grid by using this labeling, then no square will be monochromatic, showing us how to get a draw.

(The condition $M+2N \le 36$ guarantees that we only need the integers $1,2,\dots,34$ for the labeling. This is important because there's no coloring of the integers $1,2,\dots,35$ with the same property.)


For square grids, we further know that (again, ignoring the number of stones of each color) a draw is possible on a $14 \times 14$ grid, but not on a $15 \times 15$ grid. Unfortunately, there's no construction as "nice" as the one above: it's just that in this paper, the $14 \times 14$ and $15 \times 15$ questions are verified by SAT solver.

This still leaves open the question of what happens when we play on long and thin rectangles. For example, on a $3 \times N$ board, a draw is possible for all $N$: just extend the coloring \begin{array}{ccccc} \color{red}{\bullet} & \color{blue}{\bullet} &\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{red}{\bullet} & \color{blue}{\bullet}&\color{red}{\bullet} &\color{blue}{\bullet} &\cdots \\ \color{blue}{\bullet} & \color{red}{\bullet} &\color{blue}{\bullet} &\color{red}{\bullet} &\cdots \end{array} as far as you like. Is this possible on a $4 \times N$ board? Quite possibly. On a $13 \times N$ board? Almost certainly not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.