Solutions to "An Elephant Problem"

In the last issue of PUrview, we posed the following problem: An animal trainer has 13 elephants with the property that whenever any single elephant is taken aside, the remaining 12 can be separated into two groups of six of equal weight. Show that all 13 elephants must weigh exactly the same. Below are solutions provided by Professors Lempert and Golomb.

Solution 1

1. Assume first that each elephant weighs an integer number (of pounds, say). We shall show that all the weights are equal by the method of ³infinite descent.²

Consider the total weight T of all the elephants. If T is odd, then each individual weight also must be odd. Indeed, an individual weight equals T minus the total weight of the 12 leftover elephants; but this latter is even according to the problem, and odd minus even is odd. The same argument also shows that if T is even then so are all the individual weights. Thus, either all the weights are even, or all are odd.

If all weights are even, replace each elephant by one that weighs half as much. If all weights are odd, replace each elephant by one that weighs one pound less. Either way, we obtain a collection of elephants that still satisfy the requirements of the problem, but are lighter than the elephants we started with. Moreover, we can repeat this procedure and lose more and more pounds . . . but not indefinitely (because the weights are nonnegative integers)! At one point we must arrive at weights that do not go down any more. This happens only if all the weights are 0, in particular equal. Now it is easy to convince oneself that the weights had to be equal immediately before they were reduced to 0, and also immediately before that stage, and so on. They had to be equal right from the beginning!

2. Should the elephants have rational rather than integer weights, one can multiply the weights by a common denominator. Now the weights are integers, and part 1 implies they must be equal.

3. But what if the weights are just (nonnegative) real numbers? Then you have to use higher math, e.g. linear algebra.

First we again tinker with the weights as follows. We take away the same weight from each elephant so that the lightest now becomes weightless. If at this point not all the weights are zero, then divide each weight by the same number so that one weight becomes 1. Thus the weights are now 0, 1, x1, ..., x11, and they still satisfy the requirements of the problem. These requirements can be expressed as a system of 13 linear equations involving x1, ..., x11; all coefficients will be either 0, +1, or ­1.

Linear algebra tells you that if a system of linear equations with rational coefficients admits a real solution, then it also admits a rational solution. However, this translates back to having 13 elephants of rational but unequal weights subject to the requirement of the problem (unequal because 0 and 1 are among them). Yet this contradicts our findings in part 2. There is only one way to resolve the contradiction. It is to admit that when the same weight was subtracted from the elephants to make one of them weightless, all the others became weightless, too. But that means they started out weighing the same, q.e.d.

Laszlo Lempert

Solution 2

Let x1, x2, ..., x13 be the weights of the elephants, arranged so that xi (i = 1, 2, ..., 13) is the weight of the ith elephant taken aside. According to the problem, we have the following linear homogeneous system of equations:

In each equation, half of the signs are +, the other half are ­. The matrix of the coefficients of system (*) is

Again in each row, half of the signs are +, the other half are ­.

Adding up the column vectors of M, one obtains the zero vector; hence M is singular and system (*) has at least one nontrivial (i.e. non-zero) solution. The obvious solution is xi = x1(i = 2, ..., 12), where xi is any non-zero number.

Are there other solutions? To decide this, we look at the minor ML of M, which is obtained by deleting the last row and last column. We show that ML is nonsingular, hence M has rank 12, nullity 1, and system (*) has only one linearly independent solution.

A simple way of deciding that ML is nonsingular is to look at it modulo 2. If ML is nonsingular (mod 2), it is nonsingular. ML is singular (mod 2) if and only if some of its column vectors add up to the zero vector. The components of ML (mod 2) are 0 along the main diagonal and 1 everywhere else. The sum of all column vectors (mod 2) is the vector all of whose components are 1. If k < 12 column vectors are added up, then a vector with k (or 12-k) 0¹s and 12-k (or k) 1¹s is obtained. This is so because k rows of the chosen k vectors have a single 0, while the remaining 12-k rows have only 1's.

This concludes the proof.

Michael Golomb