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.
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.
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.
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.