# How many ID numbers must you have to guarantee that at least two of them sum to the same number?

ID numbers all have 7 digits from 0 to 9. We will assume that all digits can be 0 through 9

This is a homework problem, but I am afraid I am very lost, though I think I am over thinking it.

I know this is the pigeon hole theorom in which if you have N pigeons and k pigeon holes then there is at least on hole with the ceiling of N/k pigeons.

I just don't know how to apply that idea here.

The next question is similar: How many ID numbers must you have to guarantee that at least four of them have the same last 2 digits?

Would the process for this one be different than the first one?

Thanks.

• For the first problem: I'm not sure what you mean by "at least two of them sum to the same number"; do you mean "two pairs of them" instead? ... As for the second problem, yes, it's different. How many possible choices are there for the last two digits of the ID number? Now choose the smallest N such that N divided by that number, rounded up, is 4. (There is a formula for that value of N.) – Christopher Carl Heckman Dec 1 '15 at 6:43
• I am pretty sure it means the digits sum to the same number. As for the second, there are 81 possible choices and so 81 x 3 + 1 would be my answer? – Jane Doe Dec 1 '15 at 6:46
• (a) "Pretty sure"? Do you have the original problem? (b) There are not 81 possible "last 2 digits"; the rest of your answer is correct, though. – Christopher Carl Heckman Dec 1 '15 at 6:48
• That is the original problem, and I am sure as the previous part refers to the sum of all digits. And yeah, dumb mistake, 10 choices for each of the last two makes it 301. – Jane Doe Dec 1 '15 at 6:52
• I find the title of this question misleading. – Greg Martin Dec 1 '15 at 7:38

## 1 Answer

For the first part, there are exactly $64$ possibilities: the possible sums range from $0$ to $63$. In order to guarantee a repetition, you need to have $64+1$ numbers. Imagine the worst case scenario that the first $64$ are all distinct. While this is highly unlikely, it is not impossible. Now add one more random code. It must duplicate one of sums in the previous $64$ codes, its unavoidable! The thing to remember is that you might do it with fewer codes, but there is a non-zero probability that all the sums would be distinct, so you cannot guarantee that some sum is repeated.

For the second part there are $10^2$ possible 2-digit endings to the 7-digit codes. You'll need $3\cdot 10^2+1$ to guarantee one of the codes repeats $4$ times by the same reasoning as above.

• Your answer to the second part is wrong; BNSlug got it right (301). – Christopher Carl Heckman Dec 1 '15 at 7:21
• In a seven digit code there are $10^5$ codes that share a fixed $2$ digit ending. Once the two digit ending is determined, then my answer would be correct. But this is not the question being asked upon further reflection. I have edited my answer accordingly. – Laars Helenius Dec 1 '15 at 7:29
• Thanks a bunch, this makes a lot of sense. – Jane Doe Dec 1 '15 at 7:36