Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Jason DeVito Dec 9 '12 at 3:29
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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? –  Wooooop Dec 9 '12 at 3:22
1  
@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.) –  Brian M. Scott Dec 9 '12 at 3:37
    
@BrianM.Scott, ooh alright, so the 1024 subsets are the pigeons, but what would be the pigeonholes? All the possible sums? –  Wooooop Dec 9 '12 at 4:03
    
@kevlar: Yes; the possible sums range from $0$ through $1000$, so how many of them are there? –  Brian M. Scott Dec 9 '12 at 4:04
    
OH! So there are 1001 pigeonholes and 1024 pigeons! Got it! Thank you Brian! –  Wooooop Dec 9 '12 at 4:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.