The only possible solution is that all the elephants have the same weight.
If we think of the elephant weights as being variables labeled W1 through W13, then the facts about the elephants can be summarized in a linear system of the form A*W=0, where in each row of A, the diagonal entry is zero, 6 entries are +1, and the remaining 6 entries are -1.
From this, we can see that A is a singular matrix. If we look at A as a collection of column vectors, then the sum of the column vectors is the zero vector. (The first entry of this sum is the sum of the entries in row 1, for instance.) But the process of summing the entries in a row of a matrix is equivalent to multiplying the matrix times a vector of all 1's: A*1=0, which means that A is singular. And, perhaps surprisingly, that's good, because the linear system A*W=0 has a nonzero solution if and only if the matrix A is singular.
So it seems that all we've established by this argument is the obvious, namely, that there is at least one solution, in which all the weights of the elephants are equal. (They don't have to weigh 1 pound, of course. If x is a solution to a singular linear system, then so is any multiple of x.)
We already knew there was one kind of solution. We want to know if there are any other solutions. The answer is no, and the reason can be shown using the same matrix analysis. The solution x that we found is one vector in the null space of A. There are other solutions (that are not multiples of the first one) if and only if this null space has dimension 2 or greater. If we can show that the null space has dimension 1, we are done.
We try to show that the null space has dimension 1 by showing that there is some 12 by 12 minor matrix that has full rank. We will guess that it doesn't matter which minor we look at, so we simply delete the 13th row and column of the original matrix A to create a new matrix B.
Now we need to use the following fact:
If a matrix is nonsingular modulo 2, then it is nonsingular.
Using modulo 2 arithmetic, our matrix B is equivalent to a matrix which is 0 on the diagonal and 1 everywhere else. This matrix is singular modulo 2 if there is some vector y of 0's and 1's so that B*y=0, mod 2. This is equivalent to saying that we can add some subset of the column vectors to get a zero vector.
If we add all 12 of the columns, we get a vector of 1's (because there are 11 1's in each row, which sum to 11, which is equal to 1 modulo 2.) So that's not a way to get zero.
Now suppose we add together k of the columns, where k is less than 12. Then if k is even, there are exactly k entries of the sum where an odd number of 1's were added to get 1, (because each column we use in the sum has a zero that is unique in its row). Since k isn't zero, we know that the sum can't be the zero vector. If k is odd, then there is at least one row of the sum in which none of the columns being added had a zero. Hence the value of that entry of the sum is the value of k 1's, modulo 2. And since k is odd, that value will be 1.
Thus, there is no way to construct the zero vector by adding columns of the minor matrix, modulo 2. Hence the minor matrix is nonsingular modulo 2. Hence the minor matrix is nonsingular, and so it has rank 12. Hence the original matrix must have rank at least 12. But it can't have rank greater than 12, since it has a null vector. Hence it has rank exactly 12, there's one null vector, and there are no other solutions to the problem.
This puzzle appeared in the Spring 2000 issue of PUrview, the newsletter of the Purdue Mathematics Department. Solutions appeared in the Summer 2000 issue. The solution discussed here was given by Professor Michael Golomb.
Last revised on 19 December 2000.