15
$\begingroup$

One of my colleagues gave me the following problem about 15 years ago:

Given three squares inside a 1 by 2 rectangle, with no two squares overlapping, prove that the sum of side lengths is at most 2. (The sides of the squares and the rectangle need not be parallel to each other.)

I couldn't find a solution or even a source for this problem. Does anyone know about it? I was told that this was like an exercise in combinatorial geometry for high school contests such as IMO, but I'm not sure if this problem was listed in such competitions. Has anyone heard of this problem, or does anyone know how to solve it?

Any kind of help will be appreciated.

$\endgroup$
7
  • 1
    $\begingroup$ So you have three squares of sides $a,b,c$ and want to show $a+b+c\le 2$ you know from the conditions that the sum of the areas is at most $2.$ Also, each of $a,b,c$ is at most $1.$ work with that. $\endgroup$ Commented Jul 4, 2021 at 13:41
  • 6
    $\begingroup$ @AaronMeyerowitz, that only proves that $a+b+c\le \sqrt{6}$; e.g. you can have $a=b=c=\sqrt{2/3}$. $\endgroup$
    – user44143
    Commented Jul 4, 2021 at 13:44
  • 1
    $\begingroup$ This area approach corresponds to partitioning a circle of radius $\sqrt{2/\pi}$ into three congruent circular sectors. Somehow the actual shapes need to be considered. Since two unit squares side by side achieve $a+b+c=2$, maybe condition on whether the central vertical line is crossed by some square. $\endgroup$
    – RobPratt
    Commented Jul 4, 2021 at 14:22
  • 2
    $\begingroup$ @JuanMoreno you are supposed to sum the three side lengths, not all twelve sides. $\endgroup$
    – RobPratt
    Commented Jul 4, 2021 at 21:15
  • 5
    $\begingroup$ More generally, what is the maximum sum of side lengths of $n$ squares in a $1\times x$ rectangle, for any real number $x>1$? $\endgroup$ Commented Jul 4, 2021 at 23:33

2 Answers 2

5
$\begingroup$

Since the squares are convex, we can draw lines which separate them. In particular, if two separating lines go from $(b-a,0)$ to $(b,1)$ and from $(c,1)$ to $(c+d,0)$, then we can prove the result in terms of those lines and those variables.

So: let the rectangle go from $(0,0)$ to $(2,1)$. Let $A$ be the leftmost square (or one such square). Let $C$ be the rightmost square (or one such square). Let $B$ be the other square.

Draw a line separating $A$ and $B$, and let $(b,1)$ and $(b-a,0)$ be its intersections with the lines $y=1$ and $y=0$.

Draw a line separating $B$ and $C$, and let $(c,1)$ and $(c+d,0)$ be its intersections with the lines $y=1$ and $y=0$.

Reasoning as in user21820's answer, we assume wlog that:

  • $0<a$, so $A$ is left and above the line separating $A$ and $B$;
  • $0<d$, so $C$ is right and above the line separating $B$ and $C$;
  • $0<b$ and $c<2$ and $a-b+c+d>0$, so $B$ is below both lines.

(Since the lines may leave the rectangle, we do not assume $b-a>0$ or $b<2$ or $c>0$ or $c+d<2$.)

Lemma (proved at the end): \begin{align} \text{sidelength of }A &\le \min\!\left(\frac{b}{a+1},\,1\right)\\ \text{sidelength of }B &\le \min\!\left((a-b+c+d)u,\,1\right)\\ \text{sidelength of }C &\le \min\!\left(\frac{2-c}{d+1},\,1\right) \end{align} where $$u=\max\left( \frac{1}{a+d+1}, \frac{\sqrt{a^2+1}}{a^2+a+d+1}, \frac{\sqrt{d^2+1}}{d^2+d+a+1} \right)$$

The factor $u$ satisfies $1/(a+1)>u$ and $1/(d+1)>u$ so long as $a<3.66$ and $d<3.66$ respectively. I will assume those inequalities for now to show that some functions are increasing or decreasing; I don't have a clean proof for those inequalities or without them yet.

In the corner case of $b=a+1$ and $c=1-d$, the side lengths are $1$, $0$ and $1$, and they sum to exactly $2$. We now use this in analyzing four cases.

Case I, $b\le a+1$ and $c\le 1-d$: The sum of the sidelengths is at most $$\frac{b}{a+1}+(a-b+c+d)u+1$$ This is increasing in both $b$ and $c$, so its value is at most the corner value of $2$.

Case II, $b\le a+1$ and $c\ge 1-d$: The sum of the sidelengths is at most $$\frac{b}{a+1}+(a-b+c+d)u+\frac{2-c}{d+1}$$ This is increasing in $b$ and decreasing in $c$, so its value is at most the corner value of $2$.

Case III, $b\ge a+1$ and $c\le 1-d$: The sum of the sidelengths is at most $$1+(a-b+c+d)u+1$$ This is decreasing in $b$ and increasing in $c$, so its value is at most the corner value of $2$.

Case IV, $b\ge a+1$ and $c\ge 1-d$: The sum of the sidelengths is at most $$1+(a-b+c+d)u+\frac{2-c}{d+1}$$ This is decreasing in both $b$ and $c$, so its value is at most the corner value of $2$.

So the sum of the sidelengths is at most $2$ in each case.

Proof of Lemma:

The sidelength of $A$ is clearly less than 1, and also clearly less than the maximum sidelength inscribed in the right triangle bounded by $x=0$, $y=1$, and the separator of $A$ and $B$. We use Polya's formula here to calculate the sidelength in the triangle as the maximum of $b/(a+1)$ and $b\sqrt{a^2+1}/(a^2+a+1)$; since $a>0$, the maximum is just $b/(a+1)$.

A similar use of Polya's result bounds the sidelength of $C$. Yet another use of that result, now for a triangle which may be acute or obtuse, bounds the sidelength of $B$ by $|a-b+c+d|u$. Since we assumed $a-b+c+d>0$, we write this bound as $(a-b+c+d)u$.

$\endgroup$
6
  • 2
    $\begingroup$ "Since the squares are convex, we can draw lines which separate them": really? $\endgroup$ Commented Jul 6, 2021 at 9:28
  • $\begingroup$ Yes: this is the hyperplane separation theorem. en.wikipedia.org/wiki/Hyperplane_separation_theorem $\endgroup$
    – user44143
    Commented Jul 6, 2021 at 9:31
  • $\begingroup$ I don't think you understood @AndréHenriques's objection: i.sstatic.net/TzoUd.png $\endgroup$
    – user21820
    Commented Jul 6, 2021 at 10:46
  • 1
    $\begingroup$ @user21820, this does not assume that the lines go from top to bottom in the rectangle — that is why $a,b,c,d$ are defined in terms of intersections with lines instead of line segments, and why I noted that $b-a$ may be negative. The definition also applies to the illustration in your comments, which indeed allows separating $A$ and $B$ with one line, and then separating $B$ and $C$ with another. $\endgroup$
    – user44143
    Commented Jul 6, 2021 at 12:20
  • 1
    $\begingroup$ @user2182: well, the only case in which a line does not intersect two parallel lines is if it is parallel to both. In such a case, the sum of sidelengths of these two squares is at most 1, and the third has at most length 1 because of height constraints. This degenerate case so doesn't influence much the proof. $\endgroup$ Commented Jul 6, 2021 at 12:27
1
$\begingroup$

Partial solution

Let the rectangle R have the longer side horizontal. It is easy to prove that you can label the squares A,B,C such that A can be shifted (i.e. translated) all the way to the left without overlapping the other squares, and C can be shifted all the way to the right. Shift them as just described. Then we have A entirely in the left half of R and C entirely in the right half of R. Since A and C are in separate halves of R, we can shift each of them to touch two sides of R, because B can block only one direction. Now expand A until it touches B or it cannot be expanded without going beyond R, and do the same for C.

As thus constrained, A can be fully described by its size x∈[0,1] and orientation angle r∈[0,π/2] and the vertical position p∈[0,1] of its centre. The set of possible parameters (x,r,p) is compact. Likewise for C. Moreover, the maximum size of B that can fit into R without overlapping A,C is continuous with respect to the parameters specifying A,C and the parameter in [0,π/2] specifying the orientation of B. Thus by EVT (extreme-value theorem) we can assume that A,B,C actually achieve a maximum total size.

So thus far, A is in the left half of R and C is in the right half of R, each touching two sides of R, and B must fall into one of the following cases (otherwise it can be expanded contradicting maximality):

  1. B has sides s,t,u,v with s,t being opposite sides and can slide towards v. If either of s,t, say s by symmetry, has only a single contact point, that point must be touching a square (not R), and we can expand B while keeping t,u on the same lines and contracting the touching square, yielding a higher total size, contradicting maximality. Thus both s,t have multiple contact points, so B must be flush with A on one side and flush with C on the opposite side. If A is not flush with the side of R, then we can expand B slightly while contracting A by the same amount to maintain total size and create a gap between A and the left side of R, and so after that we can shift A leftward and expand A slightly, contradicting maximality. Therefore A,B,C have sides parallel with R, yielding maximum total size 2.

  2. B cannot slide towards any side, so each side is blocked by something. Thus B must touch R, otherwise A,C must block two sides each, which requires an edge of A touching a corner of B and an edge of C touching the opposite corner of B, in which case we can expand B slightly perhaps with some rotation, contradicting maximality. If B touches the left side of R, then B is entirely in the left half of R, so it suffices to show that two non-overlapping squares within a unit square have total size at most 1 (which can be done via similar tricks). Similarly if B touches the right side of R. The remaining case is if B touches the top or bottom side of R, say the top by symmetry. Then the lowest side of B must be blocked, and so A,C must both be touching the bottom side of R and a lower corner of B. Thus B is basically a maximal square inscribed in a triangle, and I believe it is not difficult to finish from here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .