For all positive integers $n, k$, let $f(n, 2k)$ be the number of ways an $n \times 2k$ board can be fully covered by $nk$ dominoes of size $2 \times 1$. (For example, $f(2,2)=2$ and $f(3,2)=3$.)
Find all positive integers $n$ such that for every positive integer $k$, the number $f(n, 2k)$ is odd.
Proposed by: U.S.A.
The integers \( n \) with the requested property are exactly the ones of the form \( 2^{k}-1 \).
In what follows, let \( f(m, n) \) denote the number of domino tilings of an \( m \times n \) grid. (For convenience, we also allow \( m \) and \( n \) to be 0, in which case \( f(m, n)=1 \).)

Claim. \( f(m, 2 n+1) \equiv f(m, n) \pmod{2} \) for all \( n \) and even \( m \).
Proof. Consider reflecting \( m \times (2 n+1) \) tilings across the central column. In this way, the tilings are grouped into singletons and pairs, so modulo 2, \( f(m, 2 n+1) \) 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 \( \frac{m}{2} \) vertical dominoes, splitting the remainder of the grid into two \( m \times n \) grids. Obeying the symmetry constraint, there are \( f(m, n) \) tilings: each of the tilings of the left grid fixes the tiling of the right grid.

Claim. \( f(n, n) \equiv 0 \pmod{2} \) for all even \( n \geq 2 \). (Recall that \( f(0,0)=1 \) is odd.)
Proof. Consider reflecting \( n \times n \) tilings across the diagonal. This groups the tilings into pairs, (no tiling is grouped with itself). Hence the number of \( n \times n \) tilings is even.

We are ready to complete the solution.

- If \( n \) is odd, the first claim shows that \( n \) satisfies the property if and only if \( \frac{1}{2}(n-1) \) does.
- If \( n \geq 2 \) is even, the second claim shows that \( n \) does not satisfy the property.
- If \( n=0 \), then \( n \) satisfies the property, as \( f(m, 0)=1 \) always.

This concludes the proof that the sought numbers are the ones of the form \( 2^{k}-1 \).