# 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 $\displaystyle 12+7+11=30$ pennies. These are your pigeons. The holes are the three possible dates. Pigeonhole principle says that if you place $\displaystyle k$ (where $\displaystyle k\leq 30$) coins into those $\displaystyle 3$ hole you will get that $\displaystyle [ k/3 ]$ end up in the same hole (here $\displaystyle [ \ \ ]$ is the ceiling function). Let us see. If $\displaystyle k=12$ then we get $\displaystyle [12/3] = [4] = 4$. Which is not sufficient, but if $\displaystyle k=13$ then we get $\displaystyle [13/3] = [4+1/3]=5$. This is what we want.

3. Thanks for the reply and explanation.