Thread: I need help to prove that...

Could you show me how to solve this problem?

In a place there are 577 people from 9 different cities.
In every subset of 9 people there are at least 2 who have the same height.
Prove that there are 5 people from the same city that have the same height
and the same sex.

Thanks

Originally Posted by drthea

Could you show me how to solve this problem?

In a place there are 577 people from 9 different cities.
In every subset of 9 people there are at least 2 who have the same height.
Prove that there are 5 people from the same city that have the same height
and the same sex.

Thanks

Hi drthea,

Since in every subset of 9 people there are at least 2 with the same height, there can be at most 8 distinct heights. Otherwise, if there were 9 heights, we could form a set of 9 people with all different heights.

There are 8 heights, 9 cities, 2 sexes (last I checked), so there are 8 * 9 * 2 = 144 possible triples of (height, city, sex) for each person. Since 577 > 4 * 144, there must be at least 5 people with the same height, city ,and sex, by the pigeonhole principle.