In a room there are 10 people, none of whom are older than 100 (ages are given in whole numbers only) but each of whom is at least 1 year old. Prove that one can always find two groups of people (possibly intersection, but different) the sums of whose ages are the same.

I know we have to use the pigeon hole principle. But I don't know how to find the pigeons and pigeonholes. Can someone help me out?

  • 4
    $\begingroup$ It seems as though if you can solve it with possible intersection, you can solve it without intersection: If you remove the same person from two sets whose sum of ages are the same, the sum of ages stays the same. $\endgroup$ – Jason DeVito Dec 9 '12 at 3:29

Hint: what is the maximum sum of all the ages in the room? How many subsets are there of people in the room?

  • $\begingroup$ So the max sum of ages is 1000 ( ten people and they all can be 100 yrs. old). And the number of subsets is 2^(10) - 1? $\endgroup$ – Wooooop Dec 9 '12 at 3:22
  • 1
    $\begingroup$ @kevlar: Almost. That’s the number of non-empty subsets; there are $2^{10}=1024$ subsets altogether, including $\varnothing$, and nothing in the problem rules it out. (Of course it’s also of no use, since its sum of $0$ can’t be duplicated by any of the non-empty subsets, but it does count as one of the pigeons.) $\endgroup$ – Brian M. Scott Dec 9 '12 at 3:37
  • $\begingroup$ @BrianM.Scott, ooh alright, so the 1024 subsets are the pigeons, but what would be the pigeonholes? All the possible sums? $\endgroup$ – Wooooop Dec 9 '12 at 4:03
  • $\begingroup$ @kevlar: Yes; the possible sums range from $0$ through $1000$, so how many of them are there? $\endgroup$ – Brian M. Scott Dec 9 '12 at 4:04
  • $\begingroup$ OH! So there are 1001 pigeonholes and 1024 pigeons! Got it! Thank you Brian! $\endgroup$ – Wooooop Dec 9 '12 at 4:09

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.