Maths Olympiad Prep

Library / /147 of 520

Combinatorics Difficulty 6.0 National olympiad Find the answer

For all positive integers n,kn, k, let f(n,2k)f(n, 2k) be the number of ways an n×2kn \times 2k board can be fully covered by nknk dominoes of size 2×12 \times 1. (For example, f(2,2)=2f(2,2)=2 and f(3,2)=3f(3,2)=3.)
Find all positive integers nn such that for every positive integer kk, the number f(n,2k)f(n, 2k) is odd.
Proposed by: U.S.A.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The integers n n with the requested property are exactly the ones of the form 2k1 2^{k}-1 .
In what follows, let f(m,n) f(m, n) denote the number of domino tilings of an m×n m \times n grid. (For convenience, we also allow m m and n n to be 0, in which case f(m,n)=1 f(m, n)=1 .)

Claim. f(m,2n+1)f(m,n)(mod2) f(m, 2 n+1) \equiv f(m, n) \pmod{2} for all n n and even m m .
Proof. Consider reflecting m×(2n+1) 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,2n+1) 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 m2 \frac{m}{2} vertical dominoes, splitting the remainder of the grid into two m×n m \times n grids. Obeying the symmetry constraint, there are f(m,n) f(m, n) tilings: each of the tilings of the left grid fixes the tiling of the right grid.

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

We are ready to complete the solution.

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

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.