2
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Harald Hanche-Olsen Jul 24 '18 at 17:46
  • $\begingroup$ 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"? $\endgroup$ – abhimohit99 Jul 24 '18 at 17:56
  • $\begingroup$ Yup. And I was wrong about the first problem being hard; see my comment on LinAlg's answer. $\endgroup$ – Harald Hanche-Olsen Jul 24 '18 at 18:01
  • $\begingroup$ 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. $\endgroup$ – Doug M Jul 24 '18 at 18:16
  • $\begingroup$ @DougM That's assuming the numbers are North American phone numbers. $\endgroup$ – Harald Hanche-Olsen Jul 25 '18 at 10:35
3
$\begingroup$

The length of the phone number is irrelevant. For the first position there are only 10 possible different digits, so the 11th phone number has to be a duplicate.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why do we not care about the other positions? Is it because we treat them as separate probabilities? I.e. does the first part of the question essentially become "how many times would you need to choose a number from 0 to 9 to have 2 of those choices be the same"? $\endgroup$ – abhimohit99 Jul 24 '18 at 17:51
  • 1
    $\begingroup$ @abhimohit99 There are no probabilities involved. I argue that the 11th has to be a duplicate. It is easy to see that a configuration with 10 phone numbers exists where all digits are different (0000000000, 1111111111, etc), so 11 is the answer. $\endgroup$ – LinAlg Jul 24 '18 at 17:52
  • $\begingroup$ Combinatorics can be hard. I was convinced this answer is wrong, but it's actually correct! If you have 11 phone numbers, two of them will indeed have the same digit in the first position. Also, two of them (maybe not the same pair) will have the same digit in the second position. And another pair will have the same in the third position, and so on. It is trivial to find 10 phone numbers with no matching digits. (I feel like an idiot for not seeing this right away.) $\endgroup$ – Harald Hanche-Olsen Jul 24 '18 at 18:00
  • $\begingroup$ Thank you for your help! $\endgroup$ – abhimohit99 Jul 24 '18 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.