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.