Using your Head is Permitted

November 2011 solution

Spoiler alert: The following description contains hints regarding the solution of last month's riddle. If you still mean to tackle that other riddle, you may want to hold on before you read this.

Let us begin by recapping from last month's solution:

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.

The smallest dimensions of an axes-parallel parcel that can contain this parcel are d1|A1i| + d2|A2i| + ... + dn|Ani|, where i is the dimension number.

What we need to prove is that the product of all these is no smaller than the product of all di.

Let B be an n-by-n matrix whose (i,j)'th element is equal to |Aij|. We are asking whether the product of all elements of Bd can be smaller than the product of all elements of d. Note that the product of all elements of Bd is a polynomial in the elements of d, all of whose monomials are of degree n. Furthermore, all these monomials are non-negative. We will show that the monomial that is associated with the product of all di is at least 1, therefore showing that the size of this monomial alone (let alone all of Bd) is at least as large as the product of all elements of d.

To show this, note that this coefficient is the permanent of B, which is at least as large as the determinant of A. (Both are sums of the same elements but with different signs. In computing the permanent of B, all signs are positive.) Because A is a rotation matrix, its determinant is known to be 1, so the permanent of B, being the coefficient we are looking for, is at least 1.


Back to riddle

Back to main page