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

[mr_coffee]

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
1,2,3,4,5,...
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.

 

[sumx4182]

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...

 

[mr_coffee]

Thanks sumx! I had a question is this a typo or did you mean 2 here:

so that means from 1-100, there are 20 integers that are evenly divisible by two, so there are 80 that are not,

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.

 

[Hurkyl]

but on all these problems i don't see how i can apply it.

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

 

[sumx4182]

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

 

[mr_coffee]

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?

Thanks

 

[Hurkyl]

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

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

In this case, the pigeons are the numbers you are choosing.

 

[mr_coffee]

In this problem, there are two obvious categories:
(1) The things divisible by 5
(2) The things not divisible by 5

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

 

[Hurkyl]

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?

 

[0rthodontist]

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.