6
$\begingroup$

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.

3 Answers 3

4

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.

  • 0
    @adamco, what benmachine said :-)2012-06-07
2

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.

  • 0
    I like this! It seems more easily generalisable than Jykri's approach.2012-06-10
0

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.

  • 0
    The key is that the only way to force those groups to be small is to make some of the *other* groups big, and hence get the result.2012-06-07