Browse · MathNet
PrintChina Girls' Mathematical Olympiad
China counting and probability
Problem
When the unit squares at the four corners are removed from a three by three square, the resulting shape is called a cross. What is the maximum number of non-overlapping crosses placed within the boundary of a chessboard? (Each cross covers exactly five unit squares on the board.) (posed by Feng Zuming)
Solution
The centers of the crosses (denoted by ) must lie in the subboard in the middle. We tile this central board by three boards, and label these three boards (a), (b) and (c), from left to right. We consider the number of centers placed in the three boards.
Note that we can place at most two centers on each subboard;
We can tile a board one board sandwiched by two boards. Hence we can place at most centers on a board, with each two centers placed on each subboard. Since there are two centers placed in the middle subboard, no centers can be placed in the third and sixth row of the board. We can only have the following two symmetric distributions.
Case I Board (b) has centers. By symmetry, we can assume that the following scheme for placing the centers (see left-hand side diagram in the following figure). It is not difficult to see that no centers can be placed on the third and the seventh columns of the board. Then it is easy to see that we can place at most centers in board (a) or (c), which implies that we can place at most centers on the board. It contradicts the assumption.
Case II Both boards (a) and (c) have six centers. By symmetry, we discuss with the right-hand side diagram in the following figure. In this case there is no centers can be placed in the fourth and the sixth columns of the board, which implies that board (b) can hold at most centers, and so the board can hold at most centers, which is again a contradiction.
Case III Exactly one of the boards (a) and (c) has six centers. In this case we assume that (a) contains centers and board (c) contains at most centers. Then no center can be placed in the fourth column of the board. It follows that board (b) contains at most centers. Hence there are at most centers on the board, which is again a contradiction.
Combining the above argument, we conclude that it is impossible to place centers on a board.
We complete our solution by providing two different ways to place centers on the board.
or
Note that we can place at most two centers on each subboard;
We can tile a board one board sandwiched by two boards. Hence we can place at most centers on a board, with each two centers placed on each subboard. Since there are two centers placed in the middle subboard, no centers can be placed in the third and sixth row of the board. We can only have the following two symmetric distributions.
Case I Board (b) has centers. By symmetry, we can assume that the following scheme for placing the centers (see left-hand side diagram in the following figure). It is not difficult to see that no centers can be placed on the third and the seventh columns of the board. Then it is easy to see that we can place at most centers in board (a) or (c), which implies that we can place at most centers on the board. It contradicts the assumption.
Case II Both boards (a) and (c) have six centers. By symmetry, we discuss with the right-hand side diagram in the following figure. In this case there is no centers can be placed in the fourth and the sixth columns of the board, which implies that board (b) can hold at most centers, and so the board can hold at most centers, which is again a contradiction.
Case III Exactly one of the boards (a) and (c) has six centers. In this case we assume that (a) contains centers and board (c) contains at most centers. Then no center can be placed in the fourth column of the board. It follows that board (b) contains at most centers. Hence there are at most centers on the board, which is again a contradiction.
Combining the above argument, we conclude that it is impossible to place centers on a board.
We complete our solution by providing two different ways to place centers on the board.
or
Final answer
15
Techniques
Coloring schemes, extremal argumentsPigeonhole principle