# 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

If there's bound to be 3 people of the same height in a group of 9, that means you classify them by at most 4 different heights, since if you classified by 5 or more, you could not make the original statement by the pigeonhole principle.

Once you have shown this, it is straightforward to prove the desired statement.

• How do you conclude that 5 or more different heights are impossible? – Henning Makholm Jun 7 '12 at 16:19
• If we had 5 different heights, we could have four groups of 2 people with the same height (in any combination) and 1 person with the remaining height. Same argument can be made for any greater number of heights. – Karl Nordstrom Jun 7 '12 at 16:21
• @KarlNordstrom: what if there are 5 different heights, but two of those heights only have one representative? – Ben Millwood Jun 7 '12 at 16:23
• I'll rephrase the original statement. We know every collection of 9 people has 3 people in the same group. If we divide 9 people into more than 4 groups we can not guarantee that there is at least one group with at least 3 people in it. This is the reverse of the pigeonhole principle in a sense. – Karl Nordstrom Jun 7 '12 at 16:25
• @Karl: Suppose there are 19 people of height 0 and one person of each of heights 1,2,3,4,5,6. Then any group of 9 people will include at least 3 people with height 0, simply because there are not enough people of other heights to select. This contradicts your claim. – Henning Makholm Jun 7 '12 at 16:39