9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This shouldngo on math.se $\endgroup$ – ev3commander May 30 '16 at 15:50
  • $\begingroup$ 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. $\endgroup$ – Ian MacDonald May 30 '16 at 15:58
7
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ (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. $\endgroup$ – Peregrine Rook May 31 '16 at 6:42
  • $\begingroup$ @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. $\endgroup$ – ghosts_in_the_code May 31 '16 at 7:30
  • 1
    $\begingroup$ 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 $\endgroup$ – Ivo Beckers May 31 '16 at 9:09
  • $\begingroup$ @IvoBeckers I hope it's ok now $\endgroup$ – ghosts_in_the_code Jul 2 '16 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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