IMO 2002 SL C2

Origin: ARM | Category: Combinatorics

Problem

For n an odd positive integer, the unit squares of an n \times n chessboard are colored alternately black and white, with the four corners colored black. A 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 nonoverlapping trominos? When it is possible, what is the minimum number of trominos needed?

Solution

Write n = 2k + 1. Consider the black squares at an odd height: there are (k + 1)2 of them in total and no two can be covered by one trimino. Thus, we always need at least (k + 1)2 triminoes, which cover 3(k + 1)2 squares in total. However, 3(k + 1)2 is greater than n2 for n = 1, 3, 5, so we must have n \geq7. The case n = 7 admits such a covering, as shown in Figure 1. For n > 7 this is possible as well: it follows by induction from Figure 2.

(n −2)\times (n −2) Fig. 2 Fig. 1