Consider a rectangle whose lengths of sides are natural numbers. If someone places as many squares as possible, each with area $3$, inside of the given rectangle, such that the sides of the squares are parallel to the rectangle sides, then the maximal number of these squares fill exactly half of the area of the rectangle. Determine the dimensions of all rectangles with this property.
Problem
Source: JBMO 2011 Shortlist C7
Tags: JBMO, combinatorics, combinatorial geometry
expsaggaf
08.10.2024 20:33
I'm surprised no one has solved this yet, so I will share my solution.
Let the dimensions of the rectangle be $m \times n$, and WLOG $m \le n$.
Claim: The maximum amount of squares of area $3$ (side length $\sqrt 3$) that can be put in the rectangle is $\lfloor \frac{m}{\sqrt{3}} \rfloor \lfloor \frac{n}{\sqrt{3}} \rfloor$.
Proof: Let m = $a\sqrt3 + r_1$, and n = $b\sqrt3 + r_2$ $(a, b \in \mathbb{Z})$
Then we can fill the rectangle with $ab$ squares. Suppose FTSOC that there is space left for another square with area $3$. Then $a\sqrt3 + \sqrt3 \le m = a\sqrt3 + r_1$, absurd since $r_1 < \sqrt3$, so there is no space horizontally. The same goes for $b$ and $r_2$, so no space vertically either, which completes the proof.
By the conditions of the problem, we obtain that $3\lfloor \frac{m}{\sqrt{3}} \rfloor \lfloor \frac{n}{\sqrt{3}} \rfloor = \frac{mn}{2}$.
Then $2(m - \sqrt 3)(n - \sqrt 3) < mn$, or $mn + 6 < 2(m + n)\sqrt 3 < 4(m + n)$. Then $10 > (m - 4)(n - 4) \ge (m - 4)^2$ so $m \le 7$.
Case 1: $m = 1$
$\implies 0 = \frac{n}{2}$ which is absurd.
Case 2: $m = 2$
$\implies n = 3 \lfloor \frac{n}{\sqrt 3} \rfloor > (n - \sqrt 3)\sqrt 3$ or $3 > n(\sqrt 3 - 1) > \frac{n}{2}$ so $n < 6$
By testing $2 \le n < 6$ we obtain $n = 3$ as the only solution.
Case 3: $m = 3$
$\implies n = 2 \lfloor \frac{n}{\sqrt 3} \rfloor > (n - \sqrt 3) \times \frac{2}{\sqrt 3}$ or $2 > n \times (2\sqrt3 - 1) > 2n$, absurd.
Case 4: $m = 4$
$\implies n = 3\lfloor \frac{n}{\sqrt3} \rfloor$ so $4 \le n < 6$ which gives no solutions.
Case 5: $m = 5$
$\implies 5n = 12\lfloor\frac{n}{\sqrt3}\rfloor > (n - \sqrt3) \times 4\sqrt3$ or $12 > n \times (4\sqrt3 - 5) > \frac{3n}{2}$ or $n > 8$
By testing $5 \le n < 8$ we obtain no solutions.
Case 6: $m = 6$
$\implies 3\lfloor \frac{n}{\sqrt3} \rfloor = n$ so $6 \le n < 6$, absurd.
Case 7: $m = 7$
$\implies 10 > 3(n - 4)$ or $n < \frac{22}{3}$ so $n = 7$ which isn't a solution.
Therefore, the only rectangles that satisfy the property are $2 \times 3$ and $3 \times 2$ rectangles.
YaoAOPS
08.10.2024 20:43
I think you also need a local argument to show that a grid packing of squares is optimal.
expsaggaf
08.10.2024 20:55
I think the edited argument is now stronger and suffices.