2006 JBMO Problems/Problem 4

Problem

Consider a $2n \times 2n$ board. From the $i$th line we remove the central $2(i-1)$ unit squares. What is the maximal number of rectangles $2 \times 1$ and $1 \times 2$ that can be placed on the obtained figure without overlapping or getting outside the board?


Solution

Problem assumes that we remove $2(i-1)$ squares if $i\leq n$, and $2(2n-i)$ squares if $i>n$.

Divide the entire board into 4 quadrants each containing $n^2$ unit squares.

First we note that the $2$ squares on the center on each of the $4$ 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 $n$ is even, there are exactly $(n-4)/2$ unit squares which cannot be filled by the tiles and if $n$ is odd, there are exactly $(n-3)/2$ 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 = $(1 + 2+ 3 +... n-1) = n(n-1)/2$

Let us consider the 2 cases for parity of $n$:


$Case 1: n$ is even

for $n = 2$, it can be seen easily that we can use a maximum of $6$ tiles.

for $n \ge 4:$

Total number of squares that cannot be filled in each quadrant is: $n(n-1)/2 + (n-4)/2 = (n^2 - 4)/2$

So total number of squares that cannot be filled on the entire board = $2(n^2 - 4)$

So total number of squares that CAN be filled completely by the tiles = $4n^2 - 2(n^2 - 4) = 2n^2 + 8$

So the maximum number of tiles that can be used = $(2n^2 + 8)/2 = n^2 + 4$


$Case 2: n$ is odd

for $n = 1$, it can be seen easily that we can use a maximum of $2$ tiles.

for $n \ge 3:$

Total number of squares that cannot be filled in each quadrant is: $n(n-1)/2 + (n-3)/2 = (n^2 - 3)/2$

So total number of squares that cannot be filled on the entire board = $2(n^2 - 3)$

So total number of squares that CAN be filled completely by the tiles = $4n^2 - 2(n^2 - 3) = 2n^2 + 6$

So the maximum number of tiles that can be used = $(2n^2 + 6)/2 = n^2 + 3$


$Kris17$