3
$\begingroup$

Let S be a set of 10 positive integers ≤ 50. Show that there two different (but not necessarily disjoint) subsets of four integers such that the sums of the 4 integers in the sets are equal.

Having problems identifying which should be the pigeon-hole. Would appreciate some help here.. Thanks

$\endgroup$
3
$\begingroup$

Hint: There are $\binom{10}{4}$ different subsets of size four but only $200$ possible sums.

$\endgroup$
  • 1
    $\begingroup$ why will there be only 200 possible sums? $\endgroup$ – qwerty23 Sep 27 '14 at 5:36
  • 1
    $\begingroup$ Min sum is $4$, max sum is $200$, the possible sums cannot exceed $200$. Note we don't need the exact count. $\endgroup$ – Macavity Sep 27 '14 at 5:42

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.