# Probability of last 3 digits matching in 9 digit student ID

Here is the scenario:

There are a number of students (n), each with a random 9-digit integer student ID number (including zeros). At what n-value would there be a 0.5 probability at least two students having the same "last 3 digits" (identical integers in identical order)?

I am not sure how to set this up.

• 1. Determine what role the first six digits play in the problem. 2. Start with the minimum possible value $n=2$. Can you write down a formula for the chance that two students have the same last three digits? Now try $n=3$. If you like repetitive work, continue with $n=4$, etc., until the solution appears. If you don't like such work, see if you can find a shortcut. At what stage in this procedure do you get stuck? – whuber Jun 3 '16 at 16:40
• I believe that this is essentially the same as the Birthday Problem (en.wikipedia.org/wiki/Birthday_problem) just with a different initial probability of a match – MikeP Jun 3 '16 at 20:17

As MikeP points out in the comments, this problem is an instance of the famous Birthday problem. There are $$10^3 = 1000$$ different combinations of the last-three digits that can occur in this case, and for simplicity we will assume these are equiprobable. Let $$\mathcal{S}_n$$ be the event that at least two of the $$n$$ students share these last three digits on their cards. Then we have:$$^\dagger$$

$$\mathbb{P}(\mathcal{S}_n) = 1 - \mathbb{P}(\bar{\mathcal{S}}_n) = 1 - \frac{(1000)_n}{1000^n}.$$

(Note that if $$n > 1000$$ then $$(1000)_n = 0$$ so $$\mathbb{P}(\mathcal{S}_n) = 1$$ as we would expect. In this case there are more students than number-combinations, so at least two student must share their number-combination.) It is quite simple to program a vectorised function in R to calculate values of these probabilities for a series of values of $$n$$. This is accomplished by the following code:

#Create function to calculate probability for any n
PROBS <- function(n) { T <- rep(1,n);
for (i in 1:(n-1)) { T[i+1] <- T[i]*((1000-i)/1000); }
1-T; }

We can plot these probabilities for different values of $$n$$ to get a sense of how this probability increases when we have more students.

library(ggplot2);
DATA   <- data.frame(n = 1:100, P = PROBS(100));
FIGURE <- ggplot(data = DATA, aes(x = n, y = P)) +
geom_line(size = 1) +
theme(plot.title    = element_text(hjust = 0.5, size = 14, face = 'bold')) +
ggtitle('Probability of sharing digits on student card') +
xlab('Number of students') +
ylab('Probability');
FIGURE;

$$^\dagger$$ The values $$(1000)_n = \prod_{i=1}^n (1000-i+1)$$ are the falling factorial.