Christmas Presents

My National Review Online "Diary" column for December 2003 included the following brainteaser.

Christmas Presents

—————————

Three children get three different Christmas presents, packed in three boxes.  All of these boxes have dimensions which are an integer number of centimeters, due to production constraints at the boxing company.  All dimensions are less than a meter.  To their amazement, the children note that  

• no two boxes have the same dimensions;
• they all have the same volume;
• the length of the piece of string tied around each box (four times the sum of the box’s dimensions) are the same.

Can you find the possible dimensions of the boxes?  Are there any other coincidences to be found among the three boxes?  For example, in the surface area of the paper wrapping them?  Can any box be a cube?  Have a square side?

———————————————

I guess I should apologize for this one, as I don't have a solution method.  I thought I did when I set the puzzle, using basic properties of the roots of a cubic and a spot of Diophantine analysis.  However, it didn't pan out.

I do know (because I wrote a VB program) that there are 342 possible solutions.  None contains a cubic box.  In 23 of the solutions, at least one of the boxes has a square face; in 4 of those 23 two boxes have a square face.  In no case do two boxes have the same surface area (which I think a bit surprising). 

A complete solution set is attached at the end of this web page.  Here are the four solutions with two boxes having a square face.  Each box is described like this:  (a, b, c)  (L, A, V), where a, b, and c are the sides of the box, L their sum, A the surface area, and V the volume. 

Solution 1:
(9, 20, 20)  (49, 1520, 3600)
(10, 15, 24)  (49, 1500, 3600)
(12, 12, 25)  (49, 1488, 3600)

Solution 2:
(18, 40, 40)  (98, 6080, 28800)
(20, 30, 48)  (98, 6000, 28800)
(24, 24, 50)  (98, 5952, 28800)

Solution 3:
(27, 60, 60)  (147, 13680, 97200)
(30, 45, 72)  (147, 13500, 97200)
(36, 36, 75)  (147, 13392, 97200)

Solution 4:
(25, 63, 63)  (151, 14238, 99225)
(27, 49, 75)  (151, 14046, 99225)
(35, 35, 81)  (151, 13790, 99225)

Solution 4 is the one of only two of the 342 possible solutions for which the volume is an odd number.

———————————————

Franηois Charton, who sent me the puzzle, adds the following theorems and proofs.  The second theorem explains why you cannot have two parcels with the same surface, the third which you will never have a cube as a solution.

Franηois has also kindly sent a correction to my own solution.  I reproduce his letter at the end of these theorems.

Theorem 1:  No two parcels can have a common dimension

Proof : Suppose we have two parcels of dimensions (a,b,c) and (a,d,e), as their volume and sum of the their dimensions are equal, we have

Abc=ade and a+b+c=a+d+e,

as a is not equal to zero, this yields

bc=de and b+c=d+e,

which means b=d+e-c and, replacing this value in de-bc=0

c*c - (d+e)c +de=0

now this means (c-e)(c-d)=0 and so c is either equal to d or e, and b is equal to e or d : the two parcels are the same, a contradiction.

Corollary :

No two parcels can have one side with the same surface, or perimeter : let (a,b,c) and (d,e,f), ab=de yields (given abc=def) c=f, and a+b=d+e yields (given a+b+c=d+e+f) c=f


Theorem 2:  No two parcels can have the same surface

Proof : Let (a,b,c) be the dimension of a parcel, its surface is 2ab+2bc+2ac

Suppose two parcels (a,b,c) and (d,e,f) have the same surface, let

V=abc=def and L=a+b+c=d+e+f (by hypothesis)

And S=ab+bc+ac=de+ef+df (as they have the same surface)

Then (X**n denoting the n-th power of X, as in Fortran) let P(X) be the polynom X**3 - 3L X**2 + 3S X - V=0

P(X), a third degree polynom, has three complex roots. And can be factored in two ways as

P(X)=(X-a)(X-b)(X-c)=(X-d)(X-e)(X-f)

Which means the parcels have to be the same


Theorem 3:  No parcel can be a cube

Proof : (a little bit more involved)

Let (a,a,a) be a cubic parcel and (b-c,b,b+d) (c,d>=0) another one

The equality of the sums yields

3a=3b+d-c (1)

And that of the volumes

a**3=b ( b**2 + (d-c)b - cd) ......... (2)

As per (1) d-c=3(a-b), replacing in (2) we have

a**3 = b**3 + 3b**2 (a-b) - bcd

a**3 - b**3 = 3b**2 (a-b) - bcd

(3) (a-b) (a**2 + ab - 2b**2) = - bcd <=0 (per hypothesis)

we know that a cannot be equal to b (theorem 1), we now have two cases

case 1 : a > b

dividing (3) by (a-b) we get :

a**2 + ab - 2b**2 <=0

as a>b>0, we have a**2 > b**2 and ab >= b**2

therefore a**2 + ab > 2b**2

and a**2 + ab - 2b**2 > 0, a contradiction

case 2 : a < b

(3) becomes

a**2 + ab - 2b**2 >0

as b>a>0, we have a**2 < b**2 and ab <= b**2

therefore a**2 + ab < 2b**2

and a**2 + ab - 2b**2 < 0, a contradiction

which completes the proof

(visually, this means that a cube is the smallest possible volume for a given sum of length in a parcel, and the minimum is strict)


Theorem 4:  At least one parcel has no square face

Proof :

Suppose the three parcels have dimensions (a a b) (c c d) (e e f)

We have 2a+b = 2c+d, which yields

d = 2 (a-c)+b

then,

a**2 b = c**2 b + 2c**2 (a-c)

that is

b(a-c)(a+c) = 2 c**2 (a-c)

dividing by a-c (per theorem 1 they cannot be equal)

2 c**2 - bc - ba = 0

Solving this in c yields

c = Ό ( b + sqrt(b**2 + 8ab))

or

c = Ό ( b - sqrt(b**2 + 8ab))

and the same argument holds for the value of e, as c and e cannot be equal, we have to have either c or e equal to

Ό ( b - sqrt(b**2 + 8ab)), which is a negative number, a contradiction.

Note that all the three first theorems do not make use of the fact that we have three parcels (they work with only two), and that none of the four use the fact that the dimensions are integers...

———————————————

(Franηois's corrections):

John,

Prompted by your comments on the number of solutions to the parcel
problem, I wrote a small program this week end to compute all of them,
and found a small error in the list you put on your page.

The number of solutions is not 342, but 358. In fact, there are 326 sets
of three boxes which satisfy the premise (is this an english word?), and
8 sets of 4 boxes. Like the famed musketeers, the three children might
as well have been four: we can find 4 parcels with the desired property.
Looking at your list, these 4-solutions are counted twice, and not 4
times as they should (there are four ways to pick 3 parcels out of
four...).

This is probably because of the way your VB program is written: my
impression is that you iterate on the dimensions of the smallest parcel,
look for two solutions and then stop without looking for other
possibilities. In this case, if you had 4 solutions A,B,C and D, you
would find :

A, B, C
B, C, D

But not A B D and A C D (this seems plain from the list you give).

The way I did it was to iterate over all possible boxes, and put them
into a list ordered per length/volume pair (for each length/volume pair,
I have a list with the corresponding solutions). Then I enumerate this
list to find all solutions (by looking a the pairs with 3 or more
solutions).

Back to the problem, I found for all parcels with dimensions 1-99
inclusive,

152 734 length-volume pairs which happen in only one parcel
6 453 length volume pairs which happen in exactly two parcels
326 pairs which appear in three parcels
8 pairs which appear in 4 parcels

I suspect that if we allow the maximum dimension to be as large as we
want, we could find solutions for the problem with any number of
children, the general reasoning behind it is that adding one child to
the problems adds three free parameters (the dimensions of his/her
parcel), and only two constraints (length and volume), and n-children
problem will therefore have 3n free parameters, and 2n-2 constraints, ie
n-2 degrees of freedom.

Interestingly, the shortest-length 3 parcel solution is 39, and the
shortest-length 4 parcel solution is 118, note that 118 = 3 * 39 + 1,
this can't be a link to the Collatz problem, can it?

Here are the 8 4-solutions (format : (a,b,c) <length,volume>

(9,56,65) <130,32760>
(10,42,78) <130,32760>
(14,26,90) <130,32760>
(15,24,91) <130,32760>

(14,50,54) <118,37800>
(15,40,63) <118,37800>
(18,30,70) <118,37800>
(21,25,72) <118,37800>

(12,60,63) <135,45360>
(14,40,81) <135,45360>
(15,36,84) <135,45360>
(21,24,90) <135,45360>

(15,48,70) <133,50400>
(16,42,75) <133,50400>
(18,35,80) <133,50400>
(24,25,84) <133,50400>

(20,54,56) <130,60480>
(21,45,64) <130,60480>
(24,36,70) <130,60480>
(28,30,72) <130,60480>

(18,52,70) <140,65520>
(20,42,78) <140,65520>
(21,39,80) <140,65520>
(26,30,84) <140,65520>

(24,60,65) <149,93600>
(25,52,72) <149,93600>
(26,48,75) <149,93600>
(30,39,80) <149,93600>

(35,72,78) <185,196560>
(36,65,84) <185,196560>
(39,56,90) <185,196560>
(40,54,91) <185,196560>

———————————————

Here is the compete solution set, laid out in the same form as the four solutions above..