For all positive integers , let be the number of ways an board can be fully covered by dominoes of size . (For example, and .)
Find all positive integers such that for every positive integer , the number is odd.
Proposed by: U.S.A.
Solution
The integers with the requested property are exactly the ones of the form .
In what follows, let denote the number of domino tilings of an grid. (For convenience, we also allow and to be 0, in which case .)
Claim. for all and even .
Proof. Consider reflecting tilings across the central column. In this way, the tilings are grouped into singletons and pairs, so modulo 2, is congruent to the number of singletons.
If a tiling is invariant under reflection in the central column, then every domino with one cell in that column must have both cells in that column.
In other words, the central column is filled with vertical dominoes, splitting the remainder of the grid into two grids. Obeying the symmetry constraint, there are tilings: each of the tilings of the left grid fixes the tiling of the right grid.
Claim. for all even . (Recall that is odd.)
Proof. Consider reflecting tilings across the diagonal. This groups the tilings into pairs, (no tiling is grouped with itself). Hence the number of tilings is even.
We are ready to complete the solution.
- If is odd, the first claim shows that satisfies the property if and only if does.
- If is even, the second claim shows that does not satisfy the property.
- If , then satisfies the property, as always.
This concludes the proof that the sought numbers are the ones of the form .