Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many ints 1 to 100, to make sure of getting one divisble by 5?

  1. Nov 5, 2006 #1
    I'm thinking this question is too easy to be right...
    the question says:

    How many integers from 1 thorugh 100 must you pick in order to be sure of getting one that is divisble by 5?

    Well i just started writing out the numbers
    now 5/5 = 1, remainder of 0, so its divisible by 5.

    So is it simply you must pick 5 integers start at 1 to ensure of getting one that is divisble by 5.
  2. jcsd
  3. Nov 5, 2006 #2
    I don't necessarily think that is what they meant by the question...here's my thinking...

    for every 10 integers, like 1-10, only 2 are evenly divisible by 5 (5, and 10), so that means from 1-100, there are 20 integers that are evenly divisible by 5, so there are 80 that are not, so if you randomly reach into a bag filled with the integers from 1-100, and you pick out 81 integers, you are 100% guaranteed to have one that is divisibly by 5. Theres a good chance you'll pick more than 1, but picking 81 guarantees you at least one...
  4. Nov 5, 2006 #3
    Thanks sumx! I had a question is this a typo or did you mean 2 here:
    Or did you mean 5?

    Also why did you say if you pick out 81, instead of 80? I'm having problems figuring out how you did this, it sounds perfect but did you use some sort of principal? The section we are doing right now is the Pigeon hole principal but on all these problems i don't see how i can apply it.
  5. Nov 5, 2006 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    To apply the pigeonhole principle, you need to, well, pigeonhole things.

    In this problem, there are two obvious categories:
    (1) The things divisible by 5
    (2) The things not divisible by 5
  6. Nov 5, 2006 #5
    Yes, i meant 5, i edited it...and i said 81 because if you pick 80, you could theoretically pick the 80 integers between 1 and 100 that are not divisible by 5, so if you pick 81 integers, then you're GUARANTEED to have one that it divisible by 5
  7. Nov 5, 2006 #6
    Thanks sumx, makes sense!

    Hurkyl, how do I choose which ones are the piegons and which one are the pigeonholes?

    Here is the generalization of the pigeonhole principal.

    A generalization of the pigeonhole principle states that if n pigeons fly into m pigeonholes and, for soeme postive integer k, n > km, then at least one pigeonhole contains k+1 or more pigeons. For m = 4, n = 9, and k = 2. Since 9 > 2x4, at least one pigeonhole contains three (2+1) or more pigeons.

    Is it possible to put it in this form Hurkyl?

  8. Nov 5, 2006 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Pigeons are the things, and pigeonholes are the categories they may fall into.

    In this case, the pigeons are the numbers you are choosing.
  9. Nov 5, 2006 #8
    Ahh okay these are the categories, then 1-100 are the numbers

    Then what directs you to choose what numbers go into the 2 "holes"? Or is it just now you have to think logically and break it down like sum did? Or is there more to the pigeon hole
  10. Nov 5, 2006 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Oh; I guess I should have read the specific version of the pigeonhole principle you were asking about. No, I don't think this problem can be put into that exact form you mention in #6.

    You do need to follow something resembling sum's line of reasoning, yes. IMHO, it's easiest to think about the dual problem: how many numbers can I pick without ever picking one divisible by 5?
  11. Nov 5, 2006 #10


    User Avatar
    Science Advisor

    It can be done using the pigeonhole principle. What you do is pair them by 5's. So pigeonhole 1 is the numbers {1, 2, 3, 4, 5}. Pigeonhole 2 is the numbers {6, 7, 8, 9, 10}, and so on, for 20 total pigeonholes. You want to know how many numbers you must choose before one of the 20 pigeonholes must receive 5 of them.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook