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
    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) ?2012-06-07
  • 2
    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.2012-06-07
  • 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
    How do you conclude that 5 or more different heights are impossible?2012-06-07
  • 0
    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.2012-06-07
  • 0
    @KarlNordstrom: what if there are 5 different heights, but two of those heights only have one representative?2012-06-07
  • 0
    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.2012-06-07
  • 1
    @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.2012-06-07
  • 0
    He didn't place any additional constraints on the group. This answer as it stands is wrong.2012-06-07
  • 0
    Sorry my mistake, you're right. I'm the one with the constraint - that every group of nine people must have three of the same height. My original answer is still correct though.2012-06-07
  • 0
    Hmm. I see where you're coming from now, but you're still wrong. If you divide 9 people into more than 4 groups, you might still be able to guarantee that three people are in the same group, because some of the groups might be forced to be small (as in Henning's example).2012-06-07
  • 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