Sunday, March 26, 2017

linear algebra - Looking for solution to "lights out" puzzle variant with multiple states




Recently in World of Warcraft, there is a puzzle that is very similar to the "lights out" puzzle where a player needs to flip switches to turn all the lights into a specific color (in this case yellow, green, red, white). I have seen other solution to the lights out problem using linear algebra however all these uses only 2 states (on or off).



I haven't ever ran into a system of linear equation with modular operation before and would like some help solving something like:



  L_1 = ((s_1 + s_2 + ...s_n + c_1 ) mod 4)

L_2 = ((s_1 + s_2 + ...s_n + c_2 ) mod 4)

...


L_n = ((s_1 + s_2 + ...s_n + c_n ) mod 4)


where each L has some linear combination of s + constant mod 4


Answer



You can solve the mod 4 version like two instances of the mod 2 version.



First treat states $1$ and $3$ as if they are switched-on lights, and states $0$ and $2$ as if they are switched-off lights. Solve this as the normal lights out. You are essentially just working mod $2$, making everything even. At the end of this stage, all lights are either $0$ or $2$.



Then solve the rest as another two-state lights out puzzle, where $2$ is the switched-on state and $0$ is a switched-off state. The only difference is that the moves you do consist of double button presses. A double button press skips over the $1$ and $3$ states, and toggles lights between the $0$ and $2$ state.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...