Results 1 to 3 of 3

Math Help - Pigeon-hole Principle (3)

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Pigeon-hole Principle (3)

    One afternoon, a mathematics library had several visitors. A librarian noticed that it was impossible to find three visitors so that no two of them had met in the library that afternoon. Prove that then it was possible to find two moments of time that afternoon so that each visitor was in the library at one of those two moments.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    193

    Re: Pigeon-hole Principle (3)

    I'm not really understanding the question. I'm imagining a counterexample where people come in two at a time, meet, and leave, with people coming in enough times so that every 3-subset of the set of all visitors contains at least one pair of people that have met. For example, with 5 people,

    {1,2}, {1,4}, {1,3}, {2,4}, {2,5}, {3,5}.

    What am I doing wrong?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Pigeon-hole Principle (3)

    Quote Originally Posted by topspin1617 View Post
    I'm not really understanding the question. I'm imagining a counterexample where people come in two at a time, meet, and leave, with people coming in enough times so that every 3-subset of the set of all visitors contains at least one pair of people that have met. For example, with 5 people,

    {1,2}, {1,4}, {1,3}, {2,4}, {2,5}, {3,5}.

    What am I doing wrong?
    You have a point.

    Edit: A poster on another forum said "The problem implicitly assumes that each visitor spent only one contiguous lapse of time in the library - otherwise we may have each pair of visitors being together at some point in the library, without more than two visitors being simultaneously in the library at any moment in time."
    Last edited by alexmahone; August 5th 2011 at 03:35 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Pigeon-Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 30th 2011, 03:48 AM
  2. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 05:24 AM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 03:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 04:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 06:37 PM

Search Tags


/mathhelpforum @mathhelpforum