Results 1 to 3 of 3

Math Help - [SOLVED] Matching Combinations Question and the pigeonhole principle

  1. #1
    Member
    Joined
    May 2008
    Posts
    101

    [SOLVED] Matching Combinations Question and the pigeonhole principle

    Hi, here is a problem which I can't solve (out of a list of 12)

    8 teams take part in a tournament. Each team plays each other once exactly. Prove that there are at least two teams that have played the same number of matches at any given time.

    While it looks simple, I simply can't find the answer.

    I've been trying for around a week now and its due tomorrow.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Dec 2008
    Posts
    105
    Can matches take place at the same time as others or do they specifically have to happen one at a time?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by BG5965 View Post
    8 teams take part in a tournament. Each team plays each other once exactly. Prove that there are at least two teams that have played the same number of matches at any given time.
    Until seven teams have each played at least one other team, there is nothing to consider.
    Because before that time there are at least two teams that have played zero matches.
    Once seven teams have each played at least one other team, then consider this.
    Each of those seven has played a maximum of six other teams (a team does not play itself).
    We partition the seven according to the number of matches played, 1,2, \cdots ,5,6.
    Seven teams into six cells means some cell has at least two teams.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: August 27th 2011, 09:26 AM
  2. Pigeonhole Principle Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2010, 12:50 PM
  3. Pigeonhole principle question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 18th 2010, 05:09 PM
  4. [SOLVED] Application of the Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 19th 2009, 06:47 PM
  5. Replies: 7
    Last Post: February 20th 2009, 03:05 PM

Search Tags


/mathhelpforum @mathhelpforum