3
$\begingroup$

I would like to select a PIN with at least one repeat. I am not sure how to go about finding the number of ways to do this.

I know if you normally want both repeats and non-repeats it would be like this: $$10×10×10×10$$ And without repeats: $$10×9×8×7$$ What about at least one repeat?

$\endgroup$
  • 5
    $\begingroup$ The answer is all four-digit pins minus pins without repeats. You have everything you need in your post. $\endgroup$ – rogerl Sep 27 '16 at 0:39
  • $\begingroup$ Note that $10 \times 10 \times 10 \times 10$ is actually with AND WITHOUT repeats. $\endgroup$ – Axoren Sep 27 '16 at 0:54
  • $\begingroup$ @Axoren can you elaborate please? I'm not sure what you mean. $\endgroup$ – cokedude Sep 27 '16 at 0:58
  • $\begingroup$ @cokedude Let's say you're just looking at your first two choices, $10 \times 10$. If you pick some digit $d$, then you have $9$ choices which won't repeat and $1$ choice which will repeat. So, $10 \times 10$ is all 2-pin choices which include both repeats and non-repeats. This logic extends to 4-pins. Your statement above "I know if you normally want repeats it would be like this" implied that $10 \times 10 \times 10 \times 10$ included only pins which contained repetitions. But in fact, it includes all 4-pin combinations, regardless of repetition. $\endgroup$ – Axoren Sep 27 '16 at 2:11
  • $\begingroup$ @Axoren Thank you for explaining that. I fixed my mistake. $\endgroup$ – cokedude Sep 27 '16 at 2:27
3
$\begingroup$

For at least $1$ digit being repeated, consider all possible combinations subtract away those combination with no repetition.

$$10^4-10 \times 9 \times 8 \times 7$$

$\endgroup$
  • $\begingroup$ Why is $$10×9×8×7 = 5040$$ without repeats bigger than $$10^4-10×9×8×7=4960$$ with at least one repeat? I thought usually when you have repeats the number is bigger than without repeats. $\endgroup$ – cokedude Sep 27 '16 at 1:19
  • $\begingroup$ The question boils down to when is $\frac{10!}{(10-n)!}>\frac{10^n}{2}$ $\endgroup$ – Siong Thye Goh Sep 27 '16 at 1:35
  • 1
    $\begingroup$ @cokedude Repetitions are actually a restriction. Consider a 2-pin case: If you want exactly one repetition in a 2-pin case, there are only $10$ possibilities, $dd$. However, if you look at the number of cases in which there are no repetitions, you find that there are $90$ of them: Pick $d$ out of $10$ choices, then pick the next digits out of the $9$ non-repeating choices. Eventually, as you increase the pins, requiring the lack of repetitions becomes a restriction instead (11-pin with no repetitions becomes impossible). $\endgroup$ – Axoren Sep 27 '16 at 2:18
  • $\begingroup$ @Axoren Thank you. I have been doing a lot of permutations and combinations recently. I am mixing up the meanings of order and repetitions. $\endgroup$ – cokedude Sep 27 '16 at 2:26
  • $\begingroup$ @cokedude No problem, man. Good luck with that stuff. I had to take a course in this stuff twice, so I've been in the same pitfalls. It helps to be rigorous about what you're thinking about because the human intuition fails at this stuff quite often. It's why unsuccessful gamblers are such a commonality. $\endgroup$ – Axoren Sep 27 '16 at 2:27
1
$\begingroup$

A PIN has either no repeats, or at least one repeat. Just subtract the number of PINs with no repeats from the total number of PINs in existence: $$10^4-10×9×8×7=4960$$

$\endgroup$
  • $\begingroup$ Why is $$10×9×8×7 = 5040$$ without repeats bigger than $$10^4-10×9×8×7=4960$$ with at least one repeat? I thought usually when you have repeats the number is bigger than without repeats. $\endgroup$ – cokedude Sep 27 '16 at 1:21
  • $\begingroup$ @cokedude It is merely a peculiarity of the system in question. Consider a five-digit PIN: the ways without repeats are $10×9×8×7×6=30240$, less than half of $10^5=100000$. $\endgroup$ – Parcly Taxel Sep 27 '16 at 1:23
0
$\begingroup$

A $4$-digit pin with at least one repetition has four cases:

Two of the digits are repetitions and the others aren't. Out of four digits, choose two of them to be the same and the others different $\binom 4 2 = 6$ $$ RRAB \\ RARB \\ RABR \\ ARRB \\ ARBR \\ ABRR $$

Two pairs of repetitions, out of four digits, choose two pairs $\frac{\binom 4 2}{2} = 3$ (almost the same count as above, except for one small difference; we're selecting which two from the first pair, the remaining two become the second pair)
$$ RRAA \\ RARA \\ RAAR \\ \color{red}{ARRA} \\ \color{red}{\text{already covered by $RAAR$}} \\ \color{red}{ARAR} \\ \color{red}{\text{already covered by $RARA$}} \\ \color{red}{AARR} \\ \color{red}{\text{already covered by $RRAA$}} $$

Three of the digits are repetitions. Out of four digits, choose three of them to be the same, $\binom 4 3 = 4$
$$ RRRA \\ RRAR \\ RARR \\ ARRR $$

Four of the digits are repetitions. Out of four digits, all of them are the same, $\binom 4 4 = 1$
$$ RRRR $$

For the two digit repetition case, we can make 3 choices of digits: $R$ can be chosen freely from $10$ values, the $A$ can be chosen from the remaining $9$ and the $B$ can be chosen from the remaining $8$. There are $6$ ways to order these, so the number of pins contributed by this case is $(6 \text{ orderings}) \times (10 \text{ choices for $R$}) \times (9 \text{ choices for $A$}) \times (8 \text{ choices for $B$} )$.

For the pair of repetitions case, we can make 2 choices of digits: $R$ can be chosen freely from $10$ values, the $A$ can be chosen from the remaining $9$. There are $3$ ways to order these, so the number of pins contributed by this case is $(3 \text{ orderings}) \times (10 \text{ choices for $R$}) \times (9 \text{ choices for $A$}) $.

For the three digit repetition case, we can make 2 choices of digits: $R$ can be chosen freely from $10$ values, the only $A$ can be chosen from the remaining $9$. There are $4$ ways to order these, so the number of pins contributed by this case is $(4 \text{ orderings}) \times (10 \text{ choices for $R$}) \times (9 \text{ choices for $A$} )$.

For the four digit repetition case, we can see that there are only $10$ subcases. There are no choice of orderings and only a choice of which value will dominate all digits. $(1 \text{ orderings}) \times (10 \text{ choices for R})$

Adding it all up together, you get $6(10 \times 9 \times 8) + 3(10 \times 9) + 4(10 \times 9) + 1(10) = 4960$

Some thinking needs to be done about why those orderings in red don't need to be counted. Think about when $R = 1$ and $A = 2$ and when $A = 1$ and $R = 2$. What do you get for those pairs of pairs?

$\endgroup$
  • $\begingroup$ As you can see, we end up with the same answer as the others, but we wasted so much more effort. Excluding the complement of what we wanted from the set of all $4$-pins is the easier way to handle this problem. $\endgroup$ – Axoren Sep 27 '16 at 3:14
  • $\begingroup$ Is it because you are using combination in this case? So order doesn't matter? $\endgroup$ – cokedude Sep 27 '16 at 3:32
  • $\begingroup$ @cokedude If you count $1122$ in the $RRAA$ case, but then you also count $1122$ in the $AARR$ case, you've double-counted the same pin number. $\endgroup$ – Axoren Sep 27 '16 at 3:38

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.