Results 1 to 3 of 3

Math Help - Pigeonhole problem

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    germany
    Posts
    1

    Pigeonhole problem

    I'm struggling with this problem for a while now, and I just can't figure it out.

    Prove: Let n_1, n_2, . . . , n_t \in N^+
    . If n_1 + n_2 + . . . + n_t-t + 1 Objects are laid in t
    Pigeonholes then there's at least one i \in \{1, . . ., t\}
    so that the i-th pigeonhole has at least n_i objects
    in it
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Pigeonhole problem

    Try a proof by contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Pigeonhole problem

    the idea is very simple. to "keep track", let's call the number of objects distributed in the i-th pigeonhole Mi.

    first we check M1, by counting the objects in the first pigeonhole. if M1 ≥ n1, we are done, it is the pigeonhole the theorem claims exists.

    but maybe not. so we move on to M2. if M2 ≥ n2, again, we are good, we can use M2 as the desired pigeonhole.

    but let's say it's just the worst possible case, the first t-1 pigeonholes all have fewer objects than the corresponding ni.

    how many objects do we have in all?

    n1 + n2 +...+ nt - t + 1.

    what's the MOST possible objects we could have come across in our first t-1 pigeonholes?

    (n1 - 1) + (n2 - 1) +...+ (nt-1 - 1) = n1 + n2 +...+ nt-1 - (t-1).

    this means that there is at LEAST:

    [n1 + n2 +...+ nt - t + 1] - [n1 + n2 +...+ nt-1 - (t-1)] = nt objects in the last pigeonhole.

    *********************

    it's easier to see what is happening with a small number of pigeonholes.

    suppose we have only one, and we have k objects distributed in 1 pigeonhole. then that pigeonhole has at least k objects (duh!).

    perhaps that's "too easy". ok, let's try TWO pigeonholes, with n1 + n2 - 1 objects in 2 pigeonholes.

    if the first pigeonhole has n1 or more objects, we're done. if not, it has at most n1 - 1. objects. that means there's at least n2 objects left over which have to be in the 2nd pigeonhole.

    the same logic applies to 3 pigeonholes and n1 + n2 + n3 - 2 objects. rather than go through the same steps, let's pick 3 numbers, like 3,6, and 8. 3+6+8 = 17. 17 - 2 = 15.

    so we have 15 objects to place in 3 pigeonholes. can we "beat the theorem" by placing less than:

    3 objects in the first pigeonhole (ok, we want to get rid of "as many as we can" so we put 2. now we have 13 left).

    6 objects in the 2nd pigeonhole (the most we can put is 5, right? that leaves us with...uh...8 left).

    8 objects in the 3rd pigeonhole (well, shucks...we're stuck!)?

    do you see why the theorem claims we have n1+..+nt - t + 1 = n1+..+nt - (t-1) objects?

    if we had subtracted from the sum of the ni, t objects, it would be possible to put ni-1 objects in each pigeonhole, summing to a total of n1+...+nt - t objects.

    by only subtracting t - 1 objects, we ensure at least ONE pigeonhole has ni objects (the "extra one we didn't subtract").
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. pigeonhole principle problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 20th 2011, 04:46 PM
  2. a pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 11th 2010, 02:33 AM
  3. Pigeonhole Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 15th 2009, 05:31 PM
  4. Pigeonhole problem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: October 18th 2008, 03:41 PM
  5. A pigeonhole problem
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: June 12th 2007, 11:22 AM

Search Tags


/mathhelpforum @mathhelpforum