# Phone number probability: how many phone numbers needed to guarantee atleast 2 have one digit matching?

I've been struggling with this one question given, as I'm not sure I'm applying ideas such as the Pigeonhole Principle the right way. I've tried to look up this question or anything remotely similar to it in hopes of understanding the correct logic I need to use, but I'm just getting more and more confused. These are a couple of links I found close but not close enough to help me: birthdays, odd phone number digits, and more phone number stuff.

Onto my question now, I guess.

# Question: How many (different) phone numbers do we need to guarantee that atleast two have atleast one digit in common? What about the first three digits in common?

Context: phone number is $$10$$ digits long; "in common" implies the same integer is in the same position in both phone numbers; integers $$0$$ to $$9$$ are being used for each digit in the phone numbers.

What I've come up with so far is that since we have $$10$$ "spaces" to fill out and $$10$$ possibilities for each, we have $$10^{10}$$ unique possibilities for phone numbers. Here's where I'm getting stuck: I'm thinking that since we have $$10$$ ways to choose each digit, to match $$1$$ digit of $$2$$ different phone numbers the probability would be $$\frac{1}{10} + \frac{1}{10}$$. This would mean that we need $$20$$ phone numbers to guarantee atleast $$1$$ digit in $$2$$ of them is matching, but I'm very unsure about my reasoning and conclusions. I chose to add the probability of each of the two phone number's first digit being a particular number (the $$\frac{1}{10}$$ thing) because I thought these are two different "choices" that are not dependent on each other, and so they have their own probabilities.

Any help given would be much appreciated! I want to understand what the right approach is in thinking about such a problem, and I can't seem to find resources to help me with this particular one online, so if I have missed any, please feel free to direct me to those as well! Thanks for reading this far either way :)

• The “what about” part is surely trivial: There are 1000 possibilities for the first three digits, so 1001 phone numbers is the smallest number of phone numbers guaranteeing two of them match in those positions. The first part is much harder. – Harald Hanche-Olsen Jul 24 '18 at 17:46
• So basically for the second part we think of it as "how many different combinations of a 3 digit number do you need to guarantee that two of them are the same"? – abhimohit99 Jul 24 '18 at 17:56
• Yup. And I was wrong about the first problem being hard; see my comment on LinAlg's answer. – Harald Hanche-Olsen Jul 24 '18 at 18:01
• Technically, the first 3 digits are the area code and there are only 401 area codes. So, with 402 numbers there must be 2 from the same area code. – Doug M Jul 24 '18 at 18:16
• @DougM That's assuming the numbers are North American phone numbers. – Harald Hanche-Olsen Jul 25 '18 at 10:35