# combinatorial geometry: covering a square

I'm stuck with this problem. can anyone help me?

A finite collection of squares has total area 4. show that they can be arranged to cover a square of side 1.

-
Square overlapping is allowed, right ? If, for exemple, you have 21 small squares with areas $a_1,a_2, \ldots ,a_{21}$ given by $a_k=\frac{19}{105}+\frac{k-1}{1050}$, then all the $a_k$'s are different and smaller than $a_{21}=\frac{1}{5}$, so if we cover a unit square with those small squares, some small squares will necessarily overlap. – Ewan Delanoy Nov 20 '11 at 17:16
yes, overlapping is allowed. – Goodarz Mehr Nov 20 '11 at 17:37

Here's a proof using the following simple combinatorial

Lemma. Let a positive integer $k$ and a nonempty finite multiset $P$ of powers $k^i$ with $i\in\mathbf{Z}$ be given. Put $s=\sum P$, the sum of all the powers, and $k^m$ the greatest power occurring in $P$; let the integer $q>0$ be such that $s\geq qk^m$. Then there exists a partition of a sub-multiset of $P$ into $q$ parts each of sum exactly $k^m$.

(Finding a decent formulation is more difficult here than finding a proof.) One can obviously take $q$ the quotient of the Euclidean division of $s$ by $k^m$, but for the proof it will be convenient to have a bit more freedom. The condition for a collection of multisets of being a partition of a sub-multiset of $P$ is what the terminology suggests: it just means that for any element, the sum of its multiplicities of occurrence in members of the collection is no more than its multiplicity of occurrence in $P$.

Proof. By induction on the number $n\geq1$ of elements in $P$. Split off from $P$ the singleton $\{k^m\}$ of its greatest element, which will be one part of the partition sought, leaving a remainder $P'$. If $q=1$, then the one-part partition $\{k^m\}$ is a solution. In the remaining case one certainly has $n>1$, so $P'$ is non-empty; let $k^{m'}$ be the greatest element of $P'$, with obviously $m'\leq m$. Applying the induction hypothesis to $P'$ and $q'=(q-1)\,k^{m-m'}$, one obtains a partition of a sub-multiset of $P'$ into $q'$ parts each of sum $k^{m'}$. Grouping them together $k^{m-m'}$ at a time (in an arbitrary way) provides a partition of the same sub-multiset of $P'$ into $q-1$ parts, which together with $\{k^m\}$ give a solution. QED

Now for the problem of the squares, round the lengths of their sides down, each to a (probably negative) integer power of $2$. Each square will certainly cover a square of the rounded-down size, and replacing the collection by the so rounded-down squares gives a multiset of squares whose total area is greater than a quarter of the original area, that is greater than 1. Excluding the trivial case of a single square of area $4$, the largest square has size $2^{-l}$ with $l\in\mathbf{N}$. Apply the lemma with $k=4$, the multiset of the areas of the rounded-down squares, and $q=4^l\in\mathbf{N}$. This provides a partition of a sub-multiset of the squares into $q$ parts, each of which parts will cover one of the $q$ squares of the $2^l\times2^l$ subdivision of the unit square. (One needs to check that the regrouping of $4^{m-m'}$ multisets done in the proof of the lemma can be realised geometrically, but this is obvious by a similar $2^{m-m'}\times2^{m-m'}$ subdivision.)

-
"...the greatest power occurring in S" - what is S? Did you mean P? – Erel Segal-Halevi May 19 '13 at 10:30
@ErelSegalHalevi Yes, thank you. Corrected now. – Marc van Leeuwen May 19 '13 at 10:38