Version of Lights-Out Puzzle Using Buttons
Date: 09/02/2004 at 12:04:32 From: James Subject: Puzzle algebra You have 36 buttons placed in a 6x6 grid. Each button can be either visible or invisible. The difference between a visible and an invisible button is that you cannot press an invisible button. When you press a button the visibility of the button and all buttons in the same column or row is inverted, i.e. the visible buttons become invisible and the invisible buttons become visible. At the beginning there is only one button in the top-left hand corner which is visible. The challenge is the following: what is the maximal number of buttons that you can make visible? I cannot get more than 32 buttons visible and I know it is possible to get 35 visible! I need to learn the algebra behind the puzzle so that I can apply it, to get more buttons visible! I need to know what specific areas of math to research (relevant topics to investigate regarding this sort of puzzle)? Thank you.
Date: 09/02/2004 at 14:46:53 From: Doctor Vogler Subject: Re: Puzzle algebra Hi James, Thanks for writing to Dr. Math. The way I would analyze this problem is by first disregarding the condition that you can't press an invisible button. Then your problem is basically the classic lights-out puzzle, as in Lights Out Puzzle http://mathworld.wolfram.com/LightsOutPuzzle.html and you can check if there is a solution by doing a little bit of linear algebra mod 2. You have 36 vectors of dimension 36 (representing what each button does), and it turns out that these 36 vectors are linearly independent. That means that there is exactly one way to get a linear combination of them that sums to whatever sum you want. And you want to find a linear combination of them that sums to a particular value--either all 36 ones, or only 34 ones and 2 zeros. Do this, and then you have a list of buttons that you need to push, and you just have to put them in some order so that your next button is always visible. Can you do that part? It turns out that your problem is *exactly* like the lights-out puzzle with two exceptions: (1) If you have no lights on (buttons visible), then you are stuck. (2) You can never turn all of the lights (buttons) on. I think you can see why both of those are true. Now I will show you how to press an invisible button. Suppose that the button at position A is invisible. It may happen that there is another button on the same row or column as A which is visible. Call this button B. Then press B, A, B. That is exactly the same as pressing the invisible A. But what happens if A is invisible and every other button on the same row and on the same column is invisible? Then you can find two buttons C and D not on the row or column with A so that C is visible and D is invisible, and C and D are on the same row (or column). The only time this is not true is if all of the buttons are invisible (exception 1) or if pressing A would turn all of the buttons visible (exception 2). Then let B be the button on A's row and C's column (or vice-versa; it doesn't matter) and press C, B, A, B, D, C, D. This is exactly the same as pressing the invisible button A. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 09/24/2004 at 09:27:20 From: James Subject: Puzzle algebra Hi. I've just read your reply and I'm still having difficulty understanding the algebraic theory underlying the puzzle. Having looked at the lights out puzzle I see the similarities, except in my puzzle you cannot press invisible buttons and pressing a visible button inverts all the buttons in the same row and column not just the adjacent buttons (as in lights out puzzle). I understand how to press an invisible button and have actually scored 35 on the puzzle now, more by luck than by applying the algebraic theory which is what I want to be able to do. My problem is I can see how there are 36 vectors but not why they are LI, and how to find a linear combination of them to sum to 35 ones, for example. Therefore I can't get a list of buttons which I need to press. Thanks again for your help.
Date: 09/24/2004 at 12:59:28 From: Doctor Vogler Subject: Re: Puzzle algebra Hi James, I will make a simple example for you of this kind of puzzle. It won't be quite like yours or like the lights-out puzzle, so that you can see how this method works in general. Suppose we have four buttons, which I will call 1, 2, 3, and 4: 1 2 3 4 Each button can also light up. Pushing button 1 will turn on or off (change the state of) buttons 2 and 3. Pushing button 2 will turn on or off buttons 2 and 4. Pushing button 3 will turn on or off buttons 1, 2, and 4. And pushing button 4 will turn on or off buttons 1 and 2. Let's say the buttons start out with 2 and 4 on, and 1 and 3 off. Now let's suppose I push a whole bunch of buttons, with little regard to what's happening, and with no real rhyme or reason. When I'm all done, let's say that I pushed button 1 a total of "a" times, and I pushed buttons 2, 3, and 4 each a total of "b," "c," and "d" times, respectively. Now I want to know what lights are on. So let's look at the first light. Well, it turns out that it doesn't matter what order I pushed the buttons in. Every time I pushed on one of the buttons 3 or 4, the light changed. It didn't do anything when I pushed buttons 1 or 2, and it started out off. So let's say that 0 means off and 1 means on, and then button ends up being on if c + d is odd, and off if it is even. Another way of saying this is c + d (mod 2) gives the state of button 1. Similarly, 1 + a + b + c + d (mod 2) gives the state of button 2, and a (mod 2) gives the state of button 3, and 1 + b + c (mod 2) gives the state of button 4. Since the states all depend on a, b, c, and d mod 2, it really doesn't matter what those numbers actually are, only whether they are odd or even - that is, it only matters what a, b, c, and d are mod 2. Now let's suppose that I wanted all the lights off. Then I want a solution in a, b, c, and d to the simultaneous linear equations c + d = 0 (mod 2) 1 + a + b + c + d = 0 (mod 2) a = 0 (mod 2) 1 + b + c = 0 (mod 2) or c + d = 0 (mod 2) a + b + c + d = 1 (mod 2) a = 0 (mod 2) b + c = 1 (mod 2) which can also be written with matrices as [ 0 0 1 1 ] [ a ] [ 0 ] [ 1 1 1 1 ] [ b ] = [ 1 ] (mod 2) [ 1 0 0 0 ] [ c ] [ 0 ] [ 0 1 1 0 ] [ d ] [ 1 ] and now we just have a linear algebra problem. If we wanted all of the lights on, then our equations would be c + d = 1 (mod 2) 1 + a + b + c + d = 1 (mod 2) a = 1 (mod 2) 1 + b + c = 1 (mod 2) or [ 0 0 1 1 ] [ a ] [ 1 ] [ 1 1 1 1 ] [ b ] = [ 0 ] (mod 2). [ 1 0 0 0 ] [ c ] [ 1 ] [ 0 1 1 0 ] [ d ] [ 0 ] Linear algebra will tell you that if the rows of the matrix are linearly independent (if the matrix has nonzero determinant), then no matter what vector you have on the right (what initial or final state of lights you have or want), there is exactly one correct choice (mod 2) for the four numbers a, b, c, and d. You can find it by inverting the matrix or (a little more efficient) Gaussian elimination, or some other method. If the rows are *not* linearly independent, then some choices of the vector on the right will have *no* solutions, and other choices of the vector on the right will have several solutions. In fact, if the height and width of the matrix (the number of buttons/lights there are) is n, and the rank of the matrix is r (nonzero determinant means r=n, otherwise r<n), then the nullspace of the matrix has dimension n-r, so there are 2^(n-r) elements of the nullspace, which means that every vector that *has* a solution, has exactly 2^(n-r) of them. And there will be 2^r vectors that *have* solutions, which means there will be 2^n - 2^r vectors that have *no* solution. In your case, you have 36 buttons and 36 lights. So your matrix will have length and width n=36. I understand that it's a pretty big matrix, so I would recommend using a graphing calculator or a math program to work with it. (I used Mathematica.) You can write out the matrix by considering which lights each button changes. (I was honestly surprised that the rows were linearly independent.) And then you can pick 1 of the 36 lights to start with, and 35 of the 36 lights that you want on, and that gives you a vector to use on the right. Then use your calculator or computer to solve the matrix, and that will tell you which buttons to press. Using the techniques from my last message for pressing invisible buttons, you can press all of them in turn (in almost any order, so long as you never turn them all off or all on). - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.