Results 1 to 2 of 2

Math Help - I need help to prove that...

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    @home
    Posts
    17

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by drthea View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a/b and a/c then a/ (3b-7c)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2010, 06:20 PM
  2. prove,,,
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 1st 2010, 10:02 AM
  3. Prove |w + z| <= |w| +|z|
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 28th 2010, 06:44 AM
  4. Replies: 2
    Last Post: August 28th 2009, 03:59 AM
  5. How to prove that n^2 + n + 2 is even??
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 30th 2008, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum