Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
See this question on this very site: math.stackexchange.com/questions/5314/… where I outline a solution in the question and T.. gives a solution in his answer (which also answers this). –  Aryabhata Jan 25 '11 at 19:27
    
@Moron: In the linear algebra solution you mentioned, how does one show that the rank of the matrix is 2n? –  Benji Jan 25 '11 at 19:55
1  
Not to mention this question: cstheory.stackexchange.com/questions/4476/… –  mjqxxxx Jan 25 '11 at 20:18
1  
@mjq: That is the cstheory post I was referring to in my answer :-) –  Aryabhata Jan 25 '11 at 20:27
    
@bobo: One way is to consider a submatrix of size 2nx2n and show the determinant is non-zero. Another way is to show that the coefficient of the linear term in the characteristic polynomial is non-zero, by showing that it is odd (derangements comes into play here). –  Aryabhata Jan 25 '11 at 20:30

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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