Solution to equal coins puzzle

This has solutions to the Equal coins puzzle posted earlier.

A brief description of the problem:

There are $2n+1$ reals numbers, $r_1, r_2, \dots, r_{2n+1}$. Given any $r_i$, you can split the remaining $2n$ into two groups of $n$ each, such that the sum of elements of one group is the same as the sum of elements of the other group.

Show that $r_i = r_j$ (i.e. all must be equal).

Solutions

---

All the solutions that I know use Linear Algebra (if you know/can think of one without using Linear Algebra, please share!).

Solution 1)

This is the solution I had come up with when I first saw this problem.

The property basically means that there is a $(2n+1)\times(2n+1)$ matrix $A$ such that

Every row of $A$ has exactly $n$ ones and $n$ minus ones.

The main diagonal of $A$ is $0$

$Ax = 0$ has a non-trivial solution.

Since $x = [1,1, \dots, 1]$ is an obvious solution, in order to show that all the coins/real numbers must be equal, it is enough if we show that the rank of $A$ is $2n$.

Consider the characteristic polynomial of $A$, $P_{A}(t) = \det(A - tI)$.

It is enough to show that coefficient of $t$ in $P_{A}(t)$ is non-zero.

Consider the formula for the determinant of an $N \times N$ matrix $M$

$$\det M = \sum_{\sigma} \text{sign}(\sigma)\prod_{i=1}^N M_{i\sigma(i)}$$

where $\sigma$ runs over the permutations of $\{1,2, \dots, N\}$ and $\text{sign}$ gives the sign (based on the parity of the permutation).

For the $P_{A}(t)$, the coefficient of $t$ is given by those permutations such that there is exactly one $i$ such that $\sigma(i) = i$.

Since each product $\prod A_{j \sigma(j)}$ is $\pm 1$, the coefficient of $t$ is a sum of ones and minus ones.

It is thus enough to show that there is an odd number of such permutations.

This number is basically $(2n+1)D_{2n}$, where $D_{2n}$ is the number of derangments of $1,2 \dots, 2n$!

This is easily shown to be odd (based on a recursive formulas) and is left as an exercise :-).

I was quite happy with this solution, when Professor David Zuckerman of UT Austin showed me this neat proof:

Solution 2)

Like 1), we start with matrix $A$, but consider it over $\mathbb{F}_2$, the field of ${0,1}$. One can show that $rank(A)$ over $\mathbb{R} \ge rank(A)$ over $\mathbb{F_2}$.

Now use the fact that $rank(A) + rank(B) \ge rank(A+B)$

In $\mathbb{F}_2$, A is just the all ones matrix, except the diagonal, which is all zeros.

To that, we add the all ones matrix $B$, giving the identity. The all ones matrix $B$ trivially has rank 1.

Thus we get $rank(A) + 1 \ge 2n+1$.

Since $rank(A) \ne 2n+1$ (it has a non-trivial solution), we are done.

And the third solution, which is quite neat too and generalizes to $kn+1$ numbers.

Solution 3)

First assume that the $r_i$ were integers. We can also assume they are all non-negative, as adding a fixed constant does not change the property.

Now consider the $r_i$ which has the smallest maximum.

If $S = r_1 + r_2 + \dots + r_{2n+1}$, then the property gives us that $S = r_i \mod 2$ for every $i$.

Thus all are even or all are odd. If all are even, we can divide by $2$. If all are odd, we can subtract the smallest number.

Thus they must be equal. This easily extends to the case when the numbers are rational.

Now the Linear Algebra application: the reals are a vector space over the rationals! (See Hamel Basis). Writing the reals as a (finite) linear combination of the basis numbers, with coefficients in $\mathbb{Q}$, gives us that the coefficients of each basis vector/number should satisfy similar properties, and thus must be equal, implying the $r_i$s are equal!