Maths Olympiad Prep

Library / /446 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it

Let nn be an odd natural number. The fields of an n×nn \times n chessboard are alternately colored black and white, with the corner fields being black. Furthermore, a triomino is defined as an L-shaped figure consisting of three connected unit squares.
a) For which values of nn is it possible to cover all black fields of the chessboard with non-overlapping triominoes?
b) What is the minimum number of triominoes required for the covering when it is possible?
Hint: Two triominoes overlap if they share at least one unit square.

Solution

a) and b): We count the rows of the chessboard from the top. The n×nn \times n chessboard has n+12\frac{n+1}{2} rows with odd numbers, and in each of these rows, there are n+12\frac{n+1}{2} black squares. Each of these (n+12)2\left(\frac{n+1}{2}\right)^{2} black squares must be covered by a different triomino, so at least (n+12)2\left(\frac{n+1}{2}\right)^{2} triominoes are required. Since each consists of 3 squares, due to the no-overlap rule, it must hold that: 3(n+12)2n23\left(\frac{n+1}{2}\right)^{2} \leq n^{2}. For 1, 3, and 5, this gives 313 \leq 1, 12912 \leq 9, 272527 \leq 25. Therefore, for n<7n<7, the required covering is not possible.
The figure shows, as an anchor, a covering for n=7n=7 with (n+12)2=16\left(\frac{n+1}{2}\right)^{2}=16 triominoes and the step nn+2n \rightarrow n+2, which proves the existence of a covering for every n7n \geq 7. In this step, an "L" shape, 5 fields wide and high, is added to the right bottom corner of the n×nn \times n chessboard, whose covering with (n+12)2\left(\frac{n+1}{2}\right)^{2} stones is assumed, and then completed with 2×22 \times 2 fields, each with a matching triomino. The "L" contains 5 triominoes, and the two 2×(n5)2 \times (n-5) rectangles together contain n3n-3 triominoes. Thus, there are (n+12)2+n3+5=n2+6n+94=(n+32)2\left(\frac{n+1}{2}\right)^{2} + n - 3 + 5 = \frac{n^{2} + 6n + 9}{4} = \left(\frac{n+3}{2}\right)^{2} triominoes, the minimum number for the (n+2)×(n+2)(n+2) \times (n+2) chessboard. By complete induction, the claim follows.
Note: Only all black squares should be covered; white squares can remain uncovered. Of course, the triominoes do not extend beyond the chessboard. A complete solution also includes proving that the added triominoes in the step nn+2n \rightarrow n+2 are compatible with the minimum number, as well as mentioning n=1n=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.