Given some square carpets with the total area 4.
Prove that they can fully cover the unit square.
From : Vasil'ev N.B, Egorov A.A. "The problems of the AllSovietUnion
mathematical competitions",Moscow.:Nauka. 1988 ISBN 5020137308.
Thanks to Vladimir A. Pertsel
                                   
From  Tue Jul 14 20:35:07 1998
From: Dean Hickerson
Newsgroups: rec.puzzles
Subject: Re: Some square carpets
Date: 13 Jul 1998 21:40:03 GMT
Organization: University of California, Davis
Laurent Morel wrote:
> Given some square carpets with the total area 4.
> Prove that they can fully cover the unit square.
If some carpet has side length >= 1, we're done, so assume that all
sides are < 1.
For each of the given squares, reduce the side length to the largest
length of the form 1/2^n with n >= 1 that's less than or equal to
the given length. E.g. squares with sides >= 1/2 and < 1 get
reduced to squares of side 1/2. If we can cover the unit square with
the reduced carpets, we can do so with the original ones.
Note that the area of each reduced square is more than 1/4 of the area
of the original, so the total area of the reduced squares is more than 1.
If we have 4 or more squares of side 1/2^n with n >= 1, glue 4 of
them together to form a square of side 1/2^(n1). Repeat this process
as often as possible. If at some point we form a square of side 1, we're
done. If not, then we end up with at most 3 squares of side 1/2, at
most 3 of side 1/4, at most 3 of side 1/8, and so on, for a total area
of at most
3 3 3 3
 +  +  +  + ... = 1.
4 2 3 4
4 4 4
This contradicts the fact that the total area is more than 1.
A followup question, to which I don't know the answer: What's the
smallest number that can replace 4 in the original problem? There are
two versions of this, depending on whether the carpets can be rotated or
are required to have sides parallel to those of the unit square.
Dean Hickerson
dean@math.ucdavis.edu
                                   
From  Sat Jul 25 18:48:44 1998
Newsgroups: rec.puzzles
From: wald@ford.uchicago.edu (Kevin Wald)
Subject: Re: Some square carpets
Organization: Dept. of Mathematics
Date: Thu, 23 Jul 1998 10:04:34 GMT
Dean Hickerson wrote:
> Laurent Morel wrote:
>> Given some square carpets with the total area 4.
>> Prove that they can fully cover the unit square.
[After a proof of this statement, which I have omitted here, though
I refer to it later on:]
> A followup question, to which I don't know the answer: What's the
> smallest number that can replace 4 in the original problem? There are
> two versions of this, depending on whether the carpets can be rotated or
> are required to have sides parallel to those of the unit square.
I've got an answer to the parallelsides version of this followup question.
I'll give the answer itself after twentyodd lines of spoiler space, and
then the proof after additional spoiler space.
*SPOILER*
c
o
m
i
n
g
i
n
t
w
e
n
t
y

o
d
d
l
i
n
e
s
The smallest number that can replace 4 in the parallelsides version
of this problem is 3.
*SPOILER* for the proof
c
o
m
i
n
g
i
n
t
w
e
n
t
y

o
d
d
l
i
n
e
s
Proof:
First of all, it's clear that no number less than 3 can be substituted,
if the sides of the carpet squares are required to be parallel to the
sides of the unit square. For if we try substituting some k < 3, then
consider three equal carpet squares, each of area k/3 < 1. Each will
have a side length < 1, and thus can reach at most one of the four corners
of the unit square. Since there are only three carpet squares, then,
one corner of the unit square (and a small area around it) will always
be uncovered.
The proof that 3 does work is, in many respects, similar to the one
Dean Hickerson gave for 4, so I'll refer to that from time to time.
First of all, as before:
> If some carpet has side length >= 1, we're done, so assume that all
> sides are < 1.
Next, in the proof for 4, we had:
> For each of the given squares, reduce the side length to the largest
> length of the form 1/2^n with n >= 1 that's less than or equal to
> the given length. E.g. squares with sides >= 1/2 and < 1 get
> reduced to squares of side 1/2. If we can cover the unit square with
> the reduced carpets, we can do so with the original ones.
In this new proof, we reduce the carpets slightly differently; the
reduced version of a carpet will be the largest rectangle with sides
of the form 1/(sqrt(2))^n and 1/(sqrt(2))^(n+1) that will fit inside
it. (That is, the possible rectangles are 1/(sqrt(2)) by 1/2,
1/2 by 1/(2sqrt(2)), 1/(2sqrt(2)) by 1/4, and so on.)
We now must distinguish two cases:
(A) There are two or fewer 1/(sqrt(2))by1/2 rectangles among
the reduced carpets.
(B) There are at least three 1/(sqrt(2))by1/2 rectangles among
the reduced carpets.
In case (A), we continue with a proof like the proof for 4. There,
we had:
> Note that the area of each reduced square is more than 1/4 of the area
> of the original, so the total area of the reduced squares is more than 1.
In the new version, the area of each reduced carpet is more than
1/(2sqrt(2)) of the original, so the total area of the reduced carpets
is more than 3/(2sqrt(2)).
Now, consider a 1by3/(2sqrt(2)) rectangle (call it R); since
3/(2sqrt(2)) > 1, if we can cover such a rectangle we can cover the
unit square. Divide R into six 1/2by1/(2sqrt(2)) subrectangles.
Place the 1/(sqrt(2))by1/2 reduced carpets (if any) so as to cover two
of these subrectangles apiece. (Note that because of the arrangement
of the subrectangles, at most two carpets can be so placed; that's why
we have to deal with case (B) in a different way.)
This leaves some number of 1/2by1/(2sqrt(2)) subrectangles left over.
We cover as many of them as possible with whatever 1/2by1/(2sqrt(2))
reduced carpets we have. If we cover all of them, we have covered R, and
we are done; otherwise, divide the remaining 1/2by1/(2sqrt(2))
subrectangles into two 1/(2sqrt(2))by1/4 subsubrectangles apiece,
and cover as many of these as possible with whatever 1/(2sqrt(2))by1/4
reduced carpets we have. If that doesn't cover all of them, we divide
the remaining subsubrectangles in half again, and so on. At some stage of
this procedure we must succeed in covering all of R; for otherwise, we
will have fit all of our reduced carpets (total area > 3/(2sqrt(2))) into
R (total area = 3/(2sqrt(2)). Thus, since we can cover R, we can cover
the unit square.
(This argument is basically a variant of the glueingtogether argument
from the proof for 4, written backwards, with shapes that glue together
in pairs instead of quartets, and a little bit of added complication.)
In Case (B), we have at least three 1/(sqrt(2))by1/2 reduced carpets.
We must thus have, among our original carpet squares, at least three
with side length > 1/(sqrt(2)). Call them, in decreasing order of size,
S1, S2, and S3. Then if we put S3 in the lower lefthand corner of
our unit square, S1 in the upper lefthand corner, and S2 in the
upper righthand corner, all that will remain uncovered will be a
small rectangle in the upper righthand corner. Let x be 1 minus
the length of S2's side; then the uncovered corner will have sides
x and something <= x, and so will fit within an xbyx square. It can
thus be covered by any collection of carpet squares of area >= 4x^2.
Now, S1 has area < 1, S2 has area (1  x)^2, and S3 has area <= the
area of S2, so the total area of all three is < 1 + 2(1  2x + x^2)
= 3  (4x  2x^2). Thus, the area of the remaining carpet squares
is greater than 4x  2x^2. Since the length of S2's side > 1/(sqrt(2)),
x < 1  1/(sqrt(2)) < 1/3, so x = (1/3)(3x) > (x)(3x) = 3x^2. Thus,
the area of the remaining carpet squares > 4(3x^2)  2x^2 = 10x^2,
which is certainly >= 4x^2. Thus, the remaining carpet squares will
cover the remaining corner, and the entire unit square thus will
have been covered.
Kevin Wald, wald@math.uchicago.edu  "Catalog of ships  I'll remember that."
http://www.math.uchicago.edu/~wald   Homer, _The Huntress and the Sphinx_
                                   
Title: A Covering Problem
Given any collection of squares with total area 3, prove that they can
cover the unit square. If the sides of the covering squares are all to
be parallel to the sides of the unit square, then 3 is best possible.
For the analogous problem with hypercubes in E^n, 3 is replaced by 2^n1.
Journal: SIAM Review
Publisher: Society for Industrial and Applied Mathematics
volume(year)page references:
Proposal: 24(1982)77 by D. J. Newman
Solution: 25(1983)99 by A. Meir
Comment: 25(1983)100 by Andr\'as Bezdek and K\'aroly Bezdek
Additional solvers listed: 26(1984)283