1
$\begingroup$

Question A lock combination code is made up of $4$ numbers ($0-9$). Each number can occur at most twice, e.g. $4764$ would be allowed but not $4464$ as the number $4$ has occurred more than $2$ times.Therefore, how many possible combination codes are there?

I know that there are $10,000$ possible combinations if repetitions are allowed. However I'm unsure as to how to answer the question. Any help is greatly appreciated, thanks!

$\endgroup$
5
  • $\begingroup$ What does "Each number can occur two times mostly." mean? Do you mean a number can occur $0,1$ or $2$ times? $\endgroup$
    – lulu
    Dec 14 '18 at 0:27
  • $\begingroup$ @lulu For example '4764' would be allowed but not '4464' as the number '4' has occurred more than 2 times. $\endgroup$
    – Jasmine078
    Dec 14 '18 at 0:31
  • $\begingroup$ Got it. I think, then, you meant to say "Each number can occur at most two times." $\endgroup$
    – lulu
    Dec 14 '18 at 0:32
  • 2
    $\begingroup$ As a hint: break it into three cases. Case I: no number repeats. Case 2: exactly one number repeats. Case 3: two numbers repeat (as in $3443$). $\endgroup$
    – lulu
    Dec 14 '18 at 0:32
  • 2
    $\begingroup$ The complement method may be quicker than finding it straight up: find the number of ways you have $3$ digits the same and $4$ digits the same and subtract from $10000$ $\endgroup$
    – WaveX
    Dec 14 '18 at 0:33
2
$\begingroup$

Here is a possible solution using the Principle of Inclusion/Exclusion:

$\textbf{Case 1}$ (digit is repeated $3$ times):

Choose the repeated digit in $10 \choose 1$ ways.

Choose the remaining digit in $9 \choose 1$ ways.

Order the digits in $\frac{4!}{3!} = 4$ ways.

$\textbf{Case 2}$ (digit is repeated $4$ times):

Choose the repeated digit in $10 \choose 1$ ways.

Order the digits in $\frac{4!}{4!} = 1$ way.

So the number of combinations that don't satisfy your constraint is $(10 * 9 * 4) + (10 * 1) = 370$. Subtracting these from the $10,000$ total combinations yields $\textbf{9,630}$ ways.

$\endgroup$
1
$\begingroup$

Solution without using the Principle of Inclusion/Exclusion:

Add by number of pairs of numbers: $0$ pairs $+$ $1$ pair $+$ $2$ pairs

$=$ (pick $4$ of the $10$ order matters) $+$ (pick which will be repeated and where and the other $2$ numbers order matters) $+$ (pick number for each pair and location of first and second pair)

$=P(10,4) + 10*{{4}\choose{2}}*P(9,2) + {{10}\choose{2}}*{{4}\choose{2}}*1$

$=5040$ $+$ $4320$ $+$ $290$

$= 9630$

$\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.