1
$\begingroup$

Consider a $2 \times 2011$ table. Two players in turn place dominoes on it, the first one place only horizontal dominoes and the second one places only vertical dominoes. The dominoes may not overlap. The player who has no legal moves loses the game.

How can we define a winning strategy for a player?

enter image description here

$\endgroup$
2
  • 2
    $\begingroup$ This game is called en.wikipedia.org/wiki/Domineering . See also arxiv.org/pdf/math/0006066.pdf $\endgroup$
    – Robert Z
    Mar 12, 2022 at 16:02
  • 2
    $\begingroup$ Hint: Whenever player one plays a horizontal domino, she "reserves" a move for herself later, since player two cannot touch the space vertically adjacent to that domino. Try to find a strategy where she can reserve a lot of moves. $\endgroup$
    – Mike Earnest
    Mar 12, 2022 at 17:07

1 Answer 1

Reset to default
1
$\begingroup$

The winner is the first player. Imagine dividing the board into $1005$ $2\times 2$ squares, with one $2\times 1$ domino leftover. For each of her first $503$ moves, the first player will cover the bottom half of one of the $2\times 2$ squares. This is always possible, since each move by the second player can obstruct at most one of these squares. Then, for the next $503$ moves, the first player plays in the top half of the blocks she played in earlier. This ensure the first player gets to play $1006$ dominos. After she plays her $1006^\text{th}$ domino, the board is perfectly filled, and player two loses.

$\endgroup$
2
  • $\begingroup$ This doesn't work as is. Your argument implies the first player is the winner for the board $2 \times 5$, but in fact, the second player has the winning strategy here. In particular, if the first player places their domino at the bottom half of the first and second column, then the second player can place their domino on the fourth column. (The second player could also use same technique for the $2 \times 2011$ board, on their 503rd move.) $\endgroup$
    – VTand
    Mar 30, 2022 at 3:46
  • 1
    $\begingroup$ @VTand My strategy only generalizes to boards of the form $2\times (4k+3)$, which does not include $2\times 5$. The key point is that when you divide the board into $2\times 2$ squares in the $2\times 2011$ case, there are an odd number of squares, so player one can claim a strict majority. When you try to do that for the $2\times 5$, there are an even number of squares, so player one can only claim an equal number of squares to player two, which is not enough. $\endgroup$
    – Mike Earnest
    Mar 30, 2022 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .