# Thread: Pigeon Hole Principle Question

1. ## 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?

2. Originally Posted by shaoen01
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.

3. Thanks for the reply and explanation.

N(X)>k.N(Y) --> 30>13.3

Hence, the least number of times i will have to pick the penny is 13?

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

5. Originally Posted by xifentoozlerix
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.