Results 1 to 3 of 3

Math Help - Pigeonhole Principle

  1. #1
    Newbie
    Joined
    May 2012
    From
    Eastville
    Posts
    10

    Pigeonhole Principle

    How is the PHP the same as saying that one of the numbers n1, n2, ... , nk is greater than or equal to their average?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13

    Re: Pigeonhole Principle

    Basic PHP says that if you have k+1 pigeons and only k pigeonholes than at least one of the pigeonholes will have at least two pigeons in it.

    Identify each pigeonhole with a number, starting from 1 to k. Then form a sequence of numbers n_1,n_2,...,n_k like this: n_j is the number of pigeons inside the j-th pigeonhole. Calculate the average for such sequence of numbers: (k+1)/k=1+1/k<=2. Since you have more pigeons than pigeonholes at least one of the numbers n_1, n_2,..., n_k will be greater than or equal to two and hence at least one of the numbers in that sequence will be greater than or equal to the average of that sequence .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    Eastville
    Posts
    10

    Re: Pigeonhole Principle

    hm, i still don't entirely see how this relates the two. But thank you for the reply!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  2. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  3. Pigeonhole principle?
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: December 9th 2007, 08:58 AM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum