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.

Improve this question
$\endgroup$
2
  • $\begingroup$ This shouldngo on math.se $\endgroup$
    – user17008
    May 30, 2016 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, 2016 at 15:58

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh this is the same as @ghosts_in_the_code's answer (maybe worded better), didn't notice. $\endgroup$
    – Jonathan Allan
    May 30, 2016 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.

Improve this answer
$\endgroup$
4
  • 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, 2016 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, 2016 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
    May 31, 2016 at 9:09
  • $\begingroup$ @IvoBeckers I hope it's ok now $\endgroup$
    – ghosts_in_the_code
    Jul 2, 2016 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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