8
$\begingroup$

I have a nice mountain bike, which I use on a daily basis. I always lock my bike.

Today, I awoke and to my surprise the bike was stolen. It startled me because it is locked with a really expensive combination lock. I walked around the vicinity and found it lying still locked in a shrubbery. Apparently, someone must have carried it away, tried to break the lock open in a more quieted neighbourhood but failed to do so.

I need to unlock my bike in order to ride it (duh). The trouble is that two of the four wheels with the numbers present on them have been removed. I can still turn the wheels, but I do not know which number I'm "entering" as a combination.

However, I have noticed that there are two cavities in the underlying smooth wheels with no numbers on them. I know for a fact that these cavities are present on the same numbers, but I can't tell them apart and do not know under which number the cavities were initially.

Artists Impression:

(Note: The two cavities are under the same number, but I don't know whether it is 2 or any other number, I just had to draw the cavities somewhere...)

enter image description here

My combination is 4 2 7 0

I can enter 4 2, but I do not know the other two numbers I'm entering it. I can unlock my lock in $10^2$ trials, but using the additional information I can't help but think that I could need even less trials.

Optional Bonus

If that is too easy, try and solve the problem for $n$ additional wheels.

$\endgroup$
  • 6
    $\begingroup$ The funny thing is the the exact same thing did in fact happen to me. (Hint to the thieves: No, the combination of my new lock isn't 4270) $\endgroup$ – Narusan Nov 19 '17 at 20:55
11
$\begingroup$

You can use the information that the cavities mark the same number to

rotate the last two wheels relative to each other such that their distance is 7 steps (first wheel 7 steps further than secon wheel). Then you rotate them together through the $10$ possible positions (or until the lock is opened). If the lock doesn't unlock, you did it with the wrong combination of cavities. In that case you need another $10$ steps for the other combination. This gives a total of $20$ steps (at most).

In the case of $n$ additional wheels it works in a similar way:

  1. First, pick a random cavity in each of the wheels and assume it marks the number 0. Under this assumption, enter your code. If this doesn't open your lock, rotate all $n$ wheels by 1 until you tried all $10$ possible orientations.
  2. After that, you need to account for the fact, that all wheels have 2 indistinguishable cavities, that means that relative to the $1$st wheel you can switch the cavity that is assumed to be 0 to the opposite cavity on each of the other $n-1$ wheels. This gives a total of $2^{n-1}$ possible permutations of cavity assignments.
    For each assignment permutation you have to:
    1. Enter your code.
    2. Repeat the $10$ rotation steps.
    Continue switching the 0-assigned cavity and try $10$ rotation steps until you tried all $2^{n-1}$ possible permutations of cavity assignments.
Like this you need at most $10 \cdot 2^{n-1}$ attempts instead of $10^n$.

$\endgroup$
  • $\begingroup$ There are two cavities on each wheel however, and I don't know which one is which. $\endgroup$ – Narusan Nov 19 '17 at 21:01
  • $\begingroup$ @Narusan Oh you're right. I've edited my answer to account for that. $\endgroup$ – A. P. Nov 19 '17 at 21:06
  • $\begingroup$ Yes, it is given that they are on the opposite side. // Okay, that was too easy. I found the incident funny and decided to share it here. If you want to, go for the optional bonus for a more complex problem. // What is the site policy, should I immediately accept a right answers (other sites like PPCG have a policy of not accepting answers too early). $\endgroup$ – Narusan Nov 19 '17 at 21:09
  • $\begingroup$ @Narusan Usually one accepts an answer if you don't expect a better one. But you can also accept a newer answer, if it is better. $\endgroup$ – A. P. Nov 19 '17 at 21:28
  • $\begingroup$ @Narusan I've improved the explanations and also clarified the maximal number of steps. Hopefully it is more clear now. $\endgroup$ – A. P. Nov 20 '17 at 20:31
9
$\begingroup$

I know for a fact that these cavities are present on the same numbers

Which implies that

The markings were made by the manufacturer, and exist below the same number on the other wheels as well. Therefore, we can learn what number the marking represents by taking note as we remove the numbers from one of the other wheels.

$\endgroup$
  • $\begingroup$ I‘d still have $2^3$ solutions to check and an even further damaged lock for the future. But yes - while not being the intended solution - this is a solution as well, in a way. $\endgroup$ – Narusan Nov 19 '17 at 22:05
  • $\begingroup$ @Narusan By this method, you figure out which number the marking corresponds to. As such, you can just turn the wheels to their proper place. You're going to keep using the lock? $\endgroup$ – Carl Nov 19 '17 at 22:15
  • $\begingroup$ Yes, I will keep using the real lock. The other answer yields me the number the marking corresponds to as well - once I have solved the combination - and for the future it will be only two wheels with less markings. // The reason why I liked the puzzle is that it shows how seemingly mundane information can lead to a drastic decrease in required trials ($10*2^n$ vs $10^n$). Your solution is also a solution, it’s just not the „desired“ one, but I appreciate the lateral thinking. Maybe I should point out that using the accepted approach I had already unlocked my bike prior to posting here, it was $\endgroup$ – Narusan Nov 19 '17 at 22:18
  • $\begingroup$ [cont‘d] afterwards that I have written this post and considered general cases for the problem. $\endgroup$ – Narusan Nov 19 '17 at 22:21
  • 2
    $\begingroup$ As the number of wheels increases, I bet this solution gets more and more attractive. $\endgroup$ – Steve V. Nov 20 '17 at 6:02
0
$\begingroup$

Let's assume that left wheel is already set to 7 (like if the cavity was at 7), turn second wheel 7 positions down to get needed offset. Not open yet? Turn both wheels down (or up), repeat 10 times until unlocked.

$\endgroup$
  • 2
    $\begingroup$ Although this answer is correct, it has already been posted $\endgroup$ – Carl Nov 20 '17 at 5:16
  • $\begingroup$ You need to do this 20 times (as the accepted answer shows) because you can’t tell cavities apart. $\endgroup$ – Narusan Nov 20 '17 at 18:28
  • $\begingroup$ Yup, I've noticed that after posting, sorry :) $\endgroup$ – Ivan Nov 22 '17 at 20:54
  • $\begingroup$ @Narusan why do you need to tell cavities apart? You know the combination, you know that cavities are at the same number, and you know the direction of numbers, so you just set relative combination and then rotate all wheels as many times as there are numbers on the wheel. $\endgroup$ – Ivan Nov 22 '17 at 20:57
  • $\begingroup$ But there are two exact same cavities on each wheel, so you don’t know whether cavity 1 corresponds to number 0 or the opposite number 5. $\endgroup$ – Narusan Nov 22 '17 at 21:00

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.