16
$\begingroup$

A cube of side one contains two cubes of sides $a$ and $b$ having non-overlapping interiors. How to prove the inequality $a+b \le 1?$ The same question in higher dimensions.

$\endgroup$
  • 2
    $\begingroup$ @John: the 1-dimensional case is utterly trivial. The 2-dimensional case is much less so. $\endgroup$ – dfeuer Jun 14 '13 at 18:55
  • 1
    $\begingroup$ A couple thoughts that may or may not have any value: 1. It's safe to assume that: one vertex of cube $A$ is in the $x_0=0$ face of the unit cube and that one vertex of cube $B$ is in the $x_0 = 1$ face of the unit cube. It's also safe to assume that for each $n$, either cube $A$ or cube $B$ has a vertex in the $x_n = 0$ face. 2. There's always a plane such that the two cubes lie on opposite sides of the plane. Under most circumstances, this plane can be made to extend a face of one of the two cubes. $\endgroup$ – dfeuer Jun 14 '13 at 20:32
  • 1
    $\begingroup$ And I did not assume so, nbubis. $\endgroup$ – dfeuer Jun 14 '13 at 20:59
  • 7
    $\begingroup$ This is hard.${}$ $\endgroup$ – Alexander Gruber Jun 14 '13 at 21:57
  • 2
    $\begingroup$ The two-dimensional case has been treated here: math.stackexchange.com/questions/244474/two-squares-in-a-box/… $\endgroup$ – Christian Blatter Jul 28 '13 at 10:27
2
$\begingroup$

Here's a proof of the (much weaker) fact that $a+b\leq\sqrt{n}$. Maybe someone can find a way to elaborate upon it to get a solution of the problem.

Let $n$ be the dimension we are considering. Let $C_n\subset\mathbb{R}^n$ be the cube of side $1$. Let $a$ be the side of the first cube (we will call it $A$), $b$ the side of the second cube ($B$). By the classical theorems of convex separation, there is an $(n-1)$-plane $P_{n-1}$ separating the two cubes (since they are disjoint). By translating everything if necessary, assume that $0$ is contained in $P_{n-1}$. Let $L$ denote the line through $0$ that is orthogonal to $P_{n-1}$ and denote by $\pi:\mathbb{R}^n\rightarrow L\cong\mathbb{R}$ be the projection on $L$. It is easy to prove that the projection of a cube of side $x$ on a line is an interval of maximal length $x\sqrt{n}$. Let $\ell$ be the function associating to an interval in $\mathbb{R}$ its length. Then: $$\ell(\pi(C_n))=:z\leq\sqrt{n}$$ $$\ell(\pi(A))=:x\geq a$$ $$\ell(\pi(B))=:y\geq b$$ Thus: $$a+b\leq x+y\leq z\leq \sqrt{n}$$ where the second inequality is given by the fact that $P_{n-1}$ separates $A$ and $B$.


A possible elaboration of the above would be treating higher dimensional planes instead of the $1$-plane (= straight line) $L$. For example we could obtain an $(n-1)$-plane $Q$ by taking some vector $v\in P_{n-1}$ and defining $Q$ to be its orthogonal complement. Then the projections of $A$ and $B$ on $Q$ would be disjoint, since the $(n-2)$-plane $P_{n-1}\cap Q$ would separate them in $Q$. Maybe some work in this sense could give us better estimates or some way to prove the initial statement by induction.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Using simple calculation of volume we can prove that (assume $n$ is the dimensioin), $$a+b\le (2^{n-1}(a^n+b^n))^{\frac{1}{n}}\le2^{\frac{n-1}{n}}$$ $\endgroup$ – asatzhh Aug 7 '13 at 14:58
  • 1
    $\begingroup$ And this above is almost best possible bound using your methods since we have some nice upper bound of volume of intersection of unit cube and some hyperplane (called cross-sections) [See: K.Ball, Volumes of sections of cubes and related problems, Lecture Notes in Math. 1376 (1989), 251–260.] $\endgroup$ – asatzhh Aug 7 '13 at 15:09
  • $\begingroup$ @asatzhh Thank you for the elaboration. I hoped in the possibility to get a better bound, but it is still pretty good, I'd say. $\endgroup$ – Daniel Robert-Nicoud Aug 7 '13 at 15:40
  • $\begingroup$ I put it with more details in MO and I hope my English is good enough for you to understand. $\endgroup$ – asatzhh Aug 7 '13 at 16:19
0
$\begingroup$

The following proof basically says the following: (1) you can assume the cubes are in opposite corners, and (2) you can then assume they are aligned with the unit cube, in which case the theorem follows easily.

Preliminary Fact: If we have an arrangement of two n-cubes, A and B, in $\mathbb{R}^n$, then for each standard basis direction, $\vec{e}_i$, we can translate A in either the $+\vec{e}_i$ or the $-\vec{e}_i$ direction forever without intersecting B (this is seen by the convexity of cubes). If A can move in one direction forever, then B can move in the opposite direction forever.

By this fact, if A and B are within the unit cube, we can go through each direction and slide each of them in opposite directions so that they end up in antipodal corners of the unit cube. WLOG let A be in the corner $(0,\ldots,0)$ and B be in the corner $(1,\ldots,1)$. So A cannot slide in the negative basis vector directions without leaving the box, and B cannot slide in any of the positive basis vector directions.

This sliding doesn't change the size of A or B, so we can assume that $a+b$ is the largest possible sum of side lengths ($a$ is side length of A and $b$ is side length of B).

Now for the main technical lemma.

Lemma: Take $x_C = \sup \{y | \{y,y,\ldots,y\}\in C\}$ where $C$ is some cube inside the unit cube which intersects the main diagonal. Then $x_C \geq c$, where $c$ is the side length of $C$.

What this says is that if we take the point $\{x_C,\ldots,x_C\}$ on the intersection of $C$ and the main diagonal which is furthest from the origin, then the cube $[0,x_C]^n$ has longer side length than $C$. We use this to show that A and B must be aligned with the unit cube if they are to have the largest side length.

Proof sketch of lemma: We will sketch the proof since it's an ugly calculation, which can be done if interested. So we can reduce the problem to saying that if an affine unitary transformation T takes the unit cube to the first quadrant, $[0,\infty)^n$, and can't be slid any further in the negative basis directions without leaving the first quadrant, then $x_{T([0,1]^n)} \geq 1$. We can get rid of the affine part by looking at only unitary transformation of $[-1/2,1/2]^n$ and defining $x_{T[-1/2,1/2]}$ w.r.t. $(\min(T_1[-1/2,1/2],\ldots,\min(T_n[-1/2,1/2])$ instead of the origin. Parameterizing the unitary transformations, we can set this up as an optimization problem, which you have to solve for general n.

So all the calculation is encoded in that lemma. The rest is pretty simple. We have A and B at opposite parts of the unit cube, and they are largest possible total side length sum. Now if A is not aligned with the unit cube, we can replace it by a cube at least as big that is aligned by the lemma. It's easy to see this new cube doesn't intersect B. So assume A is aligned. Now, we can use the same argument to replace B by an aligned cube as well (except the lemma is used w.r.t. the antipodal point of the origin this time). Thus we have two aligned cubes with total side length at maximum. From here it's not so bad to see the sum of side lengths must be at most 1.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Please explain "It's easy to see this new cube doesn't intersect B" in detail. $\endgroup$ – user64494 Aug 4 '13 at 4:41
  • $\begingroup$ Sorry, easy to see in 2-dimensions but not so much in higher, although a formal proof can still be stated. So in sliding everything to opposite corners, we must have had that $B$ can move in any of the positive basis vector directions without intersecting $A$. Hence if a point $(b_1,\ldots,b_n)$ of $B$ is in the cube $[0,x_A]^n$, then translate $B$ by $(x_A-b_1,\ldots,x_A-b_n)$ and we see that $B$ intersects $A$ now (at the point $(x_A,\ldots,x_A)$). But we've only moved in positive basis directions and it's impossible to intersect $A$ by doing so. $\endgroup$ – Louis Aug 4 '13 at 21:26
  • $\begingroup$ I don't find it serious. You did not explain the following place "It's easy to see this new cube doesn't intersect B. So assume A is aligned. Now, we can use the same argument to replace B by an aligned cube as well (except the lemma is used w.r.t. the antipodal point of the origin this time)" which was requested. $\endgroup$ – user64494 Aug 5 '13 at 4:07
  • $\begingroup$ We can replace A by an aligned cube (namely $[0,x_A]^n$) since we know it's at least as big and we'll still have a configuration of maximum total edge length. To apply the same argument to B, maybe an easier way to explain would be to say "reflect the configuration through the middle of the unit cube. Then B is now in the origin's corner and A is aligned and in the opposite corner. Then apply the same reasoning to B." The main point of making these replacements is that we assumed maximum total edge length in our configuration. So if we show a+b<=1 for the replaced configuration, then done $\endgroup$ – Louis Aug 5 '13 at 5:09
  • $\begingroup$ Unfortunately, I don't find your main technical lemma to be proved. $\endgroup$ – user64494 Aug 5 '13 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.