# Largest Triangle with Vertices in the Unit Cube

How would one find a triangle, with vertices in or on the unit cube, such that the length of the smallest side is maximized? And what is that length?

A lower bound for the length is $\sqrt{2}$, by looking at an equilateral triangle, and an upper bound is $\sqrt{3}$, since that's the diameter of the unit cube.

-
Are you looking at the unit cube $\{0,1\}^3$, or are you also considering higher dimensional analogues? – JavaMan Jun 9 '11 at 21:56
@DJC: Hint: which unit cubes have diameter $\sqrt{3}$? – TonyK Jun 9 '11 at 22:05
@DJC: Sorry for being unclear; I assumed that the unit cube had only one meaning. I am looking at the unit cube $\{0,1\}^3$ in $\mathbb{R}^3$. – Michael Chen Jun 10 '11 at 2:56
I was actually unclear. I know you were looking at the $3$-dimensional cube. What I meant to ask was have you considered higher dimensional analogues? – JavaMan Jun 10 '11 at 11:54
@DJC: I have not, I am not accustomed to thinking in higher dimensions. I suppose in a lower dimension ${0,1}^2$, one can find minimum length $1$. – Michael Chen Jun 11 '11 at 19:11

Introduce coordinates as usual, so that the cube consists of all points $(x,y,z)$ with $0 \le x \le 1$, $0 \le y \le 1$, and $0 \le z \le 1$.

Instead of trying to maximize the minimum length, let us try to maximize the product of the lengths of the sides, or better, the product of the squares of the lengths. Let the vertices be $(x_i,y_i,z_i)$, with $i=1$, $2$, and $3$.

Then one of the squares of a side is $$S_3=(x_1-x_2)^2 +(y_1-y_2)^2+(z_1-z_2)^2,$$ and the others are equally easy to write down. By the Arithmetic Mean/Geometric Mean Inequality, we have $$(S_1S_2S_3)^{1/3} \le \frac{S_1+S_2+S_3}{3}.$$

Note that $S_1+S_2+S_3$ consists of three terms, one of which is $$(x_1-x_2)^2+(x_2-x_3)^2+(x_3-x_1)^2$$ with the other terms having the same shape, but with $x$ replaced by $y$ and by $z$.

Expand. We want to maximize $$2x_1^2+2x_2^2 +2x_3^2 -2x_1x_2-2x_2x_3-2x_3x_1$$ under the constraints $0 \le x_i \le 1$.

It is easy to see, using the calculus or otherwise, that the maximum is $2$, and therefore the maximum value of $(S_1+S_2+S_3)/3$ is $2$.

Thus the geometric mean of the product of the squares of the sides is $\le 2$, so the product of the lengths of the sides must be $\le 2\sqrt{2}$. It follows that the lengths of the sides cannot be all $>\sqrt{2}$. It is easy to come up with an example where we get equality.

Comment: Disappointing! I am not altogether happy to see what looked like an interesting geometric problem fall to routine work with inequalities. But a purely geometric proof seems difficult unless one does a certain amount of handwaving. And as a bonus we have obtained a somewhat stronger result.

It could be interesting to look for geometric questions that yield to the same technique (answers looking for problems). The inequalities used here are of a general character, so we ought to be able to generate and answer similar questions about hypercubes. The fact that we are dealing with triangles is not really important, as long as we work with all mutual distances in a set of points.

-
It just seems that one could proceed with a proof by contradiction: Suppose all three sides are > $\sqrt 2$...But then again, I'm really not in a position to criticize, given that I didn't provide a "tight" proof, and given the effort you put into yours. So...please understand I certainly didn't mean to criticize your efforts: it supported what otherwise were conjectures ...My comment was meant to be more of a pondering... "hmmm...this should be provable with less equipment...hmmm..." Sorry for any misunderstanding. – amWhy Jun 11 '11 at 19:31
Actually, I'll delete my first comment...I did not intend to take away from your work. I do like the "challenge" you raise about looking for other geometric questions: answers looking for problems...! ;-) – amWhy Jun 11 '11 at 19:41

The equilateral triangle with sides $\sqrt{2}$ is maximal. To see this, fix two of the points, and move the third. It's straightforward to show that this is a local maxima.

I'm not sure of an easy way prove that this triangle is a global maxima, but some code in Mathematica or something could do it. If a better solution existed, it would be a well-known cube dissection.

-
This is exactly the sort of thing that Mathematica (like similar packages) is completely useless for -- proving global extrema in geometric problems. – TonyK Jun 9 '11 at 21:59

I am trying to prove something like this: Denote the cube $ABCDEFGH$, and suppose it has side of length $1$. Suppose that there exists a triangle in the cube with the smallest side of length greater than $\sqrt{2}$. Then we can find two spheres of radius $\sqrt{2}$ whose centers are inside the cube and are at distance greater than $\sqrt{2}$ apart, which do not cover the cube. This is because of the existence of a triangle $XYZ$ inside the cube with the smallest side $XY> \sqrt{2}$. Picking the spheres centred in $X,Y$ of radii $\sqrt{2}$, these do not cover the cube, because $Z$ is outside them.

Take a variable sphere $S_P$ of radius $\sqrt{2}$ and center $P$. Denote $S_A$ the sphere of radius $\sqrt{2}$ and center $A$. The locus for $P$ such that $A \notin S_P$ is $K\setminus S_A$ where $K$ denotes the cube. Suppose we can find two spheres $S_X, S_Y$ centred in $X,Y$ and radii $\sqrt{2}$ which do not cover the cube and $XY >\sqrt{2}$. If the two spheres do not cover the cube, then neither one of them covers the cube, and there exists a vertex(since the cube is convex) which is not covered, for example $A$. Suppose $A \notin S_X$. Then $X \in K\setminus S_A$. Wherever we pick $X \in K\setminus S_A$ it is easy to see that $S_X$ covers $K\setminus S_A$, and $S_X$ leaves uncovered at most two vertices, let's say $A$ and $E$. If $S_X$ contains all the vertices but $A$ we are done. Then $S_X$ contains the prism $BCDFGH$.

In a similar way, $Y$ is near $A$ or $E$, and $S_Y$ covers $A$ and $E$ and the prism $ABDEFH$. Therefore $S_X,S_Y$ cover the cube, which is a contradiction.

I feel I am missing something, but I don't think I'm far from the solution.

-
I think this claim requires substantiation: "In a similar way, $Y$ is near $A$ or $E$, and $S_Y$ covers $A$ and $E$ and the prism $ABDEFH$." – TonyK Jun 9 '11 at 22:41
@TonyK: That's what I was thinking too. – Beni Bogosel Jun 10 '11 at 7:00