How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15? Explain.
It seems like this is similar to the birthday pigeon hole example.
I really want to understand this question as I have been staring at it for quite some time. So please, just hints if possible to get me started.
On
This problem does use the pigeonhole principle. A major hint for this problem is: How many possible remainders are there when you divide by $15$?
There are $15$ remainders when you divide by $15$. If you draw $20$ socks, are you guaranteed to have a duplicate? What about if you draw $13$? What about $17$?
There are exactly $15$ remainders modulo $15$ and they are $0, 1, 2, \dots, 14$.
This is slightly different (easier) than the birthday problem because we want to guarantee that some pair has the same remainder, and don't have to worry about the probabilities.