Results 1 to 6 of 6

Math Help - [SOLVED] Application of the Pigeonhole Principle

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    20

    [SOLVED] Application of the Pigeonhole Principle

    I have some problems relating to the pigeonhole principle. Here they are:

    Prove that at a party where there are at least two people, there are two people who know the same number of other people there.

    The other one is,

    Let n1, n2, ... , nt be positive integers. Show that if n1+n2+...+nt - t + 1 objects are placed into t boxes, then for some i, i = 1, 2, ... , t, the ith box contains at least ni objects.



    Now, I was given the hint that the pigeonhole principle can help me here, but I don't know how to apply it. Are there any other hints anyone could think of to help me prove this? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1
    Quote Originally Posted by Oijl View Post
    Prove that at a party where there are at least two people, there are two people who know the same number of other people there.
    We must make some assumptions here.
    First “If A knows B then B knows A”.
    Second “A knows at most n-1 other people at the party".

    This problem is equivalent to the theorem: In a simple graph at two vertices have the same degree.

    For the pigeonholes, there n of them: 0,1,\cdots,n-1.
    Anyone at the party can know from 0 to n-1 other people.

    Suppose that none of those pigeonholes has more than one person in it.
    Convince yourself that the [n-1]^{th} hole would be empty.
    Think about what that means.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Not to be rude, but I think simply applying the fact that we have n-1 holes as you described, and n people in the party, the pidgeonhole principle directly gives us that there must be two people in at least one hole.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1
    Quote Originally Posted by Defunkt View Post
    Not to be rude, but I think simply applying the fact that we have n-1 holes as you described, and n people in the party, the pidgeonhole principle directly gives us that there must be two people in at least one hole.
    That is not being rude. It is being unable to count.
    There are n holes: 0,1,\cdots,n-1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Oops, didn't see the 0. Sorry.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    20
    I see! All the pigeonholes cannot be filled, because that is a contradiction, because the hole representing zero cannot be filled while the hole representing knowing n - 1 is filled... and since there are the same number of elements as holes, and all the holes cannot be filled, there must be some hole with more than one element in it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. application of pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2011, 06:05 AM
  2. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  3. Replies: 7
    Last Post: February 20th 2009, 02:05 PM
  4. Replies: 2
    Last Post: February 16th 2009, 07:30 AM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum