Frosty the Snowman has a $\ell \times \ell$ square backyard. He plans to put all the Christmas presents delivered by Santa into the backyard. The presents prepared by Santa are packed in the shape of a square with variable sizes. Frosty does not know the number nor the sizes of the presents before he receives it, but he does know that the sum of areas of the presents is $n$. After he receives one present, he will put it into the backyard, and then Santa will give him another present. This process continues until all the presents are delivered to Frosty. Since Frosty is lazy, once the presents are put into the backyard, he will not move them anymore. Frosty hopes that all the presents can be put into the backyard without overlapping, therefore he will have to arrange them wisely. (a) Prove that if $\frac{\ell^2}{ 2} < n \le \ell^2$, there does not exist a strategy such that Frosty’s goal can always be achieved. (b) Prove that if $0 < n \le \frac{\ell^2}{ 4}$ , there exists a strategy such that Frosty’s goal can always be achieved.
Problem
Source: 2024 IGMO Christmas Edition #6 International Gamma Mathematical Olympiad
Tags: combinatorics
04.02.2025 00:11
In this solution, we refer to presents as boxes. a) WLOG let $\ell = 1$. Send $2$ boxes of length $\sqrt{\dfrac{n}{2}} > \dfrac{1}{2}$. It is well know that in a right triangle $ABC$ with $\angle ABC = 90^\circ$, the maximum side length of a square is formed by having one vertex of the square be $B$. Suppose that a box doesn't pass through the center of the yard. We are able to draw a line through the center of the yard not intersecting the box. Then, WLOG, let the box have a vertex on the yard. It is then easy to see from here that the box passes through the center of the yard, contradiction. The same goes for both boxes, so they intersect at the center of the yard. We are done. b) WLOG, let $\ell = 1$. Define the power of a block with area $A \le \dfrac{1}{4}$ as the unique integer $i$ s.t. $\left(\dfrac{1}{4}\right)^i \ge A > \left(\dfrac{1}{4}\right)^{i+1}$. Claim: Suppose that all boxes sent have side length $\dfrac{1}{2^k}$, where $k$ is a non-negative integer (and so they have power $k$). As long as the total area of the boxes isn't more than $1$, we can always place the boxes in the backyard. Proof: If a box of area $1$ is sent, we're trivially done, so assume all powers are positive integers. Define a partition of depth $k \ge 1$ to be a splitting of the yard into $4^k$ squares, each with side length $\dfrac{1}{2^k}$. For a partition of depth $k$, for a square $S$ with no boxes inside, define the height of that square as the minimum $k > i \ge 1$ s.t. for a partition with depth $k-i$, the square containing $S$ has a box in it. If $i$ doesn't exist, set $i = k$. Now, our strategy for a box with power $i$ is as such; take a partition of depth $i$, and place our box perfectly inside the square with minimum height (ties broken arbitrarily). Suppose that for a box of depth $i$, all squares are filled up already in our partition of depth $i$. Let $k$ be the maximum depth. If $i = k$, then the yard is already filled, so we're trivially done (as the area goes above $1$). Otherwise, note that by how we placed the boxes, we are able to group up the boxes of power $k$ into boxes of power $k-1$ (which may require us to add at most $3$ more boxes of power $k$). Continuing this for $k-1,k-2,\dots,i+1$, by adding at most $3$ boxes of power $i < r \le k$ for any $r$, we fill up the whole grid. But, note that the boxes we added have area less than $$\sum_{r=i+1}^\infty \dfrac{3}{4^r} = \dfrac{1}{4^i}.$$ This means that our box of power $i$ adds too much area, a contradiction. Now, to solve from here, assume the box we're given of power $i$ has side length $\dfrac{1}{2^i}$ (this at most quadruples the area). Use the same strategy as given in the claim, as the total area is at most $1$. We're done.