0

You generate a list of random 5-digit integers between 10000 and 99999. What is the smallest number of integers in your list to guarantee two subsets of the integers have the same sum?

I know that there are $2^n$ subsets where $n=|A|$ and $A$ is the set of randomly generated integers.

As per the pigeonhole principle, first I tried to find cardinality to compare but I don't know the number of elements in the list. I also tried to figure out the maximum sum, which is 99999$n$ since there are at most $n$ elements in the set $A$ and each of those elements could be 99999.

I didn't get far as I couldn't really find a relation to apply the pigeonhole principle. I came up with $99999n\geq 2^n$ but I don't really see how that's even making sense.

Hedylove
  • 570
  • 1
    I agree you can use the pigeonhole principle to start solving this problem: e.g. you know there cannot be duplicates in the list, which would lead to subsets of size 1 having the same sum. When I solved the simpler problem involving one-digit integers 1...9, I found that the list of powers of two [1, 2, 4, 8] is as long as possible without having any subset sums. Maybe something like 10000 + 2^n will work here? – user326210 Dec 12 '17 at 09:29
  • Try reversing the inequality. Also note that there is a restriction on the minimum sum. – nickgard Dec 12 '17 at 14:36

0 Answers0