Writeup: IMO Shortlist 2002 C2

29 Apr, 2025

Problem Statement

For $n$ an odd positive integer, the unit squares of an $n\times n$ chessboard are coloured alternately black and white, with the four corners coloured black. A it tromino is an $L$-shape formed by three connected unit squares. For which values of $n$ is it possible to cover all the black squares with non-overlapping trominos? When it is possible, what is the minimum number of trominos needed?

My Solution

Note that if we color the board into 4 colors (based on parity of $x$ and $y$-coordinates), then each tile with both an even $x$ and $y$ coordinate must be covered by one tromino, and we can't cover two of these tiles with one tromino. Since there are $\frac{(n+1{)}^2}{2}$ such tiles, we need at least trominoes. This isn't possible for $n=3$ and $5$ since each tromino covers $3$ tiles, and we would be covering more tiles than there are total squares. For $n=7$, a valid construction is shown below. Also, a way to extend to any odd number by adding two more rows and columns is shown too. So the answer is $n\ge 7$.

https://drive.google.com/file/d/1H6zTbOBE0tvMjwkdiNixUU1SVzaMr-6Z/view?usp=sharing

https://drive.google.com/file/d/1SHPTZNCzzD0olSw8bKTNc-VGghaLDNW3/view?usp=sharing