Timeline for Four buttons on a table
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2019 at 13:57 | comment | added | OHO | @noedne This example for n=4 shows that there is a gap in the proof. Do you agree? | |
| Mar 21, 2019 at 11:04 | comment | added | noedne | Let us continue this discussion in chat. | |
| Mar 21, 2019 at 10:52 | comment | added | OHO | I don’t think we can fix where to start appliying the moves. When we enter the room, all the buttons look the same. | |
| Mar 21, 2019 at 10:12 | comment | added | noedne | @OHO We just define $C$ to line up with $b_i$. We also have to fix a choice of where to start applying the moves. | |
| Mar 21, 2019 at 9:50 | comment | added | OHO | How can we do that? What I don’t see is that we have to fix this choice of orientation for C from the start, but afterwards the table can be rotated in anyway which can destroy this alignment between C and $b_i$. I mean, when you step back into the room, you don’t know where to start applying $b_i$ to line up with C. | |
| Mar 21, 2019 at 9:31 | comment | added | noedne | @OHO I wrote that $C$ is an xor of neighbors of $A$ and $B$, but I was not clear which of the two orientations of neighbors to choose. The choice is the one such that neighboring pairs line up with the button positions that we apply duplicate values to in $b_i$. The subtle but important thing to note is that just like our moves, $C$ is always oriented by button position, not the buttons themselves. | |
| Mar 21, 2019 at 9:10 | comment | added | OHO | Yes, but if the table is rotated by one position, it’s not true anymore as in the example above. Can you explain what’s wrong with the example? | |
| Mar 21, 2019 at 6:39 | comment | added | noedne | @OHO Sorry, I misread your question. $C$ is fixed when $b_i$ is applied because it applies the same sequence to both $A$ and $B$, so it cancels out in the xor. | |
| Mar 21, 2019 at 5:08 | comment | added | OHO | Sorry, still confused. Suppose the table is 0000 (xor first and second pairs, we get C=00). If we apply $b_2=1100$ starting from the second switch, we get 0110 and C changes to 11. Did I misunderstand the definition of C? | |
| Mar 20, 2019 at 15:23 | comment | added | noedne | @OHO Because xor is commutative and associative, $C=A\oplus B$ is the same whether we xor $A$ or $B$ with $(b_i)$. | |
| Mar 20, 2019 at 9:59 | comment | added | OHO | I don't understand why $C$ remains fixed when $b_i$ is applied. I think $C$ can change when $b_i$ is applied if the table is rotated by one position. | |
| Mar 13, 2019 at 7:08 | comment | added | noedne | In the explanation above, the solution for $2n$ uses the solution for $n$ to cycle through the configurations of $C$ and to cycle through the configurations of $A$ and $B$ given $C$. | |
| Mar 13, 2019 at 7:04 | comment | added | Jay | @noedne Thanks, how does the induction assumption for $n=2^k$ supports your answer for $2n=2^k+1$ buttons ? | |
| Mar 12, 2019 at 16:22 | comment | added | noedne | @JayMar There are $m+1$ copies of $(b_i)$ (with length $m$) separated by the $m$ elements of $(c_i)$, so $(m+1)\cdot m+m=m^2+2m$. Really, $m=2^n-1$ and $m^2+2m=2^{2n}-1$. | |
| Mar 12, 2019 at 14:52 | comment | added | Jay | @noedne may I ask how did you get the $m^2 + 2m$ ? | |
| Mar 6, 2019 at 12:50 | vote | accept | Jay | ||
| Mar 6, 2019 at 12:12 | comment | added | hexomino | The explanation is very helpful, thank you. | |
| Mar 6, 2019 at 12:04 | comment | added | noedne | @hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved. | |
| Mar 6, 2019 at 12:01 | history | edited | noedne | CC BY-SA 4.0 |
Added explanation
|
| Mar 6, 2019 at 11:26 | comment | added | hexomino | 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. | |
| Mar 6, 2019 at 11:21 | comment | added | hexomino | +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. | |
| Mar 6, 2019 at 10:58 | history | answered | noedne | CC BY-SA 4.0 |