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

3 Answers 3

up vote 23 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

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.