2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – whuber Jun 3 '16 at 16:40
  • 2
    $\begingroup$ 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 $\endgroup$ – MikeP Jun 3 '16 at 20:17
0
$\begingroup$

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;

enter image description here


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

$\endgroup$

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.