2
$\begingroup$

Two friends, Amy and Ben, each use a three-disk combination lock to secure their bikes. Each disk has $10$ orientations, with integers $0$ to $9$, so there are $10^3$ possible combinations. One day, Amy and Ben compare methods for locking their bikes...

Amy: "I prefer to keep turning the disks until adding another turn would result in diminishing marginal lock-iness."

Lock-iness, $\Omega(n)$, counts the number of distinct combinations $n$ turns away from the unlocking combo.

Ben: "Wow! I do the same thing! Except that I would never only turn one disk; that'd be too easy for a thief to crack. Neglecting those cases, I also add turns until adding another would result in diminishing marginal lock-iness."

When calculating $\Omega$, Ben neglects combinations which would involve only turning one disk from the unlocking combo. He only turns two or three disks when making it lock-y.

Amy: "To clarify, I turn the first disk $n_1$ times in only one direction. Then I turn the second disk $n_2$ times in a direction, and the third $n_3$ times in a direction, where $n = n_1 + n_2 + n_3$ is the total number of turns. If the number of possible combinations $n$ turns away from my secret combo increases from $n$ to $n+1$ by less than that from $n-1$ to $n$, I stop at $n$ turns."

Consider $\Omega(n-1) = 40$, $\Omega(n) = 70$. If $\Omega(n+1) < 100$, Amy would experience diminishing marginal lock-iness (the next turn adds fewer combinations than the previous turn) and she would stop at $n$.

Ben: "We are in agreement. I stop at $m$ for the same reasons, except I don't count combinations where only one $m_i$ is nonzero; I consider it unsafe and expect a wise thief to make the same assumption. I'll leave my shiny red bike out there unwatched for a while, because it is so locked."

Ben must start by turning at least two disks, since he can't turn just one disk. He makes turns until an added turn would increase his $\Omega$ by less than the previous turn (given his "no single disk" restriction).

Amy: "Yes. I will do the same with my bike, the dirty, but equally appealing blue bike next to yours."

Unfortunately for them, a would-be thief heard this discussion and began counting states on paper.

The Problem: For a known value of $n$ turns, the thief could find every possible combination, one of which will open the lock. Whose bike will the thief choose to ride away with, if ease of thievery is the only factor?

Examples: If Amy had instead said that she only turns one disk once, $n=1$, there'd be $\Omega=6$ different combinations for a thief (knowing $n$) to try.

If Ben had said he turns two different disks once each, $n=2$ and $n_i = n_j = 1$, there would be $\Omega(2)=12$ different combos for the thief to try. Knowing both of these examples, he would try to steal Amy's to get away quickest.

If Amy makes two turns like Ben, her $\Omega(2)=18$, because she considers cases where $n = n_i = 2$, $n_j = n_k = 0$. Her marginal lock-iness from $n=1$ to $n=2$ is $\Omega(2)-\Omega(1)=12$.

enter image description here

$\endgroup$
  • $\begingroup$ Do all three wheels have exactly 10 numbers on them? $\endgroup$ – Joe Z. Sep 24 '15 at 19:59
  • $\begingroup$ Yes, I've edited the question. $\endgroup$ – Roland Sep 24 '15 at 20:07
  • 1
    $\begingroup$ Not sure if it's just me but the question is not clear to me. What are these states you are referring to? And how does turning the wheels change the number of states? $\endgroup$ – Ivo Beckers Sep 24 '15 at 20:27
  • 2
    $\begingroup$ I think I understand it now. My intuition says that the thief should always pick Ben's bike because Ben always has less states for a given $n$ because Ben's states are always a subset of Amy's states. But of course Ben's $n$ probably is an other value than Amy's $n$ and that would probably matter here $\endgroup$ – Ivo Beckers Sep 24 '15 at 22:03
  • 1
    $\begingroup$ It shouldn't really matter, but I meant for it to rule out trivial things like: n=2, Amy turns the first disk one way, then once the other way, so the lock is actually back to its unlocked combination. $\endgroup$ – Roland Sep 25 '15 at 2:45
2
$\begingroup$

Using Mathematica I generated all possible combinations for each $n$:

 n  ΩA  ΩA'   ΩB  ΩB'
---------------------
 1   6    5    0    0
 2  18   12   12   12
 3  38   20   32   20
 4  66   28   60   28
 5  99   33   96   36
 6 134   35  128   32
 7 174   40  168   40
 8 222   48  216   48
 9 278   56  272   56
10 292   14  291   19
11 308   16  302   11
12 352   44  346   44
13 388   36  382   36
14 416   28  410   28
15 292 -124  289 -121
16 400  108  394  105
17 416   16  410   16
18 424    8  418    8
19 424    0  418    0
20 292 -132  291 -127
21 424  132  418  127
22 424    0  418    0
23 424    0  418    0
24 424    0  418    0
25 292 -132  289 -129
26 424  132  418  129
27 424    0  418    0
28 424    0  418    0
29 424    0  418    0

After $n=29$ the last ten lines repeat endlessly.

We can see that:

Amy chooses $n=9$ with $\Omega_A(9)=278$, while Ben chooses $n=5$ with $\Omega_B(5)=96$.

Thus the answer is:

Ben has made a poor decision about his stopping criteria, and the thief will always choose Ben's bike!


Here's the code I used:

combos[n_] := combos[n] = Union @@ (
                            Tuples[Transpose[Mod[{#, -#}, 10]]] & /@
                              Union @@ (
                                Permutations /@ IntegerPartitions[n, {3}, Range[0, n]]
                              )
                          )

ΩA[n_] := ΩA[n] = Length[combos[n]]
ΩB[n_] := ΩB[n] = Length @ Select[combos[n], Count[0] @ # <= 1 &]

Grid @ Table[{n, ΩA[n], ΩA[n] - ΩA[n-1], ΩB[n], ΩB[n] - ΩB[n-1]}, {n, 50}]

It's actually quite fast.

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