0

So the question is pretty simple if we have a set of 10 random numbers, how do we prove that we can make 2 subsets of any length such that the sum of numbers in each subset adds up to each other? The numbers in each subset must also not be reused. I am just looking for ways to approach this problem since it has left me confused. I have been trying to use proof by contradiction, but that hasn't worked out.

EDIT: Random numbers from 1 to 100 inclusive.

Rohan Harish
  • 1
  • 4
    If the numbers are (for example) $1, 2, 4, 8, \ldots, 512$ then you can not make two subsets with the same sum. – You can construct more examples by making each numbers in the list larger than the sum of all preceding numbers. – Martin R Mar 25 '21 at 00:51
  • Yes!! That's what I was thinking! I forgot to mention that the 10 random numbers are in the range 1 to 100 (inclusive), so my thought process was: the only way it doesn't work is with 2^n, but it goes to more than 100. Hence, proved that it always works? – Rohan Harish Mar 25 '21 at 01:16
  • You should have mentioned the fact that the 10 random numbers are between 1 and 100. That is an important detail. – Kyan Cheung Mar 25 '21 at 01:19
  • Here are two similar questions: https://math.stackexchange.com/q/709271/42969, https://math.stackexchange.com/q/4071971/42969. The general idea is to use a pigeon-hole principle type argument. – Martin R Mar 25 '21 at 01:22

1 Answers1

1

As was said in the comments we have $10^{10}=1024$ subsets and the sums are all in the range $[0,10\times100]$ so by the pidgeonhole principle at least one quantity must be the sum of two distinct subsets.

Asinomás
  • 105,651
  • This makes sense but say if it was 7 numbers instead. Then by pigeon hole it would be true, but if we use 2^0 - 2^6 it would be false. – Rohan Harish Mar 25 '21 at 19:24