Russian(?) Post Office Problem

Question

I once heard about this problem at uni, but I don't remember all the details of the proof, I think it was called Russian Post Office Problem.

There is a post office, where you pay length + width + height of your parcel. The question, is it possible to save money by packing the original cuboid in a larger cuboid with different dimensions (answer is no).

The proof went something like this: Assume $a_0,b_0,c_0$ resp. $a_1,b_1,c_1$ are the dimensions of the inner resp. outer cuboid. So the volume $a_1b_1c_1$ is larger than $a_0b_0c_0$ while $a_0+b_0+c_0>a_1+b_1+c_1$. Now replace each cuboid with the union of balls with diameter $x$ and center inside the cuboid, obviously the inner cuboid still fits into the outer cuboid. Now look at the difference between the two volumes.

Here some argument was made that we can look at $$(a_1+x)(b_1+x)(c_1+x)-(a_0+x)(b_0+x)(c_0+x),$$ i.e. ignore the rounded corners and rounded edges. I understand that we can ignore the rounded corners, as replacing them by standard corners has the same effect on each volume. But for the edges, I don't remember the argument, as replacing the rounded edges of the outer cuboid would add less volume than replacing the rounded edges of the inner cuboid.

In the end, the argument was that for large $x$, we have $$((a_1+x)(b_1+x)(c_1+x)-(a_0+x)(b_0+x)(c_0+x))/x^2\sim\\a_1+b_1+c_1-a_0-b_0-c_0<0,$$ a contradiction to the larger volume of the outer cuboid.

There is another proof idea which I had myself. If the outer cuboid perfectly fits the inner cuboid, then we can get from the left side to the right side by traversing three edges of the inner cuboid. If $A$ is the rotation matrix by which the inner cuboid was rotated, then the width of the outer cuboid is $|(A(a_0,0,0))_0|+|(A(0,b_0,0))_0|+|(A(0,0,c_0))_0|$. Combining this for all sides, we get that $$a_1+b_1+c_1=\sum_i(|A(a_0,0,0))_i|+|(A(0,b_0,0))_i|+|(A(0,0,c_0))_i|.$$ Further $\sum_i |(A(a_0,0,0))_i|=a_0\sum_i |A_{1i}|\ge a_0\sum_i A_{1i}^2=a_0$ and similarly for the other dimensions, so $a_1+b_1+c_1\ge a_0+b_0+c_0$, a contradiction to the assumption.

Answer 1

I think I remember the missing argument. The volume of a cuboid with rounded corners and corner radius $x$ consists of

• $8$ corners, which are of volume $x^3$ times some constant,
• $12$ edges, which are of volume $x^2$ times the edge length times some constant,
• $6$ faces, which are cuboids with volumes $abx$, $acx$ or $bcx$
• and the inner cuboid with volume $abc$.

We can ignore the corners, since they are the same for each cuboid with corner radius $x$. So dividing the rest of the volume by $x^2$, we are left (for large $x$) with the $12$ edges, which sum up to $a+b+c$ times some constant, concluding the proof that $a_1+b_1+c_1$ must be larger than or equal to $a_0+b_0+c_0$.