Homework # 4  (Due March 11)
------------


Consider the graph Gamma consisting of a pentagon. The following
problems concern playing "Lights out" on this graph, so that clicking
in a button cyclically changes the colors of the two neighbor buttons
(but not itself).

1) For what number of colors m is the puzzle not always solvable?

2) For the initial configuration

     R
  B      B
    B  R

with three colors (N=No color, R=Red, B=Blue) give a sequence of moves
that solves the puzzle, i.e. takes it to  all lights out

     N
  N      N
    N  N

3) Is the sequence of moves in the previous question unique? (up to
   order and not counting clicking a button three times as different
   from not clicking)?

4) Playing with m=2 colors give all non-trivial moves that have no
   effect on the puzzle.

5) For m=2 give all initial configurations that cannot be solved.

6) For this last question consider a lights out puzzle with 4 buttons in
a circle  so that clicking one changes its two neighbors as well as
itself. 

 Show that the associated matrix A satisfies  

  A^2 = I_4  mod 2

where I_4 is the 4x4 identity matrix.

Explain how this fact can be used to easily solve the puzzle from any
initial configuration.