Lock problem -need a mathematical proof

[musicgold]

Hi,

There is a 2x2 matrix lock with one key in each cell. A key is nothing but a straight lever which can either be either in vertical or horizontal state. Please see the attached picture. The lock opens only when all the levers are horizontal. However, when you change the state of the lever in a cell, say cell A, the levers of all the cells in the same row and column as cell A switch their states. The question is if we can start with the levers in any state and open the clock by turning the levers.

I am able to solve this mechanically, irrespective of the state of levers at the beginning. However I want to be able to prove it using some math, but not sure how I can go about it. Can anybody please help me?

This puzzle is a subset of a bigger puzzle involving a 4x4 matrix. I think if I learn to prove how the 2x2 lock can always be solved, I can extend it to the 4x4 lock.

Thanks,

MG.

 

[awkward]

Suppose you want to change the state of the key in the (1,1) position while leaving all the other keys unchanged. Just toggle (1,1) and all the other keys in the same row and column-- i.e. (1,2) and (2,1). The key at (1,1) has changed state 3 times and hence is now in a new state, while all the other keys have changed state twice and hence are unchanged.

Repeat this operation (toggle the key and all the other keys in the same row and column) for each key you want to change state.

 

[airborne18]

Look up hanoi tower. that is what you are looking for, same principle. You need to figure out the worst case, as awkward I think has done, and the proof is a recursion problem. Recursion problems scale nicely.

 

[musicgold]

Look up hanoi tower. that is what you are looking for, same principle.

Thanks airborne. I looked at some hanoi tower solutions and found that they mostly focus on proving the number of steps required to solve a tower. For example page 4 of http://www.cs.cmu.edu/~adamchik/21-127/lectures/induction_1_print.pdf" .

On the other hand what I am trying to do is to prove that irrespective of the starting state, one can always open this lock. I don't know the math language required to state that fact.

Also please see the attached document showing all possible starting states and steps to solve the lock. The yellow cell represents the key that was turned to get to the next state. 0 = horizontal key, 1= vertical key.

 

[airborne18]

Okay.. look at my doc. You only have 1 solution to the problem. That is line 2.

You have set S and each elment of S is a state of the matrix. There is only one state that maps to the solution. So there is some function that maps S onto S until it it results in the solution.

If you look at my document you will see that line 2 is the solution. The rest of the operations on each line simply recurse through the set of states.

I quicky modified your doc, but you get the point. Now it can take from 1 - n iterations to get to the solution, but that is a different side of this.


But I believe this angle will give you a complete solution and a proof. I may stand corrected.

 

[musicgold]

airborne18,

Thanks. I get your point about there being only one solution and that the other operations just recurse through different states to get to the solution state.

However, I am still not clear as to how to prove this in terms of a set of equations. Could you point me to a resource where I can read up more on this topic?

Thank you.