# How to apply pigeonhole principle to this problem?

There are 33 students in the class and sum of their ages 430 years. Is it true that one can find 20 students in the class such that sum of their ages greater 260 ?

My approach:

The average age of each student comes out to be 13.03 If each student has an age equal to 13.03 i.e. the average age of the class, it comes out to be 260.60

The class might have students with age greater than or less than or equal to the average age of the class. So it is always possible to select some 20 students whose sum of the age adds up to 260.

I don't know if I am correct in my approach. Is there a way in which we can depict and solve this problem using pigeon hole principle?

-

I'm not sure what you are doing (or what the pigeonhole principle is), but the average age of the whole class is 430/33 =~ 13.03. It follows that the average age of the oldest 20 students in the class must be at least 13.03. Hence their aggregate age must be at least as high as 20 * 13.03 > 260. QED.

-
Thanks Martin. Corrected the typo. – user1631009 Oct 10 '12 at 16:24

Suppose the contrary, i.e. that the total age of any subset of 20 students is less than 260 years. By adding together the total age of all these subsets, we get a number

$$N < \binom{33}{20}\cdot 260.$$

Since every student belongs to $\binom{33}{20}-\binom{32}{20}=\binom{32}{19}$ subsets of 20 students, we have:

$$430 \cdot\binom{32}{19} = N < 260\cdot\binom{33}{20}$$

that is impossible, since:

$$430 > 260\cdot\frac{33}{20} = 429.$$

-

I don't think I've used the pigeonhole principle, but the following is one possible solution.

Suppose that no $20$ students have an age sum greater than $260$. Let $S$ denote the group to $20$ with the largest age sum. If we denote $x$ to be the total age sum of $S$, then by assumption $$x \le 260$$ Note that the average age of $S$ is less than or equal to $13$, so that there must be a student younger than $13$. If not then $S$ is composed of $20$ students of age $13$. The remaining $13$ students must also be younger than or equal to $13$ otherwise we can swap for a larger $x$ in $S$. But then that means the net age sum satisfies $$430 \le 260 + 13\times 13 = 429$$ which is a contradiction.

So suppose there is a student younger than $13$ in $S$. This means that the remaining $13$ students must also be younger than $13$. Again, the net age sum satisfies $$430 < 260+13\times 13 = 429$$ which is a contradiction.

-