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
    Does it count as linear algebra to use precalculus-level techniques for solving linear systems (e.g. linear combinations of equations)?2010-09-23
  • 0
    @Isaac: Yes I would say it is linear algebra, but what did you have in mind?2010-09-23
  • 0
    Is there a source for the problem (even in the integer case)?2010-09-23
  • 0
    I believe it is an exercise in the book by Babai and Frankl: http://books.google.com/books?id=zhEmHQAACAAJ2010-09-23
  • 0
    @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.2010-09-23
  • 0
    @Isaac: r_k = 0 or r_k = r_j? I don't think you can prove r_k = 0.2010-09-23
  • 0
    The problem, but with the restriction that the numbers are integers, was B-1 on the 1973 Putnam exam.2012-07-03
  • 0
    @Aryabhata: How does A having rank at least 2n imply the result? Can't we just say let A be a matrix with 0s on the diagonal and $\pm 1$ everywhere else where the rows represent our $2n + 1$ linear equations. Then the eigenvector corresponding to the eigenvalue $0$ is $\{r_1, \ldots, r_{2n + 1} \}$. However, $\{1, \cdots, 1 \}$ is also an eigenvector of $0$ which implies that $\{r_1, \ldots, r_{2n + 1}\} = c \cdot \vec{1}$2016-08-11
  • 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
    +1: Perhaps we can use the fact that the rationals are dense etc and bring analysis into the picture.2010-09-23
  • 0
    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.2010-09-23
  • 0
    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.2010-09-23
  • 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