Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 

Associated Topics:
High School Permutations and Combinations
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/