7
$\begingroup$

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?

  • 0
    @SandeepSilwal: It is to justify the use of the word "the" in the statement: "_the_ eigenvector corresponding to the eigenvalue $0$" (though technically the never applies, and we are talking about number of vectors in the basis of the eigenspace/dimension of the eigenspace).2016-08-11

1 Answers 1

7

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.)

  • 0
    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.2010-09-24