Maths Olympiad Prep

Library / /26 of 34

Geometry Difficulty 5.7 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Problem assumes that we remove 2(i1)2(i-1) squares if ini\leq n , and 2(2ni)2(2n-i) squares if i>ni>n .
Divide the entire board into 4 quadrants each containing n2n^2 unit squares.
First we note that the 22 squares on the center on each of the 44 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 nn is even, there are exactly (n4)/2(n-4)/2 unit squares which cannot be filled by the tiles and if nn is odd, there are exactly (n3)/2(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+...n1)=n(n1)/2(1 + 2+ 3 +... n-1) = n(n-1)/2
Let us consider the 2 cases for parity of nn :
Case1:nCase 1: n is even
for n=2n = 2 , it can be seen easily that we can use a maximum of 66 tiles.
for n4:n \ge 4:
Total number of squares that cannot be filled in each quadrant is: n(n1)/2+(n4)/2=(n24)/2n(n-1)/2 + (n-4)/2 = (n^2 - 4)/2
So total number of squares that cannot be filled on the entire board = 2(n24)2(n^2 - 4)
So total number of squares that CAN be filled completely by the tiles = 4n22(n24)=2n2+84n^2 - 2(n^2 - 4) = 2n^2 + 8
So the maximum number of tiles that can be used = (2n2+8)/2=n2+4(2n^2 + 8)/2 = n^2 + 4
Case2:nCase 2: n is odd
for n=1n = 1 , it can be seen easily that we can use a maximum of 22 tiles.
for n3:n \ge 3:
Total number of squares that cannot be filled in each quadrant is: n(n1)/2+(n3)/2=(n23)/2n(n-1)/2 + (n-3)/2 = (n^2 - 3)/2
So total number of squares that cannot be filled on the entire board = 2(n23)2(n^2 - 3)
So total number of squares that CAN be filled completely by the tiles = 4n22(n23)=2n2+64n^2 - 2(n^2 - 3) = 2n^2 + 6
So the maximum number of tiles that can be used = (2n2+6)/2=n2+3(2n^2 + 6)/2 = n^2 + 3
Kris17Kris17

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.