# Using the pigeonhole principle to prove there is at least two groups of people whose age sums are the same.

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?

• 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

## 1 Answer

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

• 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
• @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