Is this question a pigeon hole question?

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.

• Yes, it is a pigeonhole question – Henry Dec 13 '14 at 16:04
• How many residues are there when you divide by 15? – Phicar Dec 13 '14 at 16:04

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.

• I feel like the answer is $2$ since every number can be divided by $1$ and itself. – hax0r_n_code Dec 13 '14 at 16:09
• Suppose I pick two numbers, $1$ and $2$. Do they have the same remainder? – Michael Biro Dec 13 '14 at 16:10
• No... they do not. – hax0r_n_code Dec 13 '14 at 16:11
• So in order to guarantee that some two have the same remainder, I need to pick at least three. Suppose I pick $1,2,3$... – Michael Biro Dec 13 '14 at 16:11
• That works since $1$ and $3$ divided by $15$ leave a remainder of $0$. So how does picking at least three guarantee that I will have two numbers with the same remainder when there are more than three different types of remainders from $0-14$? – hax0r_n_code Dec 13 '14 at 16:23

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$?

• So it is accurate to say that I would need at least $16$ integers in order to guarantee a repeating remainder since there are $15$ pigeons and $15$ holes, so there is a hole for each pigeon and by increasing the number of pigeons (integers), I guarantee $1$ hole to contain $2$ pigeons? – hax0r_n_code Dec 13 '14 at 17:14
• @inquisitor That is exactly right. – apnorton Dec 13 '14 at 17:15