CR MATH 45 - The Mathematics of Quatrainment - D63165

Home> Schools> College of the Redwoods> Mathematics (MATH) > MATH 45> The Mathematics of Quatrainment

DOC PREVIEW

CR MATH 45 - The Mathematics of Quatrainment

School name College of the Redwoods

Course Math 45- Linear Algebra

Pages 19

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

Save

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

Subscribe for instant access Get instant access

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

Subscribe for instant access Get instant access

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

Subscribe for instant access Get instant access

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

Subscribe for instant access Get instant access

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

Subscribe for instant access Get instant access

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

Subscribe for instant access Get instant access

Premium Document

Do you want full access? Go Premium and unlock all 19 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Unformatted text preview:

The Mathematics of QuatrainmentFinding the SolutionLoran Briggs and Daniel McBrideCollege of the RedwoodsEureka, CA 95501, USADecember 17, 2010AbstractThe game of Quatrainment is a simple game where you flip over tiles to makea 4 by 4 gird look like another target 4 by 4 grid. This is an example of afinite-state machine. In this presentation, we will be discussing our method offinding a unique solution to any quatrainment game using the fewest numberof moves possible. We will go through the rules of the game, figuring outwhether or not there is a solution to every game, how to find a solution, aswell as our program which finds the quickest solution to the game.Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 2 / 19OverviewSetup and GoalRulesBase Two SystemsIs a Solution Always Possible?The Solution AlgorithmLoran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 3 / 19Setup and GoalStarting GridXXX XX XXTarget GridXXXXX XXLoran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 4 / 19RulesCorner Cell Selected. Inner Cell SelectedEdge Cell SelectedLoran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 5 / 19Base Two SystemFour possibilities when adding in base two:0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 01 0 0 01 1 0 10 0 1 00 1 0 1+0 0 0 01 0 0 01 1 0 01 1 1 0=1 0 0 00 1 0 11 1 1 01 0 1 1Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 6 / 19Is a Solution Always Possible?First we need to define our moves in the form of 4 × 4 matrices.M1=1 1 1 01 1 0 01 0 0 00 0 0 0M2=1 0 1 00 1 0 00 0 0 00 0 0 0M3=0 1 0 10 0 1 00 0 0 00 0 0 0M4=0 1 1 10 0 1 10 0 0 10 0 0 0M5=1 0 0 00 1 0 01 0 0 00 0 0 0M6=0 1 0 01 1 1 00 1 0 00 0 0 0M7=0 0 1 00 1 1 10 0 1 00 0 0 0M8=0 0 0 10 0 1 00 0 0 10 0 0 0M9=0 0 0 01 0 0 00 1 0 01 0 0 0M10=0 0 0 00 1 0 01 1 1 00 1 0 0M11=0 0 0 00 0 1 00 1 1 10 0 1 0M12=0 0 0 00 0 0 10 0 1 00 0 0 1M13=0 0 0 01 0 0 01 1 0 01 1 1 0M14=0 0 0 00 0 0 00 1 0 01 0 1 0M15=0 0 0 00 0 0 00 0 1 00 1 0 1M16=0 0 0 00 0 0 10 0 1 10 1 1 1Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 7 / 19Are the Inputs Linearly Independent?Is every target array reachable from any starting array?Are the input moves independent of each other?α1M1+ α2M2+ α3M3+ α4M4+ α5M5+ α6M6+ α7M7+ α8M8+ α9M9+α10M10+ α11M11+ α12M12+ α13M13+ α14M14+ α15M15+ α16M16= 0Is the only solution the trival solution?α0= α1= α2= α3= α4= α5= α6= α7= α8= α9= α10= α11= α12= α13= α14= α15= α16= 0Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 8 / 19To do this we expand our Mimatrices and multiply them with our α0s which givesα1α1α10α1α10 0α10 0 00 0 0 0+α20 α200 α20 00 0 0 00 0 0 0+0 α30 α30 0 α300 0 0 00 0 0 0+0 α4α4α40 0 α4α40 0 0 α40 0 0 0+α50 0 00 α50 0α50 0 00 0 0 0+0 α60 0α6α6α600 α60 00 0 0 0+· · · +0 0 0 00 0 0 α160 0 α16α160 α16α16α16=0 0 0 00 0 0 00 0 0 00 0 0 0Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 9 / 19Each cell indiviually must equal zero, form the zero matrixα1+ α2+ α5= 0α1+ α3+ α4+ α6= 0α1+ α2+ α4+ α7= 0α3+ α4+ α8= 0α1+ α6+ α9+ α13= 0α2+ α5+ α6+ α7+ α10= 0α3+ α4+ α6+ α7+ α8+ α11= 0α4+ α7+ α12+ α16= 0α1+ α5+ α10+ α13= 0α6+ α9+ α10+ α11+ α13+ α14= 0α7+ α10+ α11+ α12+ α15+ α16= 0α4+ α8+ α11+ α16= 0α9+ α13+ α14= 0α10+ α13+ α15+ α16= 0α11+ α13+ α14+ α16= 0α12+ α15+ α16= 0Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 10 / 19The previous sixteen equations form this matrix here.Rα = 0 :1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 01 0 1 1 0 1 0 0 0 0 0 0 0 0 0 01 1 0 1 0 0 1 0 0 0 0 0 0 0 0 00 0 1 1 0 0 0 1 0 0 0 0 0 0 0 01 0 0 0 0 1 0 0 1 0 0 0 1 0 0 01 1 0 0 1 1 1 0 0 1 0 0 0 0 0 00 0 1 1 0 1 1 1 0 0 1 0 0 0 0 00 0 0 1 0 0 1 0 0 0 0 1 0 0 0 11 0 0 0 1 0 0 0 0 1 0 0 1 0 0 00 0 0 0 0 1 0 0 1 1 1 0 1 1 0 00 0 0 0 0 0 1 0 0 1 1 1 0 0 1 10 0 0 1 0 0 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 0 0 1 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 0 0 1 0 1 10 0 0 0 0 0 0 0 0 0 1 0 1 1 0 10 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1α1α2α3α4α5α6α7α8α9α10α11α12α13α14α15α16=0000000000000000Loran Briggs and Daniel McBride (CR) The Mathematics of Quatrainment December 17, 2010 11 / 19In reduced row echelon form, matrix R yeilds:1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 1 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 0 0 0 0 00 0 0 …

View Full Document