Results 1 to 8 of 8

Math Help - Pigeon hole principle

  1. #1
    Member
    Joined
    Sep 2011
    Posts
    114

    Pigeon hole principle

    I understand what the pigeonhole principle is.

    if there are n pigeons and m holes than at least one hole has more than n/m pigeons.

    But how do I show it with specific example?

    a.Suppose a programmer wrote 1000 lines of code in 30 days. Show that there must be at least one day when the programmer wrote more than 33 lines of code.

    b.If n is a positive integer, how many distinct integers from 0 to 3n must you pick to be sure of getting a multiple of 3 (0 is considered a multiple of 3).
    Hint: try it first with n = 1, 2, 3.

    edit: for a. I just put

    1000=30*33+10

    so if all 30 day have 33 lines of code, there are still 10 lines of code to add to one day, therefore at least 1 will be greater than 33.
    Last edited by ehpoc; November 16th 2011 at 08:50 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2011
    Posts
    13

    Re: Pigeon hole principle

    I think your answer for 1) is fine. If you were to precisely apply the pigeonhole analogy, you could think of there being 30*33 total holes and 1000 pigeons, but obviously you understand the concept.

    For 2), when you range from 0 to 3n, there are going to be n+1 numbers that are divisible by 3, and 2n numbers that are not.

    For instance, when n=2

    0,1,2,3,4,5,6

    0; 3,6 are multiples of 3
    1,2; 4,5 are not
    (notice the groupings)

    I can supply a proof if you'd like, but it's intuitively clear and I don't know if you need it.

    Once you know this, you know you have 2n "holes", so you need 2n+1 "pigeons" before you are forced to pick a multiple of 3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Pigeon hole principle

    thank you!

    edit:

    I am getting more confused now.

    the question askes

    Suppose you have the set of integers {1, 2, 3, ..., 19}. How many members of that set must be chosen so that at least two of them sum to exactly 20.

    I can see then answer is 11. But what exactly do I need pigeon hole principle to come upon this answer?

    I can get then answer but they ask "Use the pigeon hole principle for these questions."

    No clue what that means.

    edit:

    then this one i have no clue how to even begin.

    How many distinct integers from 1000 to 9999 inclusive must you pick in order to be sure of getting two that have a digit in common. For example, 1234 and 3038 have the digit 3 in common.
    Last edited by ehpoc; November 16th 2011 at 11:56 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2011
    Posts
    13

    Re: Pigeon hole principle

    Sorry I didn't get this until now. It doesn't email me to alert me that a reply has been edited.

    You often don't "need" the pigeon-hole principle; it is just a nice way to think about things sometimes. In your first problem, there are 10 "holes" that can be filled up before you get a pair that adds to 20; thus you need to find out how many pigeons "force" a pair, and, as you said, the answer is 11.

    In the second problem, the restriction (1000 to 9999) forces you to pick 4-digit numbers. Thus you have 10 holes (different digits), and you need to see how many numbers does it take to fill a hole more than once (sharing a digit). The answer is 3 numbers, which means that you have 12 "pigeons" trying to fit into 10 "holes", and thus one of the holes must contain two pigeons.

    For instance, your first number could be 1234, and your second number could be 5678. The third number could have a 9 and 0 in it, but then would be forced to include one of the other digits.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Pigeon hole principle

    Ok ya I understand it. It seems so clear when you explain it. Then I move on to the next question, and my mind can't apply it to the new scenario. When you explain it, it seems clear as day LOL.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2011
    Posts
    1

    Re: Pigeon hole principle

    Come see me after class.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2011
    Posts
    1

    Re: Pigeon hole principle

    Quote Originally Posted by Kockay View Post
    Come see me after class.
    Thats not how you spell my name
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Sep 2011
    Posts
    114

    Re: Pigeon hole principle

    LMAO you guys are funny!!!!
    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, 02:48 AM
  2. [SOLVED] pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 18th 2011, 04:24 AM
  3. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 9th 2009, 02:56 AM
  4. pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2008, 03:39 AM
  5. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 8th 2007, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum