# combinatorics: The pigeonhole principle

Assume that in every group of 9 people, there are 3 in the same height.

Prove that in a group of 25 people there are 7 in the same height.

I started by defining:

pigeonhole- heights. pigeons-people.

I do not know how to use the assumption.

thanx.

-

Let $n_i$ be the number of people of height $x_i$. Without loss of generality $$n_1\ge n_2\ge \cdots \ge n_t>0,$$ where $t$ is the number of distinct heights.

Assume contrariwise that $n_1<7$. If $n_4<2$, then $n_1+n_2+n_3\le 3n_1\le 18$, and consequently $t\ge10$, because $n_k=1$ for all $k$ such that $4\le k\le t$, and therefore $$(t-3)=\sum_{k>3}n_k=25-(n_1+n_2+n_3)\ge7.$$ This is a contradiction, because we can select a group of nine people with distinct heights violating the assumption. Therefore $n_4\ge2$. If $t\ge5$, then we can again form a group of nine contradicting the assumption: two people of heights $x_1,x_2,x_3,x_4$ each and one of height $x_5$. So $t=4$. But $25=n_1+n_2+n_3+n_4\le 4\cdot6$, which is a contradiction.

-
can you explain the reasoning for this line: If n4<2, then n1+n2+n3≤3n1≤18 and consequently t≥10 (seven people with heights outside the three most popular ones remain) ? –  adamco Jun 7 '12 at 16:58
There are 25 people in total. If no seven of them are in the same group, then the biggest group size possible is six. So at most 18 of them are in the top three groups. Then there are seven people left, so if the fourth group is size 1, they must all be in their own groups. –  Ben Millwood Jun 7 '12 at 17:12
@adamco, what benmachine said :-) –  Jyrki Lahtonen Jun 7 '12 at 17:58

Just for fun an alternative to Jyrki's nice solution:

If there are at most four different heights, then $25 = 6\cdot 4 + 1$ shows that seven people have the same height.

So let's assume that there are five people all of different heights.

If among the other 20 people four have different heights, the group of these four plus the five give a group of nine contradicting the hypothesis as at most two in this group of nine have the same height.

So the remaining 20 people have at most three different height. Now $20 = 6\cdot 3 + 2$ shows that seven people of the remaining 20 have the same height.

-
I like this! It seems more easily generalisable than Jykri's approach. –  Ben Millwood Jun 10 '12 at 16:23