6
$\begingroup$

Alice and Bob are playing a game on an initially empty 3x3 matrix. They take turns, and each turn:

  • They add a number in {1,2,3} to an empty cell.
  • They are not allowed to repeat a number in a row or a column (like a partial Latin square).
  • The last person to move wins.

Alice goes first. A game might proceed as follows:

      A    B    A    B    A    B    A
...  1..  1..  1..  1..  1..  13.  13.
...  ...  ..3  ..3  ..3  .23  .23  .23
...  ...  ...  .1.  .12  .12  .12  312

In this example, Bob can't make a move, so Alice wins.

Question: Does Alice always win?

I'm just curious about this game because it relates to my research (partial Latin squares). I haven't actually sat down and written out a proof, but I believe there is a more intelligent answer than "I computed all possibilities".

$\endgroup$
1
  • $\begingroup$ Pretty sure Alice always win, not sure about the proof yet (I managed to make alice win with 4 empty squares) $\endgroup$
    – DialFrost
    Jun 23 at 5:57

2 Answers 2

5
$\begingroup$

Alice wins. Strategy:

1. Choose a diagonal
2. Place a number on the diagonal
3. Whenever Bob puts a number outside the diagonal, put the same number mirrored at the diagonal
4. If Bob puts a number on the diagonal, also put a number on the diagonal (this is possible because the row and column intersecting at the diagonal element Alice needs to fill have the same entries because of (3))

$\endgroup$
5
  • 3
    $\begingroup$ Huh. This isn't exactly what I asked about, but this proof works for all odd orders n (not just n=3 as in the question). And it seems like it also proves Bob can force a win for even n (with Bob's first step "choose a diagonal intersecting Alice's first move"). Fascinating! $\endgroup$ Jun 23 at 6:24
  • 2
    $\begingroup$ @RebeccaJ.Stones why isn't this exactly what you asked about? $\endgroup$
    – justhalf
    Jun 23 at 8:09
  • 2
    $\begingroup$ I'm asking if Alice always wins, regardless of strategy (even if she tries to lose), not if she wins with best strategy. $\endgroup$ Jun 23 at 8:10
  • 2
    $\begingroup$ @RebeccaJ.Stones so you are basically asking does every maximal partial 3x3 Latin square have an even number of gaps? (Assuming a partial Latin square is one whose existing entries have no row or column duplicates?) $\endgroup$
    – loopy walt
    Jun 23 at 8:53
  • $\begingroup$ Well yes, but only for 3x3. It's a puzzle. $\endgroup$ Jun 23 at 9:14
1
$\begingroup$

Without regard for strategy, considering cases:

If there is exactly one empty cell, the game is not over. I will say a cell "sees" another cell if they share a row or column. There are four cells that see the empty cell and four that don't. By the pigeonhole principle, two of the cells that don't see the empty cell contain the same number. Because these share neither a row or column, they see all four cells that see the empty cell, so those four cells don't contain this number. Thus, this number can be placed in the empty cell.

If there are exactly three empty cells, the game is not over. WLOG, the number of times $1$, $2$, and $3$ appear (respectively) can only be $(3, 3, 0)$, $(3, 2, 1)$, or $(2, 2, 2)$. In the case of $(3, 3, 0)$, $3$ can be placed in any of the empty cells. In the case of $(3, 2, 1)$, $1$ appears once in every row and once in every column. Thus, it appears twice in cells that see the cell with $3$: (once in the same row and once in the same column). So, there is an empty cell that doesn't see the cell with $3$ where another copy of $3$ can be placed. In the case of $(2, 2, 2)$, there is a unique cell that sees neither copy of $1$. Suppose, no move is possible. WLOG, $2$ occupies this cell. Then in the four cells that don't see this cell, there are two copies of $1$ and another copy of the $2$. If the fourth of these cells was empty, $2$ could be placed there, so it must be occupied by $3$. But, there are two other cells that could simultaneously contain additional copies of $3$. (This configuration is depicted below up to permutation of rows and columns and symmetry on the diagonal.) This is a contradiction, so some move must be possible.

12.
31.
..2

If there are between five and eight empty cells, the game is not over. Some number appears only once. There are four cells that don't see the cell with this number, and at most three are filled, so a second copy of that number can be placed in one of those cells.

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