# pigeonhole question with sets and sum of numbers

This question is meant to be solved with pigeonhole principle. But I can't solve it. I just can't figure out what is the pigeon and what is the pigeon hole. I don't really have a clear direction.

Definition: if $X$ is a set of non-negative integers, $\sum X$ is defined to be the summary of all the elements of $X$, for example: if $X =\{2,7,13,20\}$ then $\sum X = 2+7+13+20=42$

Question: let $C \subset \{0,1,2,...,102\}$, $|C| = 10$ ($C$ has 10 elements).

Show that there are sets $A,B \subset C$, such that $A \neq B \neq \emptyset$ and $\sum A = \sum B$

## 1 Answer

Hint: how many subsets of $C$ are there? What is the maximum for $\sum C$?

• $C$ has $2^{10} = 1024$ subsets, and $max(\sum C) = 975$ – Oria Gruber Dec 3 '13 at 16:52
• OK, your subsets are pigeons – Ross Millikan Dec 3 '13 at 16:55
• Yeah I got that :) thanks, it's very clear now. top answer. – Oria Gruber Dec 3 '13 at 16:55
• @GinKin: Each element of $C$ can be in the subset or not. Two choices for one element, $2^{10}$ for $10$ of them. – Ross Millikan Dec 3 '13 at 19:59
• @GinKin: Any $10$ element set has $2^{10}$ subsets. The number $102$ doesn't come in to it. We needed $102$ to make sure $\sum C$ was small enough that there weren't too many pigeonholes. – Ross Millikan Dec 3 '13 at 20:08