Diff from to

# File t2/toggle.html.wml

• Ignore whitespace
` <a href="#One_Dimensional_Board">Analysis of a 1-D Toggle-board</a><br />`
` <ul>`
` <li>`
`-<a href="#lemma1">Lemma 1: 1D is always solveable if vector 100..00 can be`
`+<a href="#lemma1">Lemma 1: 1D is always solvable if vector 100..00 can be`
` formed.</a>`
` </li>`
` <li>`
`-<a href="#lemma2">Lemma 2: 1D is always solveable only for N=3k and`
`+<a href="#lemma2">Lemma 2: 1D is always solvable only for N=3k and`
` 3k+1</a>`
` </li>`
` </ul>`
` <a href="#Two-Dimensional-Board">Main (2-D) Theorems</a><br />`
` <ul>`
` <li><a href="#theorem1">Theorem 1:`
`-(3k+2)^2 boards are not solveable for every state.</a>`
`+(3k+2)^2 boards are not solvable for every state.</a>`
` </li>`
` <li>`
`-<a href="#theorem2">Theorem 2: 3k and 3k+1 2-D boards are solveable`
`+<a href="#theorem2">Theorem 2: 3k and 3k+1 2-D boards are solvable`
` for every state.</a>`
` </li>`
` <li>`
`-<a href="#theorem3">Theorem 3: Solveable 3k+2 boards can be solved`
`+<a href="#theorem3">Theorem 3: Solvable 3k+2 boards can be solved`
` by the one way algorithm.</a>`
` </li>`
` <li>`
` <h3 id="lemma1">Lemma 1</h3>`
` `
` <p>`
`-A 1-D toggle field is solveable for every state if (and only if)`
`+A 1-D toggle field is solvable for every state if (and only if)`
` the vector 100...000 can be formed as combination of the`
` presses.`
` </p>`
` -------------`
` 001000...00`
` and from here it can be proved inductively that the vectors with all 0s`
`-and one 1, are solveable. Since this is a basis of {1,0}^N then every state`
`-is solveable. (i.e contained in Sp{Presses} )`
`+and one 1, are solvable. Since this is a basis of {1,0}^N then every state`
`+is solvable. (i.e contained in Sp{Presses} )`
` `
` </pre>`
` `
` <h3 id="lemma2">Lemma 2</h3>`
` `
` <p>`
`-A 1-D toggle field of size N is solveable for every state if N = 3k`
`+A 1-D toggle field of size N is solvable for every state if N = 3k`
` or N = 3k+1 and isn’t if N = 3k+2 for some non-negative integer`
` k.`
` </p>`
` contains 1 at the top-left cell and below a Presses Matrix of size N-2) =`
` det (PM(N-1)) XOR det(1 * PM(N-2)) = det(PM(N-1)) XOR det(PM(N-2)).`
` `
`-Hence, it’s a XOR of the detereminants of the two previous matrixes. (A`
`+Hence, it’s a XOR of the determinants of the two previous matrixes. (A`
` boolean Fibonacci series :-) )`
` `
` Recursively, we get a repeating sequence of`
` `
` Matrixes with a zero determinant cannot form every vector, and vice versa.`
` `
`-It can also be proved (at least for the solveable cases) using Lemma 1.`
`+It can also be proved (at least for the solvable cases) using Lemma 1.`
` For N=3k 1000....000 can be formed by:`
` 1110000...0000         XOR`
` 0001110...0000         XOR`
` 11111111111111111`
` `
` and thus the dimension of the span is less than n, and so not every state is`
`-included in it, and is solveable.`
`+included in it, and is solvable.`
` `
` `
` `
` `
` <h3 id="theorem1">Theorem 1</h3>`
` <p>`
`-2-D (3k+2) * (3k+2) boards are not solveable for every state.`
`+2-D (3k+2) * (3k+2) boards are not solvable for every state.`
` </p>`
` `
` <pre>`
` 00000.111`
` 00000.011`
` `
`-and Lemma 2 proved that for N=3k+2 it has unsolveable states. If some`
`+and Lemma 2 proved that for N=3k+2 it has unsolvable states. If some`
` formations of the first row cannot be solved by any combination of the`
` presses on the block, much less the entire board can be solved for every`
` state.`
` <h3 id="theorem2">Theorem 2</h3>`
` `
` <p>`
`-2-D boards of size 3k * 3k or (3k+1) * (3k+1) are solveable for`
`+2-D boards of size 3k * 3k or (3k+1) * (3k+1) are solvable for`
` every state.`
` </p>`
` `
` <pre>`
` Proof:`
` If we restrict ourselves to the presses on cells of one column, then we get`
`-an array of rectangular vectors with a fixed horizontal postion and width`
`-and a y-dimensions that resemble the 1-D toggle-squares vector set. e.g:`
`+an array of rectangular vectors with a fixed horizontal position and width`
`+and some y-dimensions that resemble the 1-D toggle-squares vector set. e.g:`
` 110000`
` 110000`
` 000000`
` and the same for every other column. Now, if we look on any row of cells,`
` we will see that the “sticks” that were generated from the various columns`
` in that row are also the 1-D TogSqrs sequence. Because N=3k,3k+1 again,`
`-every row is solveable for all states, and therefore, the entire board is`
`-solveable for all states.`
`+every row is solvable for all states, and therefore, the entire board is`
`+solvable for all states.`
` `
` Diagram:`
` 110000 , 111000 , 011100 , 001110 , 000111 , 000011`
` `
` <h3 id="theorem3">Theorem 3</h3>`
` <p>`
`-Solveable states of 3k+2 boards can be solved by the one-way`
`+Solvable states of 3k+2 boards can be solved by the one-way`
` algorithm.`
` </p>`
` `
` In a 1-D board where N=3k+1 the two-way method as is, will ping the`
` possible remaining 1 back and forth between the two edges. Therefore if`
` there is a state of 1000...0 than one should use the leftmost press to`
`-change it into 0100...000. Then, by repeatetive pressing to the right`
`+change it into 0100...000. Then, by repetitive pressing to the right`
` of the leftmost filled square, one gets to the 0...11 state, which is`
` afterwards cleared.`
` `
` 1. In N=3k+1 the two-way method as is, will ping the possible remaining`
` 1 back and forth between the two edges. Therefore if there is a state`
` of 1000...0 than one should use the leftmost press to change it into`
`-0100...000. Then, by repeatetive pressing to the right of the leftmost`
`+0100...000. Then, by repetitive pressing to the right of the leftmost`
` filled square, one gets to the 0...11 state, which is afterwards`
` cleared.`
` `
` <h2 id="dim_press_span">The Dimension of the Presses Span in 3k+2 boards</h2>`
` `
` <pre>`
`-(3k+2)*(3k+2) boards are not solveable for every state. The solveable`
`+(3k+2)*(3k+2) boards are not solvable for every state. The solvable`
` states form a vector field which is formed by the spanning all the`
` presses. Since, in this case it does not include all the states, I`
` wondered if we can calculate its dimension or characterize it somehow.`
` every possible state (Lemma 1).`
` `
` Since the 1-D clearing mechanism for 3k+2 uses only the leftmost 3k+1`
`-cells to clear every solveable state (part of Theorem 3), then`
`+cells to clear every solvable state (part of Theorem 3), then`
` their presses are a valid basis for this linear space.`
` `
` The one-way - one-way clearing algorithm which was proved in Theorem 3,`
` uses only a (3k+1)*(3k+1) square of presses to solve the entire board.`
` Ergo, the dimension is (3k+1)^2 or less. I believe it _is_ (3k+1)^2 and`
` I think I can prove it by showing that the presses of a corner`
`-(3k+1)*(3k+1) are linearly independant. In the boolean field the`
`+(3k+1)*(3k+1) are linearly independent. In the boolean field the`
` meaning is that any number of them other than zero XORed together will`
` not generate the clear state.`
` `
` certain number of presses in the square can form the clear state. If`
` so, then Pr(4,4) cannot be one of them because it is the only press`
` that can affect square (5,5). Moreover, Pr(3,4) and Pr(4,3) cannot be`
`-included either, becuase, once Pr(4,4) is eliminated they are the only`
`+included either, because, once Pr(4,4) is eliminated they are the only`
` ones that can affect (4,5) and (5,4) respectively. And so forth,`
` proving that that all the presses of cells (1,4)-(4,4) and (4,1)-(4,4)`
` cannot be part of the zero sum.`
` `
` The same can be deduced for the next layer starting from Pr(3,3), which`
` is the only vector left that can affect square (4,4). And so-on for the`
`-other layers, proving that they are a linearly independant set of`
`+other layers, proving that they are a linearly independent set of`
` vectors. In conclusion, there cannot be less than (3k+1)^2 vectors that`
`-span the space of the solveable states of (3k+2) boards.`
`+span the space of the solvable states of (3k+2) boards.`
` `
` </pre>`
` `