• 0
witzar

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?

0

Share this post


Link to post
Share on other sites

4 answers to this question

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

 

0

Share this post


Link to post
Share on other sites
  • 0

.

Edited by Pickett
duplicate entry...
0

Share this post


Link to post
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
0

Share this post


Link to post
Share on other sites
  • 0

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

https://en.wikipedia.org/wiki/Gray_code

Edited by harey
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.