Lock Optimisation

Question

In a simple combination lock, a sequence of several digits is used as a password, with one wheel per digit. Generally, it is not possible to unlock the lock without knowing the password, but due to the workings of this lock's mechanism, a "click" is heard whenever a wheel is rotated into the correct position.

For example, the following lock has 3 wheels, each with the digits from 0 to 9. Trying all possible combinations would require up to 1000 attempts to unlock the lock. But due to the clicking mechanism, it is possible to so in at most 30 tries (up to 10 tries for each wheel, where a "try" refers to a single rotation of a wheel).

Now, instead of 10 digits, you can design the lock to have $k$ digits on each wheel ($k \in \mathbb{N},\ k\geq 2$). For security reasons, we want the lock to have at least $N=10^{10}$ different possible combinations. The lock can have as many wheels as needed.

1. What is the optimal value of $k$ to minimize the number of tries (wheel rotations) needed to open the lock in the worst case? What about the average case?

2. Now, suppose that the lock can have different numbers of digits at different places. For example: The first wheel can hold 7 values (0 to 6), the second can hold 4 values and so on. Again, how can we minimize the number of tries in the average and worst cases?

Can you generalize for any $N$?

Answer 1

Definitions

Consider a lock $L$ consisting of $m$ wheels, where the $i$th wheel has $k_i$ digits (assume $k_i\geq 2$). I will use the notation $L=\{k_1,k_2,\ldots,k_m\}$.

The number of combinations $L$ can be set to, which I call the size of $L$ which I write as $|L|$, is simply the product of the $k_i$:

$$ |L|=\prod_{i=1}^m k_i $$

The worst-case number of turns to unlock the lock is:

$$ \mathsf{WC}(L)=\sum_{i=1}^mk_i $$

And the average-case is:

$$ \mathsf{AC}(L)=\sum_{i=1}^m\frac{k_i+1}2 $$

An important fact is that there are no 'cross terms' in any of the quantities associated with a lock: any subset of the wheels may be considered separately from the rest. (This also implies that the order of the $k_i$ is unimportant.)

I'll also define four types of locks:

• A worst-case minimal lock for $N$ is a lock with at least $N$ combinations and the smallest possible number of worst-case turns. Formally, a lock $L$ is worst-case minimial if $|L|\geq N$ and $\forall L'\left(|L'|\geq N\implies\textsf{WC}(L')\geq\textsf{WC}(L)\right)$.

• A worst-case optimal lock for $N$ is a minimal lock with the greatest size. Formally, a lock $L$ is worst-case optimal if $|L|\geq N$ and $\forall L'\left(|L'|\geq|L|\iff\textsf{WC}(L')\geq\textsf{WC}(L)\right)$. The set of worst-case optimal locks is the smallest set of locks which contains a worst-case minimal lock for all $N$.

• Average-case minimal locks and average-case optimal locks are defined analogously to the first two.

Worst Case

Let us consider the replacement:

$$ \{k,\ldots\}\to\{2,\frac{k}{2},\ldots\} $$

(Assume that $k$ is even.) We can see that the size is unchanged; however, the worst-case number of turns decreases by this replacement when:

$$ \frac{k}{2}+2<k \\ k+4<2k \\ k>4 $$

We can perform a similar replacement for odd $k$:

$$ \{k,\ldots\}\to\{2,\frac{k+1}{2},\ldots\} $$

This replacement increases the size, and also improves the worst-case count when:

$$ \frac{k+1}{2}+2<k \\ k+5<2k \\ k>5 $$

These replacements tell us an important fact: no worst-case minimal lock has $k_i>5$.

Now consider the replacement:

$$ \{4,\ldots\}\to\{2,2,\ldots\} $$

Under this replacement both the size and worst-case count of the lock are unchanged. This means that it is sufficient to consider locks without $4$s for now.

---

Now we move onto replacements dealing with optimal locks. The replacement:

$$ \{5,\ldots\}\to\{2,3,\ldots\} $$

increases the size of a lock without changing it's worst-case count. Therefore no optimal lock will contain a $5$. Similarly, the replacement:

$$ \{2,2,2,\ldots\}\to\{3,3,\ldots\} $$

shows that no optimal locks have more than two $2$s.

This gives us enough information to determine that all worst-case optimal locks take one of the forms:

$$ \{3\ldots\} \\ \{2,3\ldots\} \\ \{2,2,3\ldots\} \\ $$

(Note that the last form is equivalent to $\{4,3\ldots\}$) $L$, the worst-case optimal lock for $N$, has $\lceil\log_3N\rceil$ wheels. The number of $2$ wheels can be determined by looking at the fractional part, $f=\log_3N-\lfloor\log_3N\rfloor$:

• if $f\leq\log_32^2-1\approx.2619\ldots$ then $L$ has two $2$s
• if $f\leq\log_32^1-0\approx .6309\ldots$ then $L$ has one $2$
• all other wheels are $3$

Example

Take $N=10^{10}$. We have $\log_310^{10}\approx 20.9590\ldots$, so the worst-case optimal lock has $21$ wheels. The fractional part $.9590\ldots$ is larger than both cutoffs, so all wheels have $3$ digits.

The actual number of combinations is $3^{21}=10\,460\,353\,203$ and the worst-case number of turns is $3\times 21=63$.

Average Case

The arguments for the average-case minimal locks work similarly. Again we consider the transformation for even $k$:

$$ \{k,\ldots\}\to\{2,\frac{k}{2},\ldots\} $$

The average-case number of turns decreases under this replacement when:

$$ \frac{k/2+1}2+\frac{2+1}2<\frac{k+1}2 \\ k/2+1+3<k+1 \\ k>6 \\ $$

For odd $k$:

$$ \{k,\ldots\}\to\{2,\frac{k+1}{2},\ldots\} $$

This replacement decreases the average-case count when:

$$ \frac{(k+1)/2+1}2+\frac{2+1}2< \frac{k+1}2 \\ (k+1)/2+2+3< k+1 \\ k> 7 \\ $$

Thus an average-case minimal lock will consist of no wheels greater than $7$.

As before, we have an additional replacement under which both size and average count are unchanged:

$$ \{6,\ldots\}\to\{2,3,\ldots\} $$

which shows that it is sufficient to consider locks without any $6$s.

---

The replacement:

$$ \{7,\ldots\}\to\{3,3,\ldots\} $$

increases the number of combinations while leaving the average-case count unchanged, implying that no average-case optimal lock contains a $7$. Similarly, the replacements

$$ \{2,2,\ldots\}\to\{5,\ldots\} \\ \{2,3,3,\ldots\}\to\{4,5,\ldots\} \\ \{2,4,\ldots\}\to\{3,3,\ldots\} \\ \{2,5,\ldots\}\to\{3,4,\ldots\} $$

show that an average-case optimal lock will have no $2$s, except in the special cases $\{2\}$ and $\{2,3\}$. Following a similar pattern of replacements:

$$ \{5,3,\ldots\}\to\{4,4,\ldots\} \\ \{5,4,4,\ldots\}\to\{3,3,3,3,\ldots\} \\ \{5,5,\ldots\}\to\{3,3,3,\ldots\} $$

we show that an average-case optimal lock will have no $5$s, except in the special cases $\{5\}$ and $\{5,4\}$. At this point, we have shown that all average-case optimal locks consist only of $3$s and $4$s (excepting the aforementioned special cases).

Finally, consider the replacement:

$$ \{3,3,3,3,3,\ldots\}\to\{4,4,4,4,\ldots\} $$

As before, this shows that an average-case optimal lock will have at most four $3$s.

---

All average-case optimal locks take one of the forms:

$$ \{2\} \\ \{5\} \\ \{2,3\} \\ \{6\} \\ \{4,5\} \\ \{4,\ldots\} \\ \{3,4,\ldots\} \\ \{3,3,4,\ldots\} \\ \{3,3,3,4,\ldots\} \\ \{3,3,3,3,4,\ldots\} \\ $$

Given a number of combinations $N\leq 5$, the smallest average-case optimal lock is simply $\{N\}$.

For $N=6$ there are two optimal locks: $\{2,3\}$ and $\{6\}$.

For $N>6$, the smallest average-case optimal lock has $\lceil\log_4N\rceil$ wheels. The number of $3$s can be found by looking at the fractional part $f$ of $\log_4N$:

• $f\leq\log_43^4-3\approx.1699$: four $3$s
• $f\leq\log_43^3-2\approx.3774$: three $3$s
• $f\leq\log_43^2-1\approx.5849$: two $3$s
• $f\leq\log_43^1-0\approx.7925$: one $3$
• All other wheels have $4$ digits.
• Except when $17\leq N\leq 20$, where $2.0437<\log_4N<2.1610$. The above procedure dictates that we should have three wheels but four $3$s; in this case the average-case optimal lock is actually $\{4,5\}$.

Example

Take $N=10^{10}$. We have $\log_410^{10}\approx 16.6096\ldots$, so the average-case optimal lock has $17$ wheels. The fractional part, $.6096\ldots$, tells us that there is one $3$ and 16 $4$s.

The actual number of combinations is $3\times 4^{16}=12\,884\,901\,888$ and the average-case number of turns is $\frac{3+1}2+16\times\frac{4+1}2=42$.

Answer 2

1. For each $k$-digit dial, the number of tries in the worst case is $k$, and the number of tries in the average case is $\frac{k+1}{2}$.

   We get $k = 3$, giving 63 tries in the worst case (beating $k=2$ and $k=4$, both on 68) and 42 tries in the average case (beating $k=2$ on 51 and $k=4$ on 42.5). This is probably dependent on $N$: $3^{21} = 10460353203$ is just larger than $N$, but $2^{34} = 17179869184$ is much larger than $N$.

2. I haven't managed to do better than for 1.

Generalising the situation where all the dials are the same:

the number of dials is $\left\lceil{\frac {\ln N}{\ln k}}\right\rceil$; the worst case number of trials is $\left\lceil{\frac {\ln N}{\ln k}}\right\rceil k$, which is not fun to differentiate with respect to $k$. However, the minimum of $\frac{k}{\ln k}$ is $k = e$, so it's probably reasonable to expect the answer to be 3 for most values of $N$ and 2 for the rest.

I made a mistake with the average case, but 2012rcampion's answer goes further anyway so I won't correct it.