7
$\begingroup$

Two players are presented an $n\times n$ grid. They take turns placing a piece on the board until no more moves are possible. The last player able to make a move is the winner. The pieces are $2\times 1$ dominoes and $3\times 1$ trominoes. Both players have an infinite supply of both pieces. When placing a piece, it cannot lie on top of previously placed pieces. (Instead of placing pieces on a board, you may instead imagine two players circling appropriately sized regions on grid paper)

For all $n\ge 1$, determine which player wins, and describe the strategy to guarantee a win.

$\endgroup$
  • 1
    $\begingroup$ Surely this is a strategy puzzle... and would that make it inelegible for the FTC? $\endgroup$ – boboquack Jul 17 '18 at 6:15
  • $\begingroup$ @boboquack Unfortunately, I think you're right. I was not thinking about the strategy tag when I made this, but now I see that it is probably the best-fitting tag. I will remove this entry from FTC. $\endgroup$ – Riley Jul 17 '18 at 22:37
5
$\begingroup$

For $n = 1$, it's trivial that first player can't win since he can't make any move.

Also for $n = 2$, both players can make the moves so the board will be full (by placing two $1 \times 2$ tiles), hence the first player can't win too.

But for $n \geq 3$,

First player will win if $n$ is odd and second player will win if $n$ is even.

The strategy is simply to mirror (to the center point of the grid) the opponent's moves. For first player if $n$ is odd, he can simply put $1 \times 3$ tile in the middle at the beginning.

For more details:

By mirroring to the center point of the grid means the cell on up left is "pairing" to the cell on down right. The cell on $i$-th row from above and $j$-th column from left is pairing to the cell on $i$-th row from below and $j$-th column from right.

Take a note that the $1 \times 2$ and $1 \times 3$ tiles will not occupy two cells which are pairing to each other (except the first $1 \times 3$ one from first player when $n$ is odd). Small proof: The pairing is on the different row and column.

Initially, every two cells which are pairing to each other are both unoccupied or occupied.
By previous statement, if one put the unoccupied cells; the other one may simply put their pairs since they must be unoccupied too. By doing so, the integrity is still same: every two cells which are pairing to each other are both unoccupied or occupied.

Therefore, the player who copied the opponents moves will win the game.

$\endgroup$
  • 1
    $\begingroup$ Do you think you could explain the strategy in greater detail? And more about why/how it works. $\endgroup$ – Riley Jul 10 '18 at 2:49
  • 2
    $\begingroup$ @Riley ok I'm trying. I'm sorry I can't use any images here because imgur is currently blocked in my country lol. $\endgroup$ – athin Jul 10 '18 at 3:04

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.