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!
Best Answer
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