DOC PREVIEW
CR MATH 45 - Lights Out

This preview shows page 1-2-3-4-5-6 out of 19 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 19 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Matricesb11b12b13b14b15b21b22b23b24b25b31b32b33b34b35b41b42b43b44b45b51b52b53b54b55To 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 = b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 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 BWhere 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 1Noah 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.x11x12x13x14x15x21x22x23x24x25x31x32x33x34x35x41x42x43x44x45x51x52x53x54x55In 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

CR MATH 45 - Lights Out

Documents in this Course
Load more
Download Lights Out
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lights Out and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lights Out 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?