Transcript Simon Says “Play!”: An Examination of Finite Linear Games

Simon Says “Play!”: An Examination
of Finite Linear Games
By Madison Murphy and Alexander
Salter
Math 214 Spring 2008
Finite Linear Games
What is a finite linear game???
A finite linear game is a problem that involves a
situation where a physical system has only a
finite number of states which can be altered
by applying certain processes.
Poole 109
Example: a group of light bulbs
The light bulbs are the physical system with a
finite number of states: on or off. These
states are changed by flipping a switch.
http://www.geocities.com/jaapsch/puzzles/light
s.htm
Playin’ with Numbers!
When working with finite linear games, our
number line is restricted to the number of
states we have.
For example, the light bulbs have only two
states, on and off. So if we want to use
numbers to represent those states, we can
only use two of them, say 0 for ‘off’ and 1 for
‘on’.
Z2
0
and
Z3
1
0
2
Poole 110
1
Example 1
Five lights in a row!
Parameters: Switches A-E control the lights.
Turning on any light also turns on all adjacent
lights.
A
B
C
Poole 109
D
E
Starting with all lights off, find a way to turn
lights 1, 3, and 5 on.
How??? Use command vectors! Assign vectors
a-e to represent the resulting state when
switches A-E are hit; ex: a=[1,1,0,0,0],
b=[1,1,1,0,0]...e=[0,0,0,1,1]
If constants v-z represent the number of times
each switch is hit, then we have the linear
equation va+wb+xc+yd+ze=s, where s is our
desired outcome (lights 1, 3, and 5 on, 2, and
4 off, so s=[1,0,1,0,1])
Poole 110
Use an augmented coefficent matrix to
determine if the desired outcome is possible.
The matrix becomes:
11000|1
11100|0
01110|1
00111|0
00011|1
Poole 110
By row reducing the augmented coefficient
matrix, we find that X5 is a free variable.
10001|0
X1 = X5
01001|1
X2 = 1 + X5
00100|1
X3 = 1
00011|1
X4= 1 + X5
00000|0
Remember, since we are in Z2,we only have two
numbers in our domain: 0 and 1! So there are
exactly two solutions (where X5 = 0 and
X5= 1).
Poole 111
Since
X1 = X5
X2 = 1 + X5
X3 = 1
X4= 1 + X5 and X5 = 0 and X5 = 1
Substituting in gives the solution vectors
[0,1,1,1,0] and [1,2,1,2,1] (however since we
are in Z2, “2” becomes “0” so the solution
vector is [1,0,1,0,1]). In other words, hitting
switches B, C, and D, or switches A, C, and E
(in any order) gives the desired outcome!
Poole 111
Let’s check our answer
By multiplying our matrix by the solution vectors
we reach our target configuration of
[1, 0, 1, 0, 1].
11000
0
11100
1 = [1, 2, 3, 2, 1] convert to Z2!
0 1 1 1 0 * 1 so the vector =[ 1, 0, 1, 0, 1]
00111
1
This checks out for the 2nd
00011
0
solution vector as well.
Poole 110
Simon Says “Play!”
Our game: We have five “math dolls” which can
be ordered to jog in place or jump in place
(starting at rest). So we have three states
represented by numbers “0” for rest, “1” for
jogging, and “2” for jumping. Dolls must
progress through the states in order, and the
same rules from before apply.
IMPORTANT: Since we have three states, we’re
in Z3 now!
Poole 110
Math Dolls!
1
2
3
4
5
What will the command vectors be for our math dolls?
Answer: the same vectors from the previous problem. Can you explain
why?
Example: Ordering math doll 1 to start jogging would result in the vector
[1,1,0,0,0]. After this, ordering doll 3 to start jogging would result in the
vector [1,2,1,1,0]. Remember, we’re in Z3 now!
Poole 110
If we want a desired outcome for our math dolls,
represented by the vector [t1, t2, t3, t4, t5], our
augmented coefficient matrix becomes:
1 1 0 0 0 | t1
1 1 1 0 0 | t2
0 1 1 1 0 | t3
0 0 1 1 1 | t4
0 0 0 1 1 | t5
Row reducing this matrix will reveal if the desired
outcome is possible and if so what orders need to
be given to create this outcome.
Poole 110
Jogging Math Dolls
Let’s say we want all the math dolls to be jogging.
Then our desired outcome will be [1,1,1,1,1].
Plug this vector into our augmented coefficient
matrix to find our solution vectors.
We get three: [1,0,0,1,0], [0,1,0,0,1], and
[-1,2,0,-1,2].
Hey…you can’t hit a switch ‘negative one’ times!
CONVERT TO Z3: [-1,2,0,-1,2] becomes [2,2,0,2,2]
because of the repeating nature of the numbers!
Poole 110
So what do these solution vectors mean? Take
[1,0,0,1,0]. This means that if we tell math
dolls 1 and 4 to jog (regardless of order), we’ll
get our desired outcome of all the dolls
jogging represented by [1,1,1,1,1].
1
2
3
Poole 110
4
5
Not every desired outcome is possible with our game. We tried to find a
way to have math dolls 1 through 4 jumping while math doll 5 jogged,
represented by the vector:
[2, 2, 2, 2, 1].
Our row reduced augmented coefficient matrix is:
1 1 0 0 0| 0
0 0 1 0 0| 0
0 0 0 1 0| 0
0 0 0 0 1| 0
0 0 0 0 0|-1
Since we have a row of zeros equaling -1 this desired outcome is
unattainable.
Poole 110
Thanks for listening!
Poole 110
Sources
Poole, David. Linear Algebra, A Modern
Introduction (Second Edition). Belmont:
Thompson Higher Education, 2006.
Scherhuis, Jaap. "Lights Out." Jaap's Puzzle
Page. 28 March. 2008
http://www.geocities.com/jaapsch/puzzles/lig
hts.htm
Poole 110