3
$\begingroup$

A polyomino is a two-dimensional shape formed by putting together some unit squares fully along their edges. An N-omino is a polyomino formed with exactly N unit squares. Two N-ominoes are the same if one can be transformed into the other via reflection and/or rotation.

A rectangular grid of R rows and C columns is also given. Poly's objective is to choose some N-ominoes and tile the grid, i.e. fill the grid without gaps, overlaps, or any part being outside the grid. Omino can choose one N-omino that Poly must use in their tiling. If Poly completes their tiling using Omino's choice, Poly wins; if Poly fails to do so, Omino wins.

Some examples:

  • If N = 3 and (R,C) = (3,2), Omino's two possible choices are I- and L-tromino. In both cases, Poly can tile a 3x2 grid using two copies of Omino's choice, so Poly wins.
  • If N = 4 and (R,C) = (1,4), Omino can choose any tetromino that is not an I. Poly has no way to fit it in the grid that is too narrow, so Omino wins.

For each possible value of N, R, and C, determine who will win, assuming both players play optimally.


Source: Google Code Jam 2015, Qualification Round, Problem D

$\endgroup$

1 Answer 1

2
$\begingroup$

We assume that $N$ divides the product $RC$, because otherwise it is impossible to tile the $R\times C$ board by $N$-ominoes, so then Omino always wins.

Observe that if Poly wins with $N$-polyominoes at $R'\times C'$ board and $R\ge R'$, $C\ge C'$ then Poly also wins with $N$-polyominoes at $R'\times C'$ board. This is because then the $R\times C$ board with $R'\times C'$ board removed from the corner has a Hamiltonian path of adjacent cells, which can be tiled by $N$-ominoes.

For simplicity we assume that $R\le C$.

Omino wins if:

$N\ge 7$, because then Omino can chose an $N$-mino with $1\times 1$ hole and then it will be impossible to tile a rectangular board using this $N$-mino.

$N>C$, because then there is no tiling of the board using $1\times N$ rectangle.

$N>2R$, because then there is no tiling of the board using some $L$-shaped $N$-omino.

$N=4$ and $R\le 2$, because then Omino can chose this tetromino:

  x
 xxx
 

$N=5$, $R\le 3$, and $C=5$, because then Omino can chose this pentomino:

 x
 xx
  xx
 

$N=6$ and $R\le 3$, because then Omino can chose this hexomino:

  x
  x
 xxxx
 

Poly wins if:

$N\le 3$, because then Poly can place the $N$-omino chosen by Omino at a corner of the board and then tile the remaining space.

$N=4$ and $R\ge 3$. This follows from the observation at the beginning of the answer and the fact that Poly wins at the $3\times 4$ board.

$N=5$, $R\ge 3$, and $RC\ge 20$. This follows from the observation at the beginning of the answer and the facts that Poly wins at the $3\times 10$ and $4\times 5$ boards.

$N=6$, $R\ge 4$, and $C\ge 6$. This follows from the observation at the beginning of the answer and the fact that Poly wins at the $4\times 6$ board.

$\endgroup$
1
  • $\begingroup$ N>C and N>2R cases are not really necessary if you limit to the cases where N<=6 and N divides RC. $\endgroup$ Commented Dec 26, 2024 at 23:10

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.