Maths Olympiad Prep

Track / Stage 7 / 82 of 300 #1482 of 1964

Problem 1482

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.1 Prove it

m×nm\times n grid is tiled by mosaics 2×22\times2 and 1×31\times3 (horizontal and vertical). Prove that the number of ways to choose a 1×21\times2 rectangle (horizontal and vertical) such that one of its cells is tiled by 2×22\times2 mosaic and the other cell is tiled by 1×31\times3 mosaic [horizontal and vertical] is an even number.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Assign Values to Unit Squares:
- Write the number 11 in each unit square tiled by 2×22 \times 2 tiles.
- Write the number 00 in each unit square tiled by 3×13 \times 1 tiles (both horizontal and vertical).

2. **Define the Sum SS:**
- For any possible 1×21 \times 2 rectangle (domino), sum up all the numbers on the unit squares covered by that domino.
- Add all these sums together to get the total sum SS.

3. Double Counting and Modulo Operation:
- Let NN be the number of 11's on the edges of the grid, excluding the corners.
- Notice that SN(mod2)S \equiv N \pmod{2} because each 1×21 \times 2 rectangle contributes to SS based on the number of 11's it covers.

4. **Claim: NN is Even:**
- Investigate the cases when 2×22 \times 2 tiles are on the edge but do not contain any corners.
- Also, consider the case when a 2×22 \times 2 tile contains a corner unit square.
- In each case, each 2×22 \times 2 tile adds exactly 22 11's to NN, making the total even.

5. Conclusion:
- Since NN is even, SS must also be even.
- The sum SS is equal to the number of neighboring edges between 2×22 \times 2 tiles and 3×13 \times 1 tiles.
- Therefore, the number of ways to choose a 1×21 \times 2 rectangle such that one of its cells is tiled by a 2×22 \times 2 mosaic and the other cell is tiled by a 1×31 \times 3 mosaic is even.

\blacksquare

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