Means to an End (Part II): Smuggling Cocaine

Stupid Airline Policy

When you’ve been killing 24 sleepless hours in the greatest airport known to mankind, all so you can catch an overcrowded, 10 hour flight, you end up hating airlines, airports, and their many stupid rules (not to mention all other travelers on the face of the planet).   This probably has more to do with the fact that the vast majority of airline policies are asinine (albeit surprisingly complex and interesting), but still, they impact us at our worst, when we’re exhausted, anxious, and in desperate need of a shower.

One such airline policy uses “linear inches” to restrict the size of checked bags.  0.2 seconds of Googling lead me to United Airline’s Excess Baggage website where I found this nugget:

Airline-bots refer to the sum length + width + height as the amount of “linear inches,” and most do not allow bags in excess of 45 linear inches.  I’m sure there is a solid reason for using this type of measurement (as opposed to volume or surface area), but I remain suspicious that it was chosen for its simplicity.  In any event, for checked boxes, these linear inches are simply a multiple of what we called total edge length $L$.  Given a package with measurements $x, y,$ and $z$, its total edge length is $L = 4x + 4y + 4z = 4(x + y + z) = 4$(linear inches).

You can (and should!) exploit unstated assumption in these policies.  For instance, some of the largest passenger planes measure about $240$ ft. or $2892$ inches in length, and I think travelers should bring with them a rectangular package measuring $2893$ in. in length.  In order to comply with aforementioned rules you’d simply need to make its width and height sufficiently small, say $y = 1/9$ in. and $z = 1/8$ in.  I am  not certain what sort of object would require a box measuring $2892 \times 1/9 \times 1/8$ cubic inches, but that’s not the point.  The box can be empty for all we care.  The point is that, according to stated policy, United would have to check your box even though it would be physically impossible to do so.*

How to Smuggle the Most Cocaine

With our previous discussion in mind, we might wonder “What’s the largest volume box one can take aboard a United Airlines flight?”  Although this question has the sound of a “real world” problem, we travelers often can’t make use of its answer.  Many of the items we want or need to take on flights are of some fixed, rigid form (like skis or a bicycle), so that, regardless of their mass or volume, they require packaging with fixed dimensions.  No, this question really only applies to substances that are malleable and can conform to the shape of a given package.  Like sand, liquids, or, if you prefer, large amounts of a fine, white powder.

So, for the sake of argument, let’s say your job is to transport as much of this fine, white powder as possible, and that at some point you’ll need to use United Airlines to help you do so.  What sized box should you use?  To get started, we should assume that we’ll use as many linear inches as possible. This means $L/4 = x+ y + z$ is constant (specifically $45$).  Restricting $L$ and maximizing $V$ is the same as minimizing the isoperimetric ratio $L^3/V$, and so one might be nervous that the type of “box” we’ll end up designing is some sort of “generalized convex polyhedra,” like a sphere, or some other sort of package with infinitely many faces and edges.  As it turns out, the “smaller universe” of rectangular boxes keeps limits safe; our answer will be an honest, 6-sided package.

To see how this happens let’s do some math.  The volume of our box will be $V = xyz$, and given that we want to minimize $x+y+z$ subject to $V = C$Lagrange multipliers come to our rescue.  After computing some gradients, we find

$\displaystyle yz = \lambda$

$\displaystyle xz = \lambda$

$\displaystyle xy = \lambda$

$\displaystyle x + y + z = 45$

where $\lambda$ is some constant.  The first three equations easily imply that $yz = xz = xy$, and after eliminating degenerate cases (when $x, y$ or $z = 0$) as irrelevant, we find that $x = y = z$.  This is enough to tell us that the best box is a cube (one whose side length is $45/3$).

Of course, minimizing $L^3/V$ is also equivalent to restricting $V$ and minimizing $L$ (which, in this case, is the same as minimizing $x+y+z$).  The real-world version of this isoperimetric problem might sound something like this: Your boss wants you to transport one kilogram of our fine, white powder (which, after some density calculations, you figure will require $50.2$ cubic inches of space, a constant we will denote by $C$).  If the airlines charge you additional fees based on the linear inches of your package, how should you design your box so as to incur as little cost as possible?

The Lagrange multiplier equations obtained from this scenario are

$1 = \lambda yz$

$1 = \lambda xz$

$1 = \lambda xy$

$xyz = C$

which also imply that a cube does best.  At least, these equations and the ones before imply that a cube optimizes something, but given the dangerous nature of this line of work, one might be nervous about jumping to conclusions.  Perhaps a cube maximizes cost instead of minimizing it.  Sure, this feels unlikely, but what with your boss’s itchy trigger finger, it’s probably best to be entirely certain.

The Multivariable Second Derivative Test

Rather than set up our white powder transport problem using Lagrange multipliers, we could instead use the restriction $V = C$ to simplify the function being minimized.  Above we minimized $x + y + z$, but there’s no reason to restrict our attention to three variables (and how awesome would it be, by the way, to transport $k$ dimensional white powder?).  Instead, we generalize our discussion to $k$ variables $x_1, x_2, \dots, x_k$, our goal being to minimize $x_1 + x_2 + \dots + x_k$ subject to the constraint $V = x_1x_2\cdots x_k = C$.  For the three-dimensional case, we can first use this constraint to express $z$ as a function of the first variables and then attempt to minimize the function $x + y + C/(xy)$.  In general, we attempt to minimize the function

$\displaystyle f(x_1, x_2, \dots, x_{k-1}) = x_1 + x_2 + \dots + x_{k-1} + \frac{C}{x_1x_2\cdots x_{k-1}}.$

Setting $\nabla f = \vec{0}$ produces the equations

$\displaystyle 1 - \frac{C}{x_1\cdot x_2 \cdots x_i^2 \cdots x_{k-1}} = 0$

for $1 \leq i \leq k-1$.  Reintroducing our variable $x_k = C/(x_1\cdot x_2 \cdots x_{k-1})$ these equations become

$\displaystyle 1 - \frac{x_k}{x_i} = 0$

from which we determine that the only critical point corresponds to a cube with side lengths $x_i = C^{-1/k}$.  Now we are in a position to confirm that this cube minimizes our function.  All we need is the second-derivative test.

In several variables the role of a second derivative is played by the Hessian matrix.  For a general, real-valued function $f(x_1, \dots, x_{k-1})$ the $(i,j)$ entry of this $(k-1)\times(k-1)$ matrix is given by $f_{x_i, x_j}$.  For our function in particular one finds that evaluated at $x_i = C^{-1/k}$ our Hessian matrix is given by $\displaystyle -C^{-1/k}\,I$.

From single variable calculus we know that if a function’s second derivative is negative at a critical point, then that critical point is a local minimum.  An analogous statement holds in multivariable calculus: if a function’s Hessian matrix is negative definite at a critical point, then that critical point is a local minimum.  Because of the particularly simple form of our Hessian, we easily conclude that $x_i = 1/\sqrt{C}$ is a local minimum.  Moreover, because this was the only critical point, it is the global minimum.  So there you have it.  What’s the best way to package fine white powders?  Cubes.

Suppose our task was to construct a $k$-dimensional box that minimizes

$\displaystyle \frac{\left(V_{k-1}\right)^k}{\left(V_k\right)^{k-1}}.$

In three dimensions this ratio compares the cube of surface area to the square of volume. Seeking a box that minimizes this quantity is equivalent to using the smallest amount of material possible to construct a box that encloses a specified volume.

The 2-dimensional volume (or surface area) enclosed by a box with lengths $x_1 = x, x_2 = y,$ and $x_3 = z$ is given by $V_2 = 2yz + 2xz + 2xy$.  It is a fun exercise to verify that in $k$ dimensions the $(k-1)$-dimensional volume enclosed by a $k$-dimensional box with lengths $x_1, x_2, \dots, x_k$ is given by

$\displaystyle V_{k-1} = 2\sum_{i=1}^k \, \frac{V_k}{x_i} = 2\sum_{i=1}^k \, \frac{x_1\cdot x_2 \cdots x_k}{x_i}.$

Our goal is to minimize $V_{k-1}$ subject to the constraint that $V_k = C$.  As in the previous section, we can use this constraint to rewrite our function $V_{k-1}$ as one that depends only on the $(k-1)$ variables $x_1, x_2, \dots, x_{k-1}$.  The function to be minimized can be written as

$\displaystyle f(x_1, x_2, \dots, x_{k-1}) = 2x_1\cdot x_2 \cdots x_{k-1} + \sum_{i=1}^{k-1} \, \frac{2C}{x_i}.$

Setting the gradient of $f$ equal to the zero vector again implies (after some algebraic manipulation) that $x_1 = x_2 = \dots = x_{k-1} = C^{-1/k} = x_k$.  Although the Hessian is slightly more complicated in this case, it, too, is easily verified as negative definite when evaluated at our critical point.

Cubes, Man.  Cubes.

The take home lesson?  Cubes satisfy two isoperimetric problems.  In fact, one should wonder whether or not cubes satisfy any other isoperimetric problems.  Is it true that, amongst all $k$-dimensional boxes, a $k$-dimensional cube will minimize all of the ratios

$\displaystyle \frac{(V_p)^k}{(V_k)^p}$

where $1 \leq p < k$?  Repeating and adjusting the arguments above, while possible, doesn’t seem particularly elegant or enlightening.  By this point we pretty much suspect that cubes will be the answer, but what is behind this hunch?  Is there a general principal or idea at play, one that we might be able to make precise and mathematically convincing?  One that avoids the various cases and formulae for $p$-dimensional volumes enclosed by $k$-dimensional boxes?**

One basic observation (made more precise by Steiner, as hinted at in our previous post) is that isoperimetry is linked with symmetry, and so it makes sense to conjecture that, within one’s universe, the most symmetric object available ought to solve a given isoperimetric problem.

This isn’t precise enough, but I’ll let it stand for now.  The two ispoerimetric problems that $k$-cubes clearly do solve are enough of a foundation on which to build some interesting questions and observations.  Now, sit back and enjoy the remainder of your flight.

Footnotes

*In actuality a package measuring $2893$ inches in length could easily fit aboard a plane measuring $2892$ inches in length.  After all, the plane has some width, too, and so one can angle this inconvenient box and then store it.  This, of course, leads to a cute geometric question: given a rectangle of length $\ell$ and  width $w$, what is the longest line segment the rectangle can contain?

**These formulae aren’t so terrible.  Probably the best way to get a handle on them is by using elementary symmetric polynomials.  Some clever counting confirms that for a $k$-dimensional box

$\displaystyle V_p = 2^{k-p} e_p\left(x_1, x_2, \dots, x_k\right).$