3
$\begingroup$

Take 13 integers. Prove that if any 12 of them can be partitioned into two sets of six each with equal sums, then all the integers are the same.

Does anyone know if the general case with 2n+1 integers and sets of n integers results in the same conclusion?

  • 0
    The problem with an arbitrary number of integers was B-1 on the 1973 Putnam exam.2011-04-30

2 Answers 2

4

This is true for arbitrary reals and arbitrary splits. A recent answer I posted on cstheory:


To answer the more general question,

Given any positive integers $\displaystyle k$ and $\displaystyle n \gt 1$, if there are $\displaystyle kn+1$ real numbers $\displaystyle r_i$, such that for any $\displaystyle i$, all except $\displaystyle r_i$ can be split into $\displaystyle n$ groups of $\displaystyle k$ each, such that the sum of the reals in any group is the same as any other, then $\displaystyle r_i = r_j$.

This is true.

Instead of reals, start with integers.

Notice that if $\displaystyle S$ is the total sum, then $\displaystyle S = r_i \mod n$ and so $\displaystyle r_i = r_j \mod n$.

wlog assume $\displaystyle r_1$ is the smallest.

Then we have a new set of weights

$\displaystyle \frac{r_i - r_1}{n}$ which has lower $\displaystyle \text{max}\{r_i\}$ (note all have become non-negative so we can assume they were non-negative to begin with) and hence we end up with all zeroes. Since this is reversible, the original must have been equal.

Thus if the weights were integers, they all have to be the same. This easily extends to rationals weights.

Now since $\displaystyle \mathbb{R}$ is an infinite dimensional vector space over $\displaystyle \mathbb{Q}$, we are done. (Search the web for Hamel Basis).

3

They must all be even or all be odd. If not, you could find a set of 12 with odd sum and could not divide it evenly. Now subtract 1 if they are odd, then divide by 2, and make the same argument, so they are the same mod 4. Repeat.

Added based on Moron's answer: I think this (sort of) works for infinite sets as well. If you use cardinals and cardinal addition, as long as $\frac {n+3}{2}$ are the same ($\kappa$)and the rest are smaller, the sum of each subset will be $\kappa$ and you are done. But in ordinals (using ordinal addition) you can go through the same argument with Cantor normal form.