Browse · MathNet
PrintJapan Mathematical Olympiad
Japan counting and probability
Problem
On a square board, a number of tiles consisting of 4 squares, as shown in the figure, are placed along the grid. Note that the placed tiles may be rotated or flipped over. Furthermore, the placed tiles may be overlapped, but must not protrude beyond the board. Assume that every square of the board is covered with at most two tiles. Find the maximum possible number of squares of the board that are covered by at least one tile.
Solution
Consider the tile placement obtained by superposing the two given arrangements below. In this placement, each square of the board should be covered by at most two tiles. Furthermore, with the exception of the central square, each of the 24 remaining squares are covered by at least one tile.
Next, we will prove that the number of squares covered by at least one tile is no more than 24. Let us annotate some squares with the letters A and B as shown in the figure below. Then, no matter how a single tile is placed, exactly one square marked with A and exactly one square marked with B will be covered by the tile. Note that there are 4 squares marked with A. Since each square is covered by at most two tiles, the total number of tiles that can be placed is at most 8. Therefore, it is impossible to cover all of the 9 squares marked with B. Hence, the number of squares covered by at least one tile is or less.
With the above argument, we have proved that the maximum value in question is 24.
Next, we will prove that the number of squares covered by at least one tile is no more than 24. Let us annotate some squares with the letters A and B as shown in the figure below. Then, no matter how a single tile is placed, exactly one square marked with A and exactly one square marked with B will be covered by the tile. Note that there are 4 squares marked with A. Since each square is covered by at most two tiles, the total number of tiles that can be placed is at most 8. Therefore, it is impossible to cover all of the 9 squares marked with B. Hence, the number of squares covered by at least one tile is or less.
With the above argument, we have proved that the maximum value in question is 24.
Final answer
24
Techniques
Coloring schemes, extremal argumentsPigeonhole principle