13
$\begingroup$

A small argument my colleague and I were having...

Say I've got a $4$-digit security code on my burglar alarm, and I'm too lazy to ever change it. Over time, the digits involved will become worn.

If I've used $4$ different digits (as is common, eg $1357$), then an attacker, knowing those are the digits in the code, needs (if I'm right!) $24$ goes to try all combinations.

If I've repeated a digit (eg, $1317$), the attacker just knows $1$, $3$ and $7$ are used (assume that all wearing is indistinguishable). How many different possible $4$-digit codes are possible, using each digit at least once? I say it's more than $24$, my colleague is convinced otherwise.

Bonus kudos for generalizing the problem to knowing $k$ digits in an $n$-digit pin. ;)

$\endgroup$
  • $\begingroup$ I wonder if this question could be generalized further. Given an n-digit pin and a burglar who can determine which digits were used: how many unique digits should one use in the pin to product the most combinations? For 4-digits, 3 was the answer. But what is the answer for longer pins? $\endgroup$ – Moby Disk Feb 11 '15 at 21:09
  • 1
    $\begingroup$ The sequence oeis.org/A019538 is pertinent here (for the general problem). $\endgroup$ – Barry Cipra Feb 11 '15 at 21:42
4
$\begingroup$

Here is my answer for a code of length $n$ using $k$ different digits which may be repeated arbitrarily often. Each digits must appear at least once. (otherwise it won't be worn out.)

This uses the corresponding sequence “A019538” which Barry Cipra mentioned.

Now, referencing OEIS is all nice and all, but if you aren't a mathematician chances are that page is quite confusing. It has a bunch of comments all seemingly pointing at a different meaning. None of those meanings in the one we actually have. (The “Number of $k$ dimensional 'faces' of the $n$ dimensional permutohedron” doesn't look like like numbers on a keypad to me at all... And WTF even is a permutohedron?)

Here is a formulation we can turn into a keypad: “Number of surjections (onto functions) from an $n$-element set to a $k$-element set.”

What is a “surjection from an $n$-element set to a $k$-element set”? It's an assignment which assigns one out of $k$ numbers each of $n$ places. Numbers can occur arbitrarily often and the “surjection” tells us each of the $k$ elements must be picked at least once. Great! That is exactly what we are looking for. Each position $n$ positions of the code is assigned one out of $k$ worn out keys and each key is picked at least once.

We are on the right OEIS page, let's get a formula. (There are many) $$T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right) \text{ with } T(0, 0) = 1$$ That is not exactly a “plug in your numbers and get a result” formula – but with a small table getting a value is easy enough. And this formula happens to be easy to explain.

First of, why is $T(0,0) = 1$? This counts the ways you can enter a code of length $0$ using no digits. It sounds slightly insane if you see this the first time, but there is exactly one way to do that: Stand there and don't do anything.

Now where does $T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right)$ come from? For the first place, we have $k$ different possibilities. What about the other $n-1$ places which follow? We split this into two cases:

  • The first digit is never used again. Then there are $T(n-1, k-1)$ ways to fill out the last $n-1$ digits with $k-1$ numbers.
  • The first digit is used again. There there are $T(n-1, k)$ ways to fill out the last $n-1$ digits with $k$ numbers.

In sum, that gives us $T(n-1, k-1)+T(n-1, k)$ ways to fill out the last $n-1$ places times $k$ ways to fill out the first digit.

Here are some values which were also kindly supplied by OEIS:

n\k 1    2     3      4       5        6        7        8        9
1:  1
2:  1    2
3:  1    6     6
4:  1   14    36     24
5:  1   30   150    240     120
6:  1   62   540   1560    1800      720
7:  1  126  1806   8400   16800    15120     5040
8:  1  254  5796  40824  126000   191520   141120    40320
9:  1  510 18150 186480  834120  1905120  2328480  1451520   362880

In conclusion, if you use a lenght from three to six, double a single digit. For seven, eight and nine you should use two less and if you are using even longer codes, ask on stackoverflow for coding help.

I hope that helps.

$\endgroup$
10
$\begingroup$

If the burglar knows which digit is repeated, (s)he has \begin{equation*} \dfrac{4!}{2!} = 12 \end{equation*} codes to try. Since (s)he doesn't know which digit is repeated, (s)he will have to try $3 \cdot 12=36$ different codes.

$\endgroup$
  • $\begingroup$ Can you show how your work? $\endgroup$ – Moby Disk Feb 11 '15 at 19:59
  • $\begingroup$ @MobyDisk We want all permutations of four elements, but since one of the digits is repeated, we end up with repeats. For example, swapping the 7's in 1377 yields 1377. The $2!$ accounts for this. The formula used here is a common solution to the question "how many words can you spell with the letters ABCC?" These lecture notes explain it pretty well: math.lsu.edu/~madden/M3355spr2011/Lecture-3.pdf. $\endgroup$ – 211792 Feb 11 '15 at 20:26
  • $\begingroup$ I was hoping for something like: n!/(n-k)! where n=4, k=2 so 4!/(4-2)! along with an explanation of why n=4 even though there are only 3 digits. What is difficult about this problem, is not just knowing the permutation/combination rules, but understanding how to apply it in this case where there are 3 distinct values, but only one can be chosen twice while the others cannot. I took stat and understand what is in the linked lecture, but not how to apply it to this case. $\endgroup$ – Moby Disk Feb 11 '15 at 20:48
  • 1
    $\begingroup$ We have $n=4$ because we must have a 4-digit code. These leads to $4!=24$ ways that we can arrange our digits. However, we want to remove any repeats. Since our two 7's (in the above example) can be rearranged in $2!=2$ ways, we must have counted each distinct code twice, so we divide by 2. Similarly, if we were creating a 4-digit code from the digits 1 and 7 by using the 1 once and the 7 three times, we would have $3!=6$ copies of each code in our original enumeration of all 24 codes. Since we've counted each distinct code 6 times, we divide to find that there are $4!/3!=4$ codes. $\endgroup$ – 211792 Feb 11 '15 at 21:02
6
$\begingroup$

I really like that problem, it is very visual and easy to understand. I'll show the case of a code lenght of $n$ where $l<n$ digits are repeated exactly twice. That makes for a total of $k = n-l$ different digits. (i.e. for your particular question please set $n=4$, $l=1$.)

Given $n$ different digits without repetition, you got $n!$ ways to order them. That is a fairly basic problem.

Now assume you still have $n$ digits, but $l$ „marked“ ones are repeated twice. (i.e. the attacker knows which digit you double) This will reduce your possibilities by a factor of $2^k$.

Why? Your set of numbers looks like $\{1_1,1_2,2_1,2_2,...,l_1,l_2,l+1,l+2,...,n-l=k\}$. That is still $n$ elements, because the first $l$ are doubled. When ordering those we have $n!$ choices, because we can see those little indices. But you burglar alarm can't, we are counting to many possibilities! We need to figure out how often each possibility was counted and adjust for this. Each pair of doubled numbers $j_1, j_2$ (here $j\leq l$) could be placed as $..,j_1,..,j_2,..$ or the other way round as $..,j_2,..j_1,..$ giving you two possibilities in total. As changing that around is independent we need to multiply all those twos together.

The final step now considers the burglar, who doesn't know which digits are doubled. He will have to try each possible subset with $l$ elements. This is known as the binomial coefficient $n\choose l$. In total this gives us:

$${n \choose l} \cdot \frac{n!}{2^l}$$

Note that $2^l$ grows faster than $n \choose l$, but the later start with a higher initial amount. In conclusion: A small number of doubled keys is sensible, depending on your $n$. But make sure you don't double to many!

$\endgroup$
5
$\begingroup$

Your question of "using each digit at least once" is kind of confusing, because you should emphasize that there are nonetheless $3$ different digits involved, all of which are known to the attacker.

Having emphasized this, the attacker has a total of $36$ possible combinations:

 Digit #1 occurs | Digit #2 occurs | Digit #3 occurs | Combinations
-----------------|-----------------|-----------------|--------------
 1 time          | 1 time          | 2 times         | 12
-----------------|-----------------|-----------------|--------------
 1 time          | 2 times         | 1 time          | 12
-----------------|-----------------|-----------------|--------------
 2 times         | 1 time          | 1 time          | 12

Each case can be calculated in any of the following ways:

  • $\binom41\cdot\binom31\cdot\binom22=12$
  • $\binom41\cdot\binom32\cdot\binom11=12$
  • $\binom42\cdot\binom21\cdot\binom11=12$
$\endgroup$
  • $\begingroup$ Can you explain each of the 3 cases that you calculated? $\endgroup$ – Moby Disk Feb 11 '15 at 20:17
  • $\begingroup$ @MobyDisk: I'll explain the first case as an example (you can equally do it using any of the other cases): Choose $1$ out of $4$ places for the first digit, choose $1$ out of the remaining $3$ places for the second digit, choose $2$ out of the remaining $2$ places for the third digit. $\endgroup$ – barak manos Feb 11 '15 at 20:33
  • $\begingroup$ Actually, it is the second and third cases I am not clear on. I see that you are treating 2 of the choices as the same digit, so I'm unclear why those cases are not (4 1) (3 1) (2 2) as well. The result is the same, but the thinking is different. $\endgroup$ – Moby Disk Feb 11 '15 at 20:44
  • $\begingroup$ @MobyDisk: In the second case, I pick $1$ place for the first digit, $2$ places for the second digit, and $1$ place for the third digit. Does that explain everything now? $\endgroup$ – barak manos Feb 11 '15 at 21:04
1
$\begingroup$

If
$n$...the total number of digits,
$k$...the number of the same digits.
then the number of different options (and numbers) $c$ equals to:
$$c=\binom{n}{k}\cdot (n-k)!$$ and because of the $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ the $c$ can be simplified:
$$c=\frac{n!}{k!}$$ For $n=4$[digits], and $k=1$(all numbers are different): $c=\frac{4!}{1!}=24$,
for $n=4$[digits], and $k=2$[the same numbers]: $c=\frac{4!}{2!}=12$,
for $n=4$[digits], and $k=3$[the same numbers]: $c=\frac{4!}{3!}=4$,
and for $n=4$[digits], and $k=4$(4 the same numbers): $c=\frac{4!}{4!}=1$.
If you have $n$ digits containing $k$ the same numbers, then you can create $\binom{n}{k}$ combinations representing different number patters(where each contains (n-k) empty positions). The (n-k) remaining positions can contain any permutation remaining numbers. For example, for numbers $1,1,3,4$, this means $n=4$ and $k=2$ you can create $\binom{4}{2}=6$ these diffrerent patterns:
1)$1,1,-,-$;
2)$1,-,1,-$;
3)$1,-,-,1$;
4)$-,1,1,-$;
5)$-,1,-,1$;
6)$-,-,1,1$
Now for each combination you can replace pair of $-$ with permutation of two remaining numbers, this mean $3,4$ or $4,3$. For first combination $1,1,-,-$: $1,1,3,4$ and $1,1,4,3$. And, therefore, $6\cdot{2}=12$.

$\endgroup$
1
$\begingroup$

For those less mathematically inclined, here are all 36 combinations for a 4 digit pin, using 3 digits, where 1 digit can be repeated. This might be useful for proving it to someone without having to explain permutations and combinations:

AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA

ABBC
ABCB
ACBB
BABC
BACB
BBAC
BBCA
BCAB
BCBA
CABB
CBAB
CBBA

ABCC
ACBC
ACCB
BACC
BCAC
BCCA
CABC
CACB
CBAC
CBCA
CCAB
CCBA
$\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.