2006 JBMO Problems/Problem 4
Problem
Consider a board. From the th line we remove the central unit squares. What is the maximal number of rectangles and that can be placed on the obtained figure without overlapping or getting outside the board?
Solution
Problem assumes that we remove squares if , and squares if .
Divide the entire board into 4 quadrants each containing unit squares.
First we note that the squares on the center on each of the bordering lines of the board can always be completely covered by a single tile, so we can count in the first and last unit squares (which are diagonally opposite) of each quadrant as being filled in completely by a tile.
So in each quadrant we have:
if is even, there are exactly unit squares which cannot be filled by the tiles and if is odd, there are exactly unit squares which cannot be filled by the tiles.
Above can be seen by drawing a diagram and noticing that alternate columns have even and odd number of unit squares (leaving a unit square uncovered by tiles in odd numbered blocks of columns).
Also, note that the total number of unit squares which were removed from each quadrant =
Let us consider the 2 cases for parity of :
is even
for , it can be seen easily that we can use a maximum of tiles.
for
Total number of squares that cannot be filled in each quadrant is:
So total number of squares that cannot be filled on the entire board =
So total number of squares that CAN be filled completely by the tiles =
So the maximum number of tiles that can be used =
is odd
for , it can be seen easily that we can use a maximum of tiles.
for
Total number of squares that cannot be filled in each quadrant is:
So total number of squares that cannot be filled on the entire board =
So total number of squares that CAN be filled completely by the tiles =
So the maximum number of tiles that can be used =