Results 1 to 5 of 5

Math Help - Pigeon Hole Principle Question

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    15

    Pigeon Hole Principle Question

    A penny collection contains twelve 1976 pennies, seven 1968 pennies and eleven 1971 pennies. If you are to pick some pennies without looking at the dates, what is the least number that you must pick to be sure of getting at least five pennies from the same year?

    My working:
    I tried the generalized principle: N(X)>k.N(Y) where N(X) defines the number of pennies. So it should be 30>6.5 --> But the solution says 13. Am i applying the principle wrongly?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by shaoen01 View Post
    A penny collection contains twelve 1976 pennies, seven 1968 pennies and eleven 1971 pennies. If you are to pick some pennies without looking at the dates, what is the least number that you must pick to be sure of getting at least five pennies from the same year?

    My working:
    I tried the generalized principle: N(X)>k.N(Y) where N(X) defines the number of pennies. So it should be 30>6.5 --> But the solution says 13. Am i applying the principle wrongly?
    All together you have 12+7+11=30 pennies. These are your pigeons. The holes are the three possible dates. Pigeonhole principle says that if you place k (where k\leq 30) coins into those 3 hole you will get that [ k/3 ] end up in the same hole (here [ \ \ ] is the ceiling function). Let us see. If k=12 then we get [12/3] = [4] = 4. Which is not sufficient, but if k=13 then we get [13/3] = [4+1/3]=5. This is what we want.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2008
    Posts
    15
    Thanks for the reply and explanation.

    Can i go about this way as well:
    N(X)>k.N(Y) --> 30>13.3

    Hence, the least number of times i will have to pick the penny is 13?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2007
    Posts
    131
    Just think about it intuitively. The worst case scenario is that you have already selected 4 pennies of each date. There are 3 dates, giving you 12 pennies selected. The next one you pick guarantees that you will have at least 5 pennies for at least one date. Thus, taking 13 pennies guarantees you will have at least 5 of at least one date.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by xifentoozlerix View Post
    Just think about it intuitively. The worst case scenario is that you have already selected 4 pennies of each date. There are 3 dates, giving you 12 pennies selected. The next one you pick guarantees that you will have at least 5 pennies for at least one date. Thus, taking 13 pennies guarantees you will have at least 5 of at least one date.
    The point here is not to think intuitively, but rather to do it mathematically so to develope the mathematical understanding of pigeonholing.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2014, 09:46 PM
  2. Pigeon-hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 31st 2011, 05:14 AM
  3. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2011, 02:44 PM
  4. Pigeon Hole Principle Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2009, 10:22 PM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM

Search Tags


/mathhelpforum @mathhelpforum