Looking for solution to “lights out” puzzle variant with multiple states
$begingroup$
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
linear-algebra combinatorics modular-arithmetic puzzle combinatorial-game-theory
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
$endgroup$
add a comment |
$begingroup$
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
linear-algebra combinatorics modular-arithmetic puzzle combinatorial-game-theory
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
$endgroup$
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21
add a comment |
$begingroup$
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
linear-algebra combinatorics modular-arithmetic puzzle combinatorial-game-theory
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
$endgroup$
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
linear-algebra combinatorics modular-arithmetic puzzle combinatorial-game-theory
linear-algebra combinatorics modular-arithmetic puzzle combinatorial-game-theory
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
edited Dec 17 '18 at 1:38
Batominovski
33.1k33293
33.1k33293
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
asked Dec 17 '18 at 1:17
kkawabatkkawabat
1304
1304
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21
add a comment |
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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.
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043430%2flooking-for-solution-to-lights-out-puzzle-variant-with-multiple-states%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
$endgroup$
add a comment |
$begingroup$
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.
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
$endgroup$
add a comment |
$begingroup$
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.
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
$endgroup$
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.
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
answered Dec 17 '18 at 6:32
Jaap ScherphuisJaap Scherphuis
4,167717
4,167717
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3043430%2flooking-for-solution-to-lights-out-puzzle-variant-with-multiple-states%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
It will be a bit different mod 4 because 2 doesn't have a modular inverse, so mod 4 doesn't form a field. But you can still do gaussian elimination on the matrix, just do all the adding and mulitplying mod 4 and try hard to pick odd numbers to make into pivots.
$endgroup$
– DanielV
Dec 17 '18 at 1:27
$begingroup$
See the 2017 article "Lights Out" and Variants by Martin Kreh in the American Mathematical Monthly which specifically treats modular colors on square grids.
$endgroup$
– Brian Hopkins
Dec 17 '18 at 3:21