Can prove that any random numbers between 1-100 can be divided into two equal partially sum groups?

Can you prove that any 10 random numbers between 1-100 (No duplications) can be divided into two groups of numbers in which the sum of some (one or more) of the numbers from one group would be equal to the sum of some (one or more) of the number from the other group?

For example: I've got the numbers (1, 72, 2, 3, 5 , 99 ,22, 13, 17, 45). I can divide it into (1, 2, ... ) and (3, ...) and 1 + 2 = 3.

• This shouldngo on math.se – user17008 May 30 '16 at 15:50
• I imagine the largest distinct set for 1-100 is 7 (think binary representations), though I'm not currently of a state of mind where I'd be able to hammer out a proof. – Ian MacDonald May 30 '16 at 15:58

We

can always find a way to partition the random set of $10$ unique numbers from $[1,100]$ into two sets such that a non-empty subset of each have the same sum ("satisfy the property").

Proof

If we can find a set which does not satisfy the property, then all the sums of subsets sized between $1$ and $5$ must sum to unique results.  The number of such subsets is
\begin{align}\sum_{i=1}^5\binom{10}{i} &=\frac12\left(\quad\left(\sum_{i=0}^{10}\binom{10}{i}\right)\quad-\binom{10}{0}-\binom{10}{10}+\binom{10}{5}\right)\\[1.5ex] &=\frac12\left(2^{10}-1-1+\frac{10\times9\times8\times7\times6}{5\times4\times3\times2}\right)\\[1.5ex] &=637\end{align} Each sum is also necessarily an integer between $1$ (the sum of the subset $\{1\}$) and $490$ (the sum of the subset $\{96,97,98,99,100\}$).
So such a set would need to yield subsets with $637$ sums unique across $490$ integers, but $637>490$; hence, no such set exists.

• Oh this is the same as @ghosts_in_the_code's answer (maybe worded better), didn't notice. – Jonathan Allan May 30 '16 at 23:48

Let us assume that there exists a set which cannot be partitioned into two subsets with equal sums. Now if we select any subset, we will always get a sum that is unique. Hence, if we count the number of subsets with at most 5 elements, we get $C^{10}_1 + C^{10}_2 + C^{10}_3 + C^{10}_4 + C^{10}_5 = 10+45+120+210+252=637$

Hence we should have 637 unique sums. However the sum of 5 numbers cannot exceed 490. (Because the numbers can at most be 100,99,98,97,96)

Hence no such set exists.

• (1) This is very unclear. I can’t tell whether you are proving that the statement is true or false! What do you mean by “create such a set”? (2) When you say “almost 5”, do you mean “at most 5”? (3) Please use spoiler blocks. – Peregrine Rook May 31 '16 at 6:42
• @PeregrineRook I've edited a bit to make it clearer. Yes, I meant at most 5 only (autocorrect error). Thanks for pointing out. The q asks for a proof that no such set exists, it doesn't ask whether such a set exists or not (so hopefully that's anyway clear enough). As for spoiler blocks, I don't know if they are really required for a proof like this, it may be classified as overuse of spoilers. – ghosts_in_the_code May 31 '16 at 7:30
• I think the wording is a bit weird. you talk about 'such a set'. At first I would think that it means 'a set that has the property' but you actually mean 'a set that doesn't have the property'. Also, at first It wasn't clear to me why such a set must have unique sums, you might want to explain why that is so – Ivo Beckers May 31 '16 at 9:09
• @IvoBeckers I hope it's ok now – ghosts_in_the_code Jul 2 '16 at 16:26