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