Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2006 JBMO Problems/Problem 4

Revision as of 11:16, 31 December 2018 by KRIS17 (talk | contribs) (Created page with "==Problem== Consider a <math>2n \times 2n</math> board. From the <math>i</math>th line we remove the central <math>2(i-1)</math> unit squares. What is the maximal number of r...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_JBMO_Problems/Problem_4&oldid=99912"