2
$\begingroup$

Disclaimer: The purpose of this post is a ask question, not to offer a puzzle. Still, there are some puzzles here for the reader's pleasure.

Disclaimer 2: This question was also asked on Math Stack Exchange. I gave an answer there which gives some partial progress.


Animal tic-tac-toe was conceived by Frank Harary in 1977. It is like regular tic-tac-toe, except it is played on a $b\times b$ board, for some integer $b$. Also, instead of trying to get three-in-a-row, both players are trying to make a certain polyomino shape with their marked squares. Any rotation or reflection of the polyomino counts as a win. The players are X and O, with X playing first. Each choice of $b$ and each choice of polyomino gives a different game. The five possible tetrominos were given the following cute names by Harary:

enter image description here

Using a strategy-stealing argument, you can prove that O cannot win under optimal play. Therefore, the question of interest is: for each polyomino, what is that smallest board size on which X can achieve that polyomino, and in how few moves can he do so?

The following data summarizes the known results for polyominos with three and four cells. I have seen these numbers published in several places, cited at the end. However, I cannot find a winning strategy for Skinny, the $4\times 1$ rectangle, on a 7 x 7 board.

Question: Can X achieve a 4 x 1 rectangle on a 7 x 7 board? Remember that diagonals are not allowed. Can it be done in eight moves?

I understand that this is a hard question, and the answer would likely be a relatively complex strategy. I hope that it is actually answerable, since all of the sources below claimed it is true without proof, or the barest sketch of a proof.

Puzzles for the readers enjoyment: Show how X can win for each of the other polyominos, on the given board sizes. Also, prove that X cannot achieve the 2x2 square on any board size.

Polyomino Minimal board size where X wins Minimal number of moves for X to win
Straight Tromino 4 3
Bent Tromino 3 3
Tippy (S Tetromino) 3 5
Elly (L Tetromino) 4 4
Knobby (T Tetromino) 5 4
Fatty (2x2 Square) X cannot win on any board size N/A
Skinny (4x1 rectangle) 7? 8?

Sources that claim that Skinny is achievable on a 7 x 7 in 8 moves, all without proof:

Beck, József (2008), Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, 114, Cambridge: Cambridge University Press, pp. 60–64, doi https://doi.org/10.1017%2FCBO9780511735202

Gardner, M. (2001). The colossal book of mathematics: Classic puzzles, paradoxes, and problems. W. W. Norton.

Harary, Frank, "Achieving the Skinny Animal," Eureka, No. 42, Summer 1982, pp. 8-14; Errata, No. 43, Easter, 1983, pp. 5-6.

$\endgroup$

1 Answer 1

3
$\begingroup$

Daniel Mathias has solved this question in a comment on the MSE post, so for completeness I will summarize the entire strategy here.

X starts by claiming the center. Up to symmetry, O's response is one of the nine squares below: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&& \\\hline &&&&&& \\\hline &&&&&& \\\hline &&&X_1&&& \\\hline &&\color{gray}{O_1}&\color{gray}{O_1}&\;\;\;\;&\;\;\;\;&\;\;\; \\\hline &\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&\color{gray}{O_1}&&& \\\hline \end{array} $$ I have winning strategies for seven of these responses, as shown below: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&\color{gray}{O_3}& \\\hline &&&X_4&\color{gray}{X_5}&X_3& \\\hline &&&\color{gray}{X_5}&&\color{gray}{O_3}& \\\hline &&\color{gray}{O_2}&X_1&\color{gray}{O_2}&X_2&\color{gray}{O_2} \\\hline &&&&\;\;\;\;&\color{gray}{O_3}&\;\;\; \\\hline &\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \color{gray}{O_1}&\color{gray}{O_1}&&\color{gray}{O_1}&&& \\\hline \end{array}\qquad \begin{array}{|c|c|c|c|c|c|c|} \hline &&\color{gray}{O_3}&&&& \\\hline &&\color{gray}{O_3}&\color{gray}{X_5}&&& \\\hline &&X_3&X_4&\color{gray}{X_5}&& \\\hline &\color{gray}{O_2}&X_2&X_1&\color{gray}{O_2}&& \\\hline &&\color{gray}{O_3}&&&\;\;\;\;&\;\;\; \\\hline &&\color{gray}{O_1}&&&& \\\hline \;\;\;\;&&\color{gray}{O_1}&&&& \\\hline \end{array} $$

All that remains is when O responds either orthogonally or diagonally adjacent to the center. These lines of play were worked out by Daniel Mathias:

enter image description here

$\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.