Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
yes, overlapping is allowed. –  Goodarz Mehr Nov 20 '11 at 17:37
add comment

1 Answer 1

up vote 7 down vote accepted

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.)

share|improve this answer
    
"...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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.