# Odd number of reals with equal partitions

Consider the following problem:

You are given a multiset (a set with repetitions allowed) of $2n+1$ real numbers, say $S = \{r_1, \dots, r_{2n+1}\}$.

These numbers are such that for every $k$, the multiset $S - \{r_k\}$ can be split into two multisets of size $n$ each, such that the sum of numbers in one multiset is same as the sum of numbers in the other.

Show that all the numbers must be equal.( i.e. $r_{i} = r_{j}$)

Please stop reading further if you want to try and solve this problem.

Spoiler:

Now this problem can easily be solved using Linear Algebra. We have a set of $2n+1$ linear equations, which corresponds to a matrix equation $Ar = 0$. It can be shown that $A$ has rank at least $2n$ which implies the result.

The question is, is there any solution to this problem which does not involve any linear algebra?

• Does it count as linear algebra to use precalculus-level techniques for solving linear systems (e.g. linear combinations of equations)? – Isaac Sep 23 '10 at 17:08
• @Isaac: Yes I would say it is linear algebra, but what did you have in mind? – Aryabhata Sep 23 '10 at 17:09
• Is there a source for the problem (even in the integer case)? – T.. Sep 23 '10 at 18:03
• I believe it is an exercise in the book by Babai and Frankl: books.google.com/books?id=zhEmHQAACAAJ – Aryabhata Sep 23 '10 at 18:16
• @Moron: I had in mind some sort of clever trick of adding up all the equations in such a way that nearly every instance of nearly every r_k cancelled out and left something that made it obvious that r_k=0 for each k (e.g. when you add all the equations and divide by 2 to solve a+b=k1, b+c=k2, c+a=k3). In thinking about it more, it's less clear to me what the clever arrangement would be, though. – Isaac Sep 23 '10 at 18:34

You can't avoid some sort of algebra, because the statement is false in a commutative group where $nx = 0$ has nontrivial solutions.
If $\Sigma$ is the sum of all elements, $\Sigma - r_i$ is even and thus all $r_i$ have the same parity. We can replace each $r_i$ by $(r_i-r_k)/2$ and get a smaller solution, where $r_k$ is the smallest of the numbers. This process ends at the zero solution, and is reversible, so the original solution has all numbers equal.
• I think that any use of inequalities or 2-adic valuation will be finitary for given $n$, so no analysis. I'm pretty sure that you only need reduction mod 2^n or 2^(2n+1), for example, rather than the 2-adic numbers as a whole. But there could be an easier way of describing a finitary argument, using the language of analysis. – T.. Sep 23 '10 at 18:31