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 All-Soviet-Union mathematical competitions",-Moscow.:Nauka. 1988 ISBN 5-02-013730-8. 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^(n-1). 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 parallel-sides version of this followup question. I'll give the answer itself after twenty-odd 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 parallel-sides 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))-by-1/2 rectangles among the reduced carpets. (B) There are at least three 1/(sqrt(2))-by-1/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 1-by-3/(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/2-by-1/(2sqrt(2)) subrectangles. Place the 1/(sqrt(2))-by-1/2 reduced carpets (if any) so as to cover two of these sub-rectangles 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/2-by-1/(2sqrt(2)) subrectangles left over. We cover as many of them as possible with whatever 1/2-by-1/(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/2-by-1/(2sqrt(2)) subrectangles into two 1/(2sqrt(2))-by-1/4 subsubrectangles apiece, and cover as many of these as possible with whatever 1/(2sqrt(2))-by-1/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 glueing-together 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))-by-1/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 left-hand corner of our unit square, S1 in the upper left-hand corner, and S2 in the upper right-hand corner, all that will remain uncovered will be a small rectangle in the upper right-hand 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 x-by-x 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^n-1. 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