### 54th Putnam 1993

Problem B5

Show that given any 4 points in the plane we can find two whose distance apart is not an odd integer.

Solution

This is a curious question. It is easy if you happen to know the formula for the volume of a tetrahedron in terms of the lengths of its sides (which almost no one does). Otherwise it harder. Some alternative solutions are below.

The formula is V = 1/12 √(∑1 a2b2c2 - ∑2a2b2c2 - ∑3 a4b2). Here ∑1 is taken over the 12 cases where a, b, c form an open path of length 3. ∑2 is taken over the 4 cases where a, b, c form the sides of a face. ∑3 is taken over the 6 cases where a, b are opposite sides (without a vertex in common). This is usually written as a 5 x 5 symmetric determinant D with zeros on the diagonal (the volume is 12/√2 times the square root of D). If we label the vertices as 1, 2, 3, 4 so that the lengths of the sides become dij, then the elements below the diagonal are given by D21 = d212, D31 = d312, D32 = d322, D41 = d412, D42 = d422, D43 = d432, and D51 = D52 = D53 = D54 = 1.

In either case, we use a parity argument. If all the lengths are odd integers, then their squares are all congruent to 1 mod 4. So the sum is obviously congruent to 2 mod 4 and hence non-zero. With a little more work the determinant is congruent to 4 mod 8 and hence non-zero.

I do not know an elegant proof of the formula for the volume of a tetrahedron. It can be derived in a straightforward way, but the algebra is fairly horrendous (and probably takes half an hour, if you are careful enough not to make any mistakes). Choose coordinates so that the points are (0, 0, 0), (a, 0, 0), (d, b, 0), (e, f, c). Take the lengths as: P from (0, 0, 0) to (a, 0, 0); Q from (0, 0, 0) to (d, b, 0); R from (a, 0, 0) to (d, b, 0); L from (0, 0, 0) to (e, f, c); M from (a, 0, 0) to (e, f, c); and N from (d, b, 0) to (e, f, c). Then the volume is 1/6 abc. We have the following equations:
P2 = a2 (1); Q2 = b2 + d2 (2);
R2 = (a - d)2 + b2 (3); L2 = e2 + f2 + c2 (4);
M2 = (a - e)2 + f2 + c2 (5); N2 = (d - e)2 + (b - f)2 + c2 (6).
(1) gives: a = P.
(1) + (2) - (3) gives: 2ad = P2 + Q2 - R2, or d = (P2 + Q2 - R2)/2P;
subs in (2) gives: b2 = Q2 - d2 = (2P2Q2 + 2Q2R2 + 2R2P2 - P4 - Q4 - R4)/4P2;
(1) + (4) - (5) gives: 2ae = P2 + L2 - M2, or e = (P2 + L2 - M2)/2P;
(2) + (4) - (6) gives: Q2 + L2 - N2 = 2de + 2bf, so 2bf = Q2 + L2 - N2 - (P2 + Q2 - R2)(P2 + L2 - M2)/2P2;

Finally, a4b2c2 = a4b2(L2 - e2 - f2) = a2(a2b2)L2 - (a2b2)(a2e2) - a4(bf)2. Substituting the results already obtained and multiplying out, gives 16a4b2c2 as a sum of almost 100 terms. Most of these cancel and we are left with the result quoted.

I subsequently discovered that there are several better ways of doing this problem. First, we can get (a variant of) the tetrahedral formula more easily using vectors.

Take one of the points at the origin and the vectors to the other three points as a, b, c. The volume V = |a.(b x c)|. Expressing as a matrix and multiplying by its transpose gives V2 = det X, where X is the 3 x 3 matrix with first row a.a, a.b, a.c, second row b.a, b.b, b.c, third row c.a, c.b, c.c. Now using 2a.b = a2 + b2 - |a - b|2 etc, we get 8V2 = det Y, where Y is the 3 x 3 matrix with first row 2a2, a2 + b2 - z2, a2 - y2 + c2, second row a2 + b2 - z2, 2b2, -x2 + b2 + c2, third row a2 - y2 + c2, -x2 + b2 + c2, 2c2 (and x is the distance from the tip of vector c to the tip of vector b etc). Now since odd squares are 1 mod 8, we get immediately that 8V2 = 4 mod 8, which is impossible.

There are many variants on this, some using explicitly the angles in the figure.

Many thanks to Ignacio Larrosa Cañestro for prompting me to look at this again.