1
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $C$ has $2^{10} = 1024$ subsets, and $max(\sum C) = 975$ $\endgroup$ – Oria Gruber Dec 3 '13 at 16:52
  • $\begingroup$ OK, your subsets are pigeons $\endgroup$ – Ross Millikan Dec 3 '13 at 16:55
  • $\begingroup$ Yeah I got that :) thanks, it's very clear now. top answer. $\endgroup$ – Oria Gruber Dec 3 '13 at 16:55
  • 1
    $\begingroup$ @GinKin: Each element of $C$ can be in the subset or not. Two choices for one element, $2^{10}$ for $10$ of them. $\endgroup$ – Ross Millikan Dec 3 '13 at 19:59
  • 1
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Dec 3 '13 at 20:08

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.