Generating Lever-Door Puzzles with JavaScript | Hacker News Reader

Generating Lever-Door Puzzles with JavaScript

blog.reconquer.online

There’s a good maths puzzle hidden in the table of levers toggling doors that has my curiosity while reading this.

Given levers that toggle at least one door and with a stipulation that no single lever toggles the state of exactly the same set of doors as another lever how many levers do you need before you can precisely toggle the state of X doors? I personally hypothesise the answer as X but welcome thought on this from those that know their linear maths.

I’ll give an example of 2 levers and 2 doors. 2 distinct levers can toggle all states of 2 doors.

Eg. Lever 1 toggles 1,1 ( notation for both doors)

Lever 2 toggles 1, 0 ( just the first door )

Since the levers xor over each other I can make a truth table of all four possible states of the doors

( 0, 0 )

( 0, 1 ) - both levers for to this

( 1, 0 ) - just the second lever

( 1, 1 ) - just the first lever

Now i could change what the levers do, eg. I could make the first lever toggle ( 0, 1 ) and I can still build the above complete truth table.

A quick sketch without stating it here and I can see I can do the same with 3 levers and 3 doors. Is it true that x unique levers can always toggle all states of x unique doors?

It requires 2^(x-1) levers to guarantee you can precisely toggle the state of all the doors. You have add other restrictions, e.g. that all doors must be controlled by at least one lever, all doors must have at least one lever that does not control them, then X levers would be sufficient.

With three doors, you have levers (1,0,0), (0,1,0), (1,1,0) and any fourth unique non null lever. In general, you have a set of 2^(x-1) levers that don't touch the Xth door, and then you replace the null lever with anything that includes the Xth door and you are fine.

That actually makes a lot of sense and means it was a coincidence that the 2 and 3 door cases needed 2 and 3 levers (accepting the 0,0,0 as a starting state - it can actually be considered another lever).

The four lever counter example (0001, 0010, 0011, 0100) - door 0 is never touched by any of these is clear. It was just that 2^(x-1) covered the respective space in the 2 and 3 lever cases, heh. Thanks!

Reply on news.ycombinator.com