4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Are the only three possible results from testing the lock "nothing," "click," and "open?" Or do we get some information about how many wheels are in the correct position? Also, is the lock guaranteed to be in a non-clicking position at the start or are the wheels randomly positioned initially? $\endgroup$ – 2012rcampion Aug 22 '15 at 23:03
  • $\begingroup$ Yes, "nothing", "click" and "open". You may have to turn the whole wheel to find a click. The lock is in a random position. $\endgroup$ – Rohcana Aug 22 '15 at 23:04
  • 1
    $\begingroup$ I remember finding a lock like that in my basement one day. And yes, I went through the 999 attempts way. I eventually found it around 600ish $\endgroup$ – warspyking Aug 22 '15 at 23:13
  • $\begingroup$ Does your 30 tries worst case take into account the cases when you start in a position that clicks? Also, shouldn't it be 9 tries per digit (since if 0-8 haven't clicked, 9 is guaranteed to be correct)? $\endgroup$ – 2012rcampion Aug 23 '15 at 1:25
  • $\begingroup$ @2012rcampion Remember that, even if we know 9 is the correct answer, we still have turn the wheel to make it 9, otherwise we won't be able to unlock the lock. In other words, our aim is to unlock the lock, not find the key. $\endgroup$ – Rohcana Aug 23 '15 at 1:28
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I wish I could upvote it a thousand times. This is thousand times better than my intended solution. This is the definition of beautiful. $\endgroup$ – Rohcana Aug 23 '15 at 6:21
  • $\begingroup$ @Anachor What was the intended solution? (Alternatively: is my answer "beautiful" but also wrong?) $\endgroup$ – 2012rcampion Aug 23 '15 at 6:25
  • $\begingroup$ The "all wheels equal" part was just equation (and some calculas like in Peter's answer). The general part was derived from the previous parts with a lot of casework, but nowhere as elegantly as these. There seems to be a slight inconsistency with my results, but I couldn't find any error in yours, so I will recheck mine and let you know. $\endgroup$ – Rohcana Aug 23 '15 at 6:30
  • $\begingroup$ Yes, it is perfectly correct. The inconsistency results because when faced with multiple optimal choices, my solution sticks to the smallest one. $\endgroup$ – Rohcana Aug 23 '15 at 9:46
  • $\begingroup$ @Anachor I see, my solution goes exactly the opposite way (i.e. an optimal lock is the largest minimal lock for a given $N$). $\endgroup$ – 2012rcampion Aug 23 '15 at 17:12
4
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ You are correct on $N=10^{10}$. If you experiment further, you should reveal something. $\endgroup$ – Rohcana Aug 22 '15 at 22:06
  • 2
    $\begingroup$ @Anachor, I think I will mainly reveal that I should have been in bed half an hour ago. $\endgroup$ – Peter Taylor Aug 22 '15 at 22:09
  • $\begingroup$ I'm getting a different result for the minimum of $(k+1)/\log k$: $$\partial_k(k+1)/\log k=0 \\ \frac{\log k-1-1/k}{\log^2 k}=0 \\ \log k=1+1/ k \\ k\approx 3.5911$$ $\endgroup$ – 2012rcampion Aug 23 '15 at 6:38
  • $\begingroup$ @2012rcampion, which proves my point about being too tired. I minimised $k+k/\log k$. $\endgroup$ – Peter Taylor Aug 23 '15 at 7:07

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.