Lights OutNoah Flemensand ReedWillistonLights OutNoah Flemens and Reed Williston12-17-10Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonThe GameFigure: A picture of the original Tiger Toys game.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonThe GameFigure: One of the 225possible configuations.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonCorner ButtonFigure: Pressing a corner button toggles adjacent cells.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonEdge ButtonFigure: Pressing an edge button toggles adjacent cells.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonInterior ButtonFigure: Pressing an interior button toggles adjacent cells.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonDescribing the Game with Vectors and Matricesb11b12b13b14b15b21b22b23b24b25b31b32b33b34b35b41b42b43b44b45b51b52b53b54b55b11b12b13b14b15Figure: This shows our scheme for labeling each button on the gameboard.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonDescribing the Game with Vectors and Matricesb11b12b13b14b15b21b22b23b24b25b31b32b33b34b35b41b42b43b44b45b51b52b53b54b55To describe the game we will use the notation bijto describethe state of the light in the ith row and jth column. Arragingthese entries into a vector, we have a configuration for thegame:b = (b11, b12, b13· · · b21, b22· · · b55)We will describe a initial configuration by b and a solution by x.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonAx = bWe will use a 25x25 matrix A to model the relationshipbetween between the solution x and the initial configuration b.A square on the board is affected only by the adjacent squaresand thus, the sum of the presses to the adjacent buttons givesthe state of a button.b11= x11+ x12+ x21b12= x11+ x12+ x13+ x22b13= x12+ x13+ x14+ x23b14= x13+ x14+ x15+ x24b15= x14+ x15+ x25Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonAx = b1 1 0 0 0 1 0 0 0 0 · · ·1 1 1 0 0 0 1 0 0 0 · · ·0 1 1 1 0 0 0 1 0 0 · · ·0 0 1 1 1 0 0 0 1 0 · · ·0 0 0 1 1 0 0 0 0 1 · · ·..............................x11x12x13x14x15...=b11b12b13b14b15...This matrix describes the relationship between x and the firstfive entries of b. The separation highlights the two veryimportant blocks of the matrix.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonWhat is A?If we expand out every b and continue A all way down we getthis matrix:A =B I O O OI B I O OO I B I OO O I B IO O O I BWhere I is a 5x5 identity matrix, O is a 5x5 matrix of zeros andB is:B =1 1 0 0 01 1 1 0 00 1 1 1 00 0 1 1 10 0 0 1 1Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonIs it Solvable?Note that B = BT, I = IT, O = OTso,AT=BTITOTOTOTITBTITOTOTOTITBTITOTOTOTITBTITOTOTOTITBT=B I O O OI B I O OO I B I OO O I B IO O O I B= AThus, A is symmetric. This allows us to get some importantinformation out of it.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonIs it Solvable?Because A is symmetric:1The Column Space of A is equal to the Row Space of A.2b is in the Column Space of A only if it is orthogonal tothe Null Space of A.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonNullspace of AWe deduce that b can be solved only if its dot productwith the elements of N(A) is zero.A is a rank 23 matrix so the Nullspace only contains 2vectors. We will call them n1and n2.This gives us a way to check a configuration to see if it issolvable. If one of the dot products is not zero, there is nosolution.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonThe SolutionsAssume x is a solution.A(x + αn1+ βn2) =bAx + Aαn1+ Aβn2=bAx + 0 + 0 =bAx =bα, β = 1, 0n1, n2∈ N(A)We conclude that adding either of the nullspace vectors to asolution still gives us a solution.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonThe Best SolutionIf our winning strategy is x. We can see that there are actually4 winning strategies:xx + n1x + n2x + n1+ n2From these we will chose the shortest solution. This iswhatever vector has the least number of nonzero entries.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonFinding A SolutionAx = bWe use a modified binary RREF program which does notreduce the 26th column, only preforms the same rowoperations on it.Finally to get a solution we simply put A and b into anaugmented matrix and perform elimination on it.After elimination, the 26th column of the augmentedmatrix is the strategy vector.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonWinning the GameWe then take the shortest solution and think of it as a 5x5matrix again.x11x12x13x14x15x21x22x23x24x25x31x32x33x34x35x41x42x43x44x45x51x52x53x54x55In each entry of the matrix:1=push0= do not pushOnce all these are carried out, the game will be solved.Noah Flemens and Reed Williston Lights OutLights OutNoah Flemensand ReedWillistonBibliographyD. Arnold. 2001 Writing Scientific Papers in Latex.Marlow Anderson, Todd Feil Turning Lights Out withLinear Algebra, Mathematics Magazine, Vol. 71, No. 4,October 1998Oscar Martin-Sanchez, Cristobal Pareja-Flores TwoReflected Analyses of Lights Out, Mathematics Magazine,Vol. 74, No. 4, October 2001Noah Flemens and Reed Williston Lights
View Full Document