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.

According to Arthur Engel, "Problem Solving Strategies", this problem goes back to Erdős, but I cannot find the solution:

Let $A$ and $B$ be two non-overlapping squares inside a unit square, of side lengths $a$ and $b$, respectively. Prove that $$a+b \le 1.$$

EDIT: Since this question received an ingenious answer, I asked a new question regarding the sum of the perimeters of five squares (the cases of 3 or 4 squares are now trivial). Maybe someone of you knows how to proceed in this case.

share|improve this question
1  
This paper may be of interest. –  EuYu Nov 25 '12 at 21:55
1  
@EuYu "It is not hard to see that $f(2) = 1$." That's all your link has to say, at least to someone like me who can't see past the first page. As to an answer, I believe the trick is in showing that, fixing the position of $A$, a square the size of $B$ can be put in one of the corners of the unit square without overlapping with $A$. From there you can assume wlog that both squares rest squarely in some corner of the unit square, and the result follows. –  Arthur Nov 25 '12 at 22:44
1  
Perhaps math.ucsd.edu/~ronspubs/75_06_squares.pdf is not behind a paywall. –  Gerry Myerson Nov 25 '12 at 23:44
4  
Even with full access, I'm afraid there isn't much more. The authors list the results for $f(2),\ f(3),\ f(5),\ f(6)$ and $f(7)$, state that the results can be shown with little difficulty and move on. I've emailed the authors about the claim, hopefully I'll hear back from them soon. –  EuYu Nov 26 '12 at 0:20
3  
Well, I got a response. "I think we must have been referring to the version of the question where the sides of the tiles are parallel to the sides of the unit square. I remember that for f(2) and f(3) it was helpful to look at the center point of the square. If no tile covers it, then all tiles must have side length less than 1/2. If a tile with side s does cover it, the remaining tiles can have sides no larger than 1-s. I'll have to think about what happens for 5,6 and 7. I'll let you know if I figure it out. As far as I know, this problem is still open. Good luck with it." –  EuYu Nov 28 '12 at 8:49

4 Answers 4

up vote 24 down vote accepted

Given two nonoverlapping squares in a large square $Q$ there is a line $g$ separating the two squares. Assume $g$ is not parallel to one of the sides of $Q$ (otherwise we are done). Let $A$ and $C$ be the two vertices of $Q$ farthest away from $g$ on the two sides of $g$. The two edges of $Q$ meeting at $A$ together with $g$ determine a rightangled triangle $T_A$, and similarly we get a rightangled triangle $T_C$; see the following figure. (One could draw a second figure where $g$ cuts off just one vertex $A$. The proof remains the same.)

enter image description here

To finish the proof we need the following

Lemma. Given a triangle $T_C$ with a right angle at $C$ the largest square inscribed in $T$ is the square with one vertex at $C$ and one vertex at the intersection of the angle bisector at $C$ with the hypotenuse of $T$.

Sketch of proof of the Lemma:

Put $C$ at the origin of the $(x,y)$-plane, and let $(a,0)$, $(0,b)$ be the other two vertices of $T$. We may assume two vertices of the inscribed square on the legs of $T$. If $(u,0)$ and $(0,v)$ are these two vertices the other two vertices are $(u+v,u)$ and $(v,u+v)$. It follows that $u$ and $v$ have to satisfy the conditions $$u\geq0, \quad v\geq 0,\quad {u+v\over a}+{u\over b}\leq 1,\quad {v\over a}+{u+v\over b}\leq 1\ .$$ These four conditions define a convex quadrilateral $P$ in the "abstract" $(u,v)$-plane. The vertices of $P$ are $$V_1=(0,0),\quad V_2=\Bigl({ab\over a+b},0\Bigr),\quad V_3=\Bigl({a^2b\over a^2+ab +b^2},{ab^2\over a^2+ab +b^2}\Bigr), \quad V_4=\Bigl(0,{ab\over a+b}\Bigr)\ .$$ Computation shows that $$|V_2|^2-|V_3|^2={a^4 b^4 \over(a+b)^2(a^2+ab+b^2)^2}>0\ .$$

Therefore $u^2+v^2$ ($=$ the square of the side length of our square) is maximal at the two vertices $V_2$ and $V_4$ of $P$, which correspond to the statement of the Lemma.

share|improve this answer
2  
Excellent! I would upvote it again if I could. –  TonyK Nov 28 '12 at 14:05

So, assume that $0 \leq a \leq 1$ and $0\leq b\leq 1$. I'll address the boundary conditions later.[1] You have square A, inside of a unit square. When the square A is touching a corner, you have the most space available for square B.[2] Assuming that the square is touching a corner, you are left with two rectangles of space of size $(1-a)$ X 1. (With the understanding that these two rectangles of space overlap.) Now, a square is restricted in size by the smaller of the two dimensions, so the max size for $b$ is $(1-a)$, or:

$0 \leq b \leq (1-a) \leq 1 \Rightarrow [\text{add $a$ to everything}] \Rightarrow$
$a \leq b+a \leq 1 < 1+a \Rightarrow$
[removing the terms on the ends gives us a weaker statement]
$b+a \leq 1$

[1] So, lets take the two edge cases first:
1) $a=1$: If a=1, a takes up all the room in the square. Honestly, I don't know my definitions well know to know if a square B can exist in zero space, with a length of zero size. You have to prove this, to prove the statement is correct.
2) $a=0$: Square B can fit in the box, and be any size 0<b<=1, but again, I don't remember my geometry well enough to know if you can have a square of zero size.

[2] If you want to prove that the corner is optimal, for allowing the biggest rectangles, and squares, you can prove it by finding an expressing for the free space on each side of a square, based on the square's position, and assuming the size is a constant C. Then you can show the free space is maximized then the position of the square is in a corner.

Edit: This is harder to prove than originally stated, because it neglects to account for what happens if the rectangles are rotated.

share|improve this answer
2  
Proving that the corner is optimal is what makes this problem hard! –  TonyK Nov 28 '12 at 9:08
    
These forums are a great place to practise writing fomulas etc in Latex. You could edit your answer quite simply if you wanted... –  Simon Hayward Nov 28 '12 at 9:10
    
@TonyK Agreed. I thought it was easy, but I forgot that the squares can be rotated which makes things more complicated, so this is more like half an answer. –  Patrick M Nov 28 '12 at 9:38

For the "square in triangle" subproblem, I think the solution always looks like test

where $0 \leq a \leq b$. If $a > b$, then just flip the figure around the $x=y$ line.

With the notations in the figure (if you don't like them, you can file a complaint), we have $t = s(\cos a + \sin a + \cos a / \tan b)$ so we have to minimize $f(a) = \sin a + (1 + 1 / \tan b) \cos a$.

Analyzing the derivative, I found that the function is increasing up to $\tan a = 1 / (1 + 1 / \tan b)$ and then decreasing, so the minimum is at one of the extremes: $a = 0$ or $a = b$

We get $f(0) = 1 + 1 / \tan b = (\sin b + \cos b) / \sin b$ and $f(b) = \sin b + \cos b + \cos^2b / \sin b = (1 + \sin b \cos b) / \sin b$.

Since $0 < \sin b$, $\cos b < 1$, we have $(1 - \sin b)(1 - \cos b) / \sin b > 0$ therefore $f(0) < f(b)$ so we get the biggest square for $a = 0$.

share|improve this answer

Another way of solving this problem is with bounding boxes. A bounding box is the minimum rectangle containing a shape orthogonal to two chosen axes. Consider the bounding boxes of the two squares A and B orthogonal to the main square Q. In each case, the remaining space makes four right angled triangles. Call them the waste triangles.

Now you need two lemmas.

  1. Given two non-overlapping squares A' and B', A' either doesn't intersect the bounding box of B', or it does so only in one of the waste triangles. Proof: assume that there is an intersection in more than one triangle. Draw a line between the two points in the two distinct triangles. This line intersects B' at some point. But by convexity of the square, this point must also be in A'. Which is impossible. And we're done.

  2. A square can always be placed in the corner of its bounding box so that it does not intersect the triangle at the opposite corner. For this, use algebra and express everything in terms of the two non-hypotenuse sides of the waste triangle. The bottom left corner of the bounding box is the origin, so all squares in this corner have their top-right corner along the line x = y. The intersection of this line and the line formed by the hypotenuse of the top-right waste triangle gives a value of x that is bigger than the side of the square. And so we're done.

Now we're ready for the main proof. Take the square A. We can always put it into some corner of its bounding box by our two lemmas. Do this. Repeat the process for B. Now we have two squares orthogonal to the main square. Showing that the sides add up to at most 1 is now trivial.


Proof of Lemma 2: We look for the intersection of the diagonal $x = y$ with the line extended from the hypotenuse of the top-right triangle. That is, the green and red lines from the image below:

enter image description here

Now the equation of the red line is $y = -(\frac{a}{b})x + c$ for some $c$.

To find this c, we just use the fact that that value of $y$ at $x = a$ for the red line is $a + b$. Putting this into the equation we get: $ a + b = -(\frac{a^2}{b}) + c$. From here we get $ c = (\frac{a^2 + b^2 + ab}{b})$. So the equation of our line becomes: $y = -(\frac{a}{b})x + \frac{a^2 + b^2 + ab}{b}$. Intersecting with the line $x = y$, the green line, we get: $x = -(\frac{a}{b})x + \frac{a^2 + b^2 + ab}{b}$, and after some algebraic manipulation, this works out as: $x = \frac{a^2 + b^2 + ab}{a + b}$.

At this point, it's good to reiterate the meaning of $x$. This is the size of the largest square that fits orthogonally into the bottom left corner of the black bounding box without intersecting the top-right waste triangle. Equivalently, it is the largest such square that doesn't intersect the red line. All we have now to prove, to show that the blue square can be placed in this corner, is that the side of the blue square is less than or equal $x$. So our goal is to solve the inequality:

$\sqrt{a^2 + b^2} \leq x$

Substitute our term for $x$:

$\sqrt{a^2 + b^2} \leq \frac{a^2 + b^2 + ab}{a + b}$

Positive terms allows squaring both sides:

$a^2 + b^2 \leq \frac{(a^2 + b^2 + ab)^2}{(a + b)^2} \equiv$ $(a^2 + b^2)(a + b)^2 \leq (a^2 + b^2 + ab)^2$

Now let $u = a^2 + b^2$ yielding:

$u(a + b)^2 \leq (u + ab)^2$

Now multiply it all out:

$ua^2 + ub^2 + 2uab \leq u^2 + a^2b^2 + 2uab \equiv$ $ua^2 + ub^2 \leq u^2 + a^2b^2$

And plug back in our term for $u$ getting:

$a^4 + 2a^2b^2 + b^4 \leq a^4 + b^4 + 2a^2b^2 + a^2b^2 \equiv$ $0 \leq a^2b^2$

Which is clearly true. And we're done proving the lemma.

share|improve this answer

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.