[Math] combinatorics: The pigeonhole principle

Question

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.

Answer 1

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.