Let be an odd natural number. The fields of an 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 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 chessboard has rows with odd numbers, and in each of these rows, there are black squares. Each of these black squares must be covered by a different triomino, so at least triominoes are required. Since each consists of 3 squares, due to the no-overlap rule, it must hold that: . For 1, 3, and 5, this gives , , . Therefore, for , the required covering is not possible.
The figure shows, as an anchor, a covering for with triominoes and the step , which proves the existence of a covering for every . In this step, an "L" shape, 5 fields wide and high, is added to the right bottom corner of the chessboard, whose covering with stones is assumed, and then completed with fields, each with a matching triomino. The "L" contains 5 triominoes, and the two rectangles together contain triominoes. Thus, there are triominoes, the minimum number for the 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 are compatible with the minimum number, as well as mentioning .
!