Four buttons on a tableSliding Bolt PuzzleFour cups on a table$n$ buttons on a tableColor the Table16 Buttons, Turn them all Red or Green?Table tennis tournamentFour cups on a tableFour-by-four table with equal row and column productsRed cells in a 4x4 tableA Strange Box of ButtonsA line in Connect FourThe round tableFour coins on the corner of a rotating rectangular table
Can inspiration allow the Rogue to make a Sneak Attack?
What does "rhumatis" mean?
What is the meaning of option 'by' in TikZ Intersections
Python 3.6+ function to ask for a multiple-choice answer
Can a space-faring robot still function over a billion years?
The (Easy) Road to Code
Too soon for a plot twist?
Why are special aircraft used for the carriers in the United States Navy?
How do you make a gun that shoots melee weapons and/or swords?
Why doesn't "adolescent" take any articles in "listen to adolescent agonising"?
New invention compresses matter to produce energy? or other items? (Short Story)
Computing the volume of a simplex-like object with constraints
The Key to the Door
Why won't the strings command stop?
Using the imperfect indicative vs. subjunctive with si
What does it mean when I add a new variable to my linear model and the R^2 stays the same?
Dukha vs legitimate need
Is this nominative case or accusative case?
Ultrafilters as a double dual
Is there a math equivalent to the conditional ternary operator?
School performs periodic password audits. Is my password compromised?
ESPP--any reason not to go all in?
Why do phishing e-mails use faked e-mail addresses instead of the real one?
Quitting employee has privileged access to critical information
Four buttons on a table
Sliding Bolt PuzzleFour cups on a table$n$ buttons on a tableColor the Table16 Buttons, Turn them all Red or Green?Table tennis tournamentFour cups on a tableFour-by-four table with equal row and column productsRed cells in a 4x4 tableA Strange Box of ButtonsA line in Connect FourThe round tableFour coins on the corner of a rotating rectangular table
$begingroup$
I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle.
In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot
tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.
• A person is (repeatedly) allowed to enter the room, and press whichever buttons
she likes. After she steps out, she is told whether she succeeded to put the light
on. At the same time, a table rotates in an unknown manner.
The goal is:
to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.
As a bonus I was given:
The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.
logical-deduction combinatorics proof-without-words
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 3 more comments
$begingroup$
I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle.
In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot
tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.
• A person is (repeatedly) allowed to enter the room, and press whichever buttons
she likes. After she steps out, she is told whether she succeeded to put the light
on. At the same time, a table rotates in an unknown manner.
The goal is:
to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.
As a bonus I was given:
The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.
logical-deduction combinatorics proof-without-words
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
3
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday
|
show 3 more comments
$begingroup$
I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle.
In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot
tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.
• A person is (repeatedly) allowed to enter the room, and press whichever buttons
she likes. After she steps out, she is told whether she succeeded to put the light
on. At the same time, a table rotates in an unknown manner.
The goal is:
to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.
As a bonus I was given:
The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.
logical-deduction combinatorics proof-without-words
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle.
In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot
tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.
• A person is (repeatedly) allowed to enter the room, and press whichever buttons
she likes. After she steps out, she is told whether she succeeded to put the light
on. At the same time, a table rotates in an unknown manner.
The goal is:
to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.
As a bonus I was given:
The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.
logical-deduction combinatorics proof-without-words
logical-deduction combinatorics proof-without-words
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Jay MarJay Mar
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Jay MarJay Mar
1735
asked yesterday
Jay MarJay Mar
1735
1735
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Jay Mar is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
3
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday
|
show 3 more comments
$begingroup$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
3
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday
$begingroup$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
3
3
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday
|
show 3 more comments
2 Answers
2
active
oldest
votes
$begingroup$
$n=2^k$ button method
Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.
Induct on $k$.
If $k=0$, then one possible sequence is $(1)$.
Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.
Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).
Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).
Then a sequence for $2n=2^k+1$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_m-1,b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.
For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.
Explanation:
Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.
answered yesterday
noednenoedne
6,52711956
$endgroup$
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
add a comment |
$begingroup$
4-button method
Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.
If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".
Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out
If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".
Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.
If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".
Step 7 - Repeat Step 3
Step 8 - Repeat Step 4
If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".
Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.
If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.
Steps 11 - 16 - Repeat Steps 3 - 8
The light must be turned on at one of these steps.
answered yesterday
hexominohexomino
42.5k3128203
$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: "559"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
);
);
Jay Mar is a new contributor. Be nice, and check out our Code of Conduct.
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%2fpuzzling.stackexchange.com%2fquestions%2f80329%2ffour-buttons-on-a-table%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$n=2^k$ button method
Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.
Induct on $k$.
If $k=0$, then one possible sequence is $(1)$.
Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.
Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).
Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).
Then a sequence for $2n=2^k+1$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_m-1,b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.
For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.
Explanation:
Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.
answered yesterday
noednenoedne
6,52711956
$endgroup$
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
add a comment |
$begingroup$
$n=2^k$ button method
Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.
Induct on $k$.
If $k=0$, then one possible sequence is $(1)$.
Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.
Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).
Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).
Then a sequence for $2n=2^k+1$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_m-1,b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.
For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.
Explanation:
Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.
answered yesterday
noednenoedne
6,52711956
$endgroup$
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
add a comment |
$begingroup$
$n=2^k$ button method
Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.
Induct on $k$.
If $k=0$, then one possible sequence is $(1)$.
Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.
Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).
Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).
Then a sequence for $2n=2^k+1$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_m-1,b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.
For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.
Explanation:
Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.
answered yesterday
noednenoedne
6,52711956
$endgroup$
$n=2^k$ button method
Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.
Induct on $k$.
If $k=0$, then one possible sequence is $(1)$.
Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.
Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).
Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).
Then a sequence for $2n=2^k+1$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_m-1,b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.
For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.
Explanation:
Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.
answered yesterday
noednenoedne
6,52711956
edited yesterday
answered yesterday
noednenoedne
6,52711956
answered yesterday
noednenoedne
6,52711956
answered yesterday
noednenoedne
6,52711956
6,52711956
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
add a comment |
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
+1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^2^k - 1$ steps which seems correct.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding.
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
@hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved.
$endgroup$
– noedne
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
The explanation is very helpful, thank you.
$endgroup$
– hexomino
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
$begingroup$
@noedne Thanks for the explanation you rock :)
$endgroup$
– Jay Mar
yesterday
add a comment |
$begingroup$
4-button method
Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.
If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".
Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out
If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".
Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.
If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".
Step 7 - Repeat Step 3
Step 8 - Repeat Step 4
If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".
Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.
If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.
Steps 11 - 16 - Repeat Steps 3 - 8
The light must be turned on at one of these steps.
answered yesterday
hexominohexomino
42.5k3128203
$endgroup$
add a comment |
$begingroup$
4-button method
Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.
If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".
Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out
If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".
Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.
If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".
Step 7 - Repeat Step 3
Step 8 - Repeat Step 4
If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".
Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.
If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.
Steps 11 - 16 - Repeat Steps 3 - 8
The light must be turned on at one of these steps.
answered yesterday
hexominohexomino
42.5k3128203
$endgroup$
add a comment |
$begingroup$
4-button method
Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.
If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".
Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out
If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".
Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.
If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".
Step 7 - Repeat Step 3
Step 8 - Repeat Step 4
If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".
Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.
If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.
Steps 11 - 16 - Repeat Steps 3 - 8
The light must be turned on at one of these steps.
answered yesterday
hexominohexomino
42.5k3128203
$endgroup$
4-button method
Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.
If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".
Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out
If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".
Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.
If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".
Step 7 - Repeat Step 3
Step 8 - Repeat Step 4
If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".
Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.
If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.
Steps 11 - 16 - Repeat Steps 3 - 8
The light must be turned on at one of these steps.
answered yesterday
hexominohexomino
42.5k3128203
answered yesterday
hexominohexomino
42.5k3128203
answered yesterday
hexominohexomino
42.5k3128203
answered yesterday
hexominohexomino
42.5k3128203
42.5k3128203
add a comment |
add a comment |
Jay Mar is a new contributor. Be nice, and check out our Code of Conduct.
Jay Mar is a new contributor. Be nice, and check out our Code of Conduct.
Jay Mar is a new contributor. Be nice, and check out our Code of Conduct.
Jay Mar is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f80329%2ffour-buttons-on-a-table%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$
You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)?
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right?
$endgroup$
– hexomino
yesterday
$begingroup$
@hexomino I don't know, in the version I know you can touch only two cups per turn.
$endgroup$
– Arnaud Mortier
yesterday
$begingroup$
@ArnaudMortier Ah yes, I forgot that part.
$endgroup$
– hexomino
yesterday
3
$begingroup$
@noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle.
$endgroup$
– Jaap Scherphuis
yesterday