15
$\begingroup$

I suddenly thought of a question today: What is the best $n$-digit password? It is not specific so I'll write it in a better way:

There is a password lock that has $n$ digits. There are $t$ choices for every digit. There is a thief that wants to crack the password lock, so he blows some powder into the lock that will show the fingerprints and will tell him the digits used (If there are repeated digit in the password, it only shows one fingerprint on the repeated digit). If the password consists of $m$ distinct digits, then find $m$ ($m\le n$) that makes the number of the combination of the possible password $P\left(m\right)$ the most.

Let me show a example:

For $n=4,t=4$,

$P\left(1\right)=1,$

$P\left(2\right)=C^4_2+2C^4_1=14$

$P\left(3\right)=3\times2C^4_2=36$

$P\left(4\right)=4!=24$

$\therefore m=3$ is the answer for the case $n=4,t=4$.

However, when $n,t$ are bigger number, it will be hard to calculate. Hence, I want to ask you guys the general case or making a table. Thank you!

$\endgroup$
  • 1
    $\begingroup$ Aren't you overcomplicating this a little bit? For 10 digits or less, use as many distinct digits as you can. For 10 or more, use every digit at least once. Once that measure is taken, all paswords are equally secure $\endgroup$ – David Sep 9 at 11:37
  • $\begingroup$ @David I didn't mention the digit must be number! It can be letters, shapes, or sth else! $\endgroup$ – Isaac YIU Math Studio Sep 9 at 11:41
  • $\begingroup$ How can $P(3)$ possibly be more than $81$? If there are $3$ known distinct digits used in the password, then there are at most $3^4$ ways to choose all $4$ digits, only fewer because we want to make sure to use all $3$ of them. $\endgroup$ – Misha Lavrov Sep 9 at 13:44
  • $\begingroup$ @Isaac YIU Math Studio: Nice question (+1). Based on the pattern of data in my answer to your question, I asked this followup question: math.stackexchange.com/questions/3349688 $\endgroup$ – quasi Sep 9 at 16:43
9
$\begingroup$

The thief is able to determine the digits, but not their multiplicities.

Let $m$ be the number of distinct digits, with $m\le n\le t$.

Without loss of generality, we can assume the digits are $1,...,m$.

Let $P(m,n)$ be the number of $n$-tuples with each component in $\{1,...,m\}$ such that each of the values$\;1,...,m\;$occurs at least once.

For example, for $n=4$, we have $$P(1,4)=1,\;\;\;\;P(2,4)=14,\;\;\;\;P(3,4)=36,\;\;\;\;P(4,4)=24$$ For each positive integer $n$, let $f(n)$ be the least positive integer $m\le n$ such that $P(m,n)$ is as large as possible.

For $1\le n \le 20$, here are the values of $f(n)$, computed via Maple . . . $$ \begin{array} { |c |c|c|c|c|c|c|c|c|c|c| |c|c|c|c|c|c|c|c|c|c| } \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline f(n) &1 &2 &2 &3 &4 &5 &5 &6 &7 &8 &8 &9 &10 &10 &11 &12 &13 &13 &14 &15 \\ \hline \end{array} $$ For example, the result $f(20)=15$ means that for $n=20$, an optimal strategy is to choose $a_1,...,a_5$ independently and uniformly at random from $\{1,...,15\}$, and then let the combination be a random reordering of the $20$-tuple$\;(1,...,15,a_1,...,a_5)$.

From the data, it appears that

  • $f(n)$ is approximately ${\large{\frac{3}{4}}}n$.$\\[4pt]$
  • If $n$ is a multiple of $4$, $f(n)$ is exactly ${\large{\frac{3}{4}}}n$.
$\endgroup$
3
$\begingroup$

Since the thief knows which numbers are used - not just how many - I think $P(1)=1, P(2)=14, P(3)=36, P(4)=24$, so $m=3$ is still safest.

In general, you need the Inclusion-Exclusion Principle. You are looking for passwords that use all $m$ different characters in $n$ digits.

  1. The total count of $n$-digit passwords using $m$ different characters is $m^n$.
  2. Subtract the number that lack a '1', which is $(m-1)^n$. Also subtract those that lack '2', '3' and do on. In all, subtract $m(m-1)^n$.
  3. Those that lack both '1' and '2' were subtracted twice, and need to be added back in once. In all, add in ${m\choose2}(m-2)^n$
  4. Subtract ${m\choose3}(m-3)^n$, add ${m\choose4}(m-4)^n$ and so on until ${m\choose m}(m-m)^n$

Sorry I don't have a feel for which is safest as a function of $n$.

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