How many subsets of $\{1,2,3,\dots,10\}$, each containing at least 3 and at most 5 elements, must be selected in order to ensure that the selection contains three subsets $A , B , C\subset \{1,2,\dots,10\}$ such that sums of elements of each of the subsets are equal?
35 sums are possible, from minimum sum 6 (for the subset $\{1,2,3\}$) to maximum sum 40 (for the subset $\{6,7,8,9,10\}$). So by the Pigeonhole Principle, at least 71 sets must be chosen to ensure there are three with equal sums. But in the book where I found this question, the answer is given as 67. Where am I wrong?
Best Answer
The question seems to be requiring that the subsets be distinct. In this case, certain sums can only be attained in one way, and it is thus impossible to put two pigeons in these pigeonholes, reducing the count.
Explicitly:
You can only fit one pigeon in each of these pigeonholes. The other 31 numbers can fit two or more. Then the maximum number of pigeons without any pigeonholes having three is $4+2*31=66$. Hence 67 guarantees three pigeons in some hole.