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.


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?

  • $\begingroup$ Does it count as linear algebra to use precalculus-level techniques for solving linear systems (e.g. linear combinations of equations)? $\endgroup$ – Isaac Sep 23 '10 at 17:08
  • $\begingroup$ @Isaac: Yes I would say it is linear algebra, but what did you have in mind? $\endgroup$ – Aryabhata Sep 23 '10 at 17:09
  • $\begingroup$ Is there a source for the problem (even in the integer case)? $\endgroup$ – T.. Sep 23 '10 at 18:03
  • $\begingroup$ I believe it is an exercise in the book by Babai and Frankl: books.google.com/books?id=zhEmHQAACAAJ $\endgroup$ – Aryabhata Sep 23 '10 at 18:16
  • $\begingroup$ @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. $\endgroup$ – 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 you allow use of the linear algebra fact that rank is the same over any field containing the coefficients of the equations, it is enough to consider rational (and thus integer) solutions and extra structure is available. One can then avoid use of determinants or matrices:

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.

(added: you can consider this a use of either the real or 2-adic metric on integers, so this must correspond to a linear algebra argument using inequalities or reduction mod 2^(2n+1) on the system of equations or its determinant.)

  • $\begingroup$ +1: Perhaps we can use the fact that the rationals are dense etc and bring analysis into the picture. $\endgroup$ – Aryabhata Sep 23 '10 at 18:28
  • $\begingroup$ 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. $\endgroup$ – T.. Sep 23 '10 at 18:31
  • $\begingroup$ I have no clue what a finitary argument is. I think I know what 2-adic means, but it has been a long time since I read about those things. $\endgroup$ – Aryabhata Sep 23 '10 at 18:54
  • $\begingroup$ For example, you could use analysis by writing the equations as a system v=Mv where vector v records the differences between the r_i and M is a contraction. Then v is the limit of (M^n)v, which is zero. However, in this setting you can also note that there is a fixed value of k>0 (e.g., I think k=2 works in this problem) so that looking at (M^k)v you find that the largest nonzero component v_m of v would have to satisfy |v_m| < |v_m|, and the result is attainable without passing to the limit. So the same proof idea can be expressed in "finitary" or in "analytic" language. $\endgroup$ – T.. Sep 24 '10 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.