# 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, 2016 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. May 30, 2016 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. May 30, 2016 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. May 31, 2016 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. May 31, 2016 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
May 31, 2016 at 9:09
• @IvoBeckers I hope it's ok now Jul 2, 2016 at 16:26