4 ms·
The second problem is really good. I just thought up a solution that, though more complex, seems to me much less mysterious, and the 2D case does shed guidance
by cousin_it 17y ago
The second problem is really good. I just thought up a solution that, though more complex, seems to me much less mysterious, and the 2D case does shed guidance on 3D.
One-dimensional case:
a1 < a2
Two-dimensional case:
a1*b1 < a2*b2 (area)
a1+b1 < a2+b2 (sides projected outwards, triangle inequality)
Three-dimensional case:
a1*b1*c1 < a2*b2*c2 (volume)
a1*b1+a1*c1+b1*c1 < a2*b2+a2*c2+b2*c2 (surface area, projected outwards)
a1+b1+c1 < a2+b2+c2 (our problem)
Notice the pattern already? If one N-dimensional box lies inside the other, the inequality holds for all elementary symmetric polynomials of box dimensions.
http://en.wikipedia.org/wiki/Elementary_symmetric_polynomial http://en.wikipedia.org/wiki/Elementary_symmetric_polynomial
To prove it, we need only notice that the symmetric polynomial of degree M is proportional to the average volume of the M-dimensional "shadow" of the N-dimensional box, averaged over all projection directions uniformly. (To convince yourself of that, work through the two-dimensional case.) On the other hand, if a box lies inside another box, each "shadow" of the smaller box lies within the corresponding "shadow" of the bigger box. Done!