Prove or disprove whether there exists two subsets of $X$ such that sum of all the elements in each of these set is same

combinatoricspigeonhole-principleproof-verification

Let $X\subset\{1,2,\ldots 100\}$ be set with cardinality $10$. Then I need to prove or disprove whether there exist two subsets of $X$ such that the sum of all the elements in either of these sets is the same.

Total number of subsets of $X$ = $2^{10} =1024$

Also, the maximum sum of elements in a subset of $X$ can be $100+99+\ldots 91 = 955$

So by the pigeonhole principle, there must exist at least $\big\lceil\frac{1024}{955}\big\rceil= 2$ subsets that have the same sum

Is this correct?

Best Answer

Strictly speaking there are $956$ possible sums from $0$ to $955$. (You included the empty set in your 1024 sets.)

Other than that your proof is extremely good and clearly expressed.

Related Question