Let d be an n-dimensional vector denoting the dimensions of the parcel. Suppose we wish to pack it inside a larger parcel by placing it at some odd angle. We describe this angle by an n-by-n matrix, A, whose rows are the unit vectors in the directions of the main axes of the parcel.
What are the smallest dimensions of an axes-parallel parcel that can contain this parcel?
If X and Y are two diametrically opposite corners of the parcel, the vector connecting X and Y is ±d1A1 ±d2A2 ... ±dnAn.
By picking all 2n possible X-Y pairs, any assignment of signs to the previous equation can be attained. For the larger parcel to contain all these vectors, it must be at least as large as the largest of these in every dimension. Therefore, the i'th dimension of the parcel must be at least d1|A1i| + d2|A2i| + ... + dn|Ani|, which, summed together, yields d1(Σi |A1i|) + d2(Σi |A2i|) + ... + dn(Σi |Ani|).
We will prove that for any j, Σi |Aji| ≥ 1.
To do this, we recall that the transpose of a rotation matrix is also a rotation matrix. (This is a fact that appeared previously on this site. It can be seen immediately when considering that a rotation matrix can be represented as the product of matrices that represent axis-parallel rotations. The transpose can therefore be represented as a product of transposed axis-parallel rotation matrices, which can easily be verified to be axis-parallel rotation matrices themselves.)
We therefore know that Σi Aji2=1. Compare this with (Σi |Aji|)2, and the solution is immediate.
Now for credits:
This is a puzzle of Russian origins. It made an appearance in the International Mathematics Tournament of the Towns (Problem 5, Fall 1998, Senior A-Level Paper). However, it is older than this. I first saw it with a different solution in a Peter Winkler collection.
Back to riddle
Back to main page