Binary lock

[witzar]

There are n binary levers: each lever can be in position 0 or position 1.
Exactly one out of 2ⁿ 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?

[Pickett]

  Reveal hidden contents

Worst possible number of moves: 2ⁿ - 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...

 

[harey]

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 January 10, 2017 by harey

[Pickett]

.

Edited January 10, 2017 by Pickett
duplicate entry...

[witzar]

  Reveal hidden contents

This is correct, Pickett. No "extra" moves are required (obviously we cannot do better, since there are 2ⁿ-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 January 10, 2017 by witzar