BrainDen.com - Brain Teasers
• 0

Binary lock

Question

There are n binary levers: each lever can be in position 0 or position 1.
Exactly one out of 2n possible combinations of levers opens the lock.
The lock opens immediately as soon as each lever is in proper position.
Changing position of one lever is called a move.
Suppose all levers are initially in position 0.
What is the minimal number of moves that guarantees opening the lock?
In other words: how many moves are required to test each position of levers (the worst case scenario)?

Can you also describe the optimal procedure of moving the levers?

Recommended Posts

• 0
Spoiler

Worst possible number of moves: 2n - 1

I'm still working on formalizing the pattern to follow...in my head it's almost similar to the Towers of Hanoi (but using binary)...but trying to figure it out how to describe it...

Share on other sites

• 1

Real life: I bought (very cheep) a 256MB extension card for a 80286. There were 8 dip switches and no manual. I do not know how many times each switch can be flipped, in any case, it is better to minimize the manipulation.

Look

Edited by harey
Share on other sites

• 0

.

Edited by Pickett
duplicate entry...
Share on other sites

• 0
Spoiler

This is correct, Pickett. No "extra" moves are required (obviously we cannot do better, since there are 2n-1 combinations to test).
Comparing this problem to Towers of Hanoi looks like a good insight to me, since both problems are naturally defined with exactly the same recurrence.
I've played a game today where I had to brute-force such lock. I was just testing subsequent binary numbers (thinking of levers as bits), hence I made more moves then optimal. Even after I gave this problem some thoughts, I'd still be afraid to use "optimal procedure", since I feel that the gain in speed is not worth the risk of making a mistake and starting over.

Edited by witzar

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.