2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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