Transcript The 4-Number Game

The 4-Number
Game
Dave Brown
Ithaca College
October 21, 2015
faculty.ithaca.edu/dabrown/fournumber
The Game
4
9
2
4
0
8
5
2
0
2
2
0
0
2
2
2
1
4
7
6
The Game
O This game reached all zeroes!
O Do all games end?
O That is, do they all stabilize at all zeroes?
O If a game ends, we count the number of
steps to reach all zeroes.
O This is how we characterize games that end.
O Activity 1
The Game
O What effect do large numbers have on the
game?
O Did you find any interesting examples?
Patterns?
O What is the longest game you found using
integers from 0 to 9?
O Can you predict the game’s length in some
cases?
Symmetry in the Game
O Is there a rigid motion that will transform the
game on the left to the game on the right?
9
5
9
1
7
1
7
5
Symmetry in the Game
O Activity 2
O What role does symmetry play?
O How many symmetries of the square are
O
O
O
O
there?
Up to symmetry, how many truly different
games are there using 9, 7, 5, 1?
Possible games for 9, 4, 1, 0?
Still hard to characterize all games.
Can we build really long games?
Long Games
O Can we build some arbitrarily long games?
O Take an aside to division, GCD, and
Fibonacci numbers.
O What is the Division Algorithm?
O Use the Division Algorithm to divide 32 by
18.
O 32 = 1*18 + 14
dividend
remainder
divisor
quotient
Long Games
O What is the greatest common divisor of 32
and 18?
O How do we compute GCD?
O Is there a systematic way to compute GCD?
O Yes! Euclidean Algorithm.
Euclidean Algorithm
O Repeated use of Division Algorithm
O Find GCD(32,18)
O 32 = 1*18 + 14
O 18 = 1*14 + 4
O 14 = 3*4 + 2
O 4 = 2*2 + 0
O GCD(32,18) is last non-zero remainder!
O Try on your own: Find GCD(15808, 456)
Euclidean Algorithm
O Find GCD(15808, 456)
O 15808 = 34*456 + 304
O 456 = 1*304 + 152
O 304 = 2*152 + 0
O GCD(15808, 456) =152
O Euclidean Algorithm is fast!
O Can we slow it down?
O Or, equivalently, can we make the number
steps grow longer?
Slowing Euclid
O Compute the following, noting the number of
steps for the Euclidean Algorithm
O GCD(21, 13)
O GCD(21, 13) = 1, # of steps = 6
O GCD(34, 21)
O GCD(34, 21) = 1, # of steps = 7
O GCD(55, 34)
O GCD(55, 34) = 1, # of steps = 8
Slowing Euclid
O What do we notice?
O Fibonacci Numbers
O Consecutive Fibonacci numbers are worst-
case scenario for Euclidean Algorithm.
O And, we see that consecutive Fibonacci
numbers are relatively prime.
O Let’s look again!
Slowing Euclid
O 1=GCD(21, 13)=GCD(F8, F7)
O # of steps = 6
O 1=GCD(34, 21)=GCD(F9, F8)
O # of steps = 7
O 1=GCD(55, 34)=GCD(F10, F9)
O # of steps = 8
O Guess: GCD(F22, F21) and # of steps
O GCD(F22, F21) =1 and # of steps = 20
O GCD(Fn, Fn-1) = 1 and # of steps = n-2
Going Way Off Track
But for a Little Fun
O Compute GCD(F9, F6)=GCD(34, 8)
O GCD(34, 8)=2
O Compute GCD(F10, F8)=GCD(55, 21)
O GCD(55, 21)=1
O Compute GCD(F12, F8)=GCD(144, 21)
O GCD(144, 21)=3
O Compute GCD(F18, F12)=GCD(2584, 144)
O GCD(2584, 144)=8
Going Way Off Track
But for a Little Fun
O GCD(F9,F6)=GCD(34,8)= 2 = F3
O GCD(F10,F8)=GCD(55,21)= 1 =F2
O GCD(F12,F8)=GCD(144,21)= 3 =F4
O GCD(F18,F12)=GCD(2584,144) = 8 = F6
O GCD(Fm,Fn) = FGCD(m,n)
O Now, let’s get back to the show!
Long Games
O Recall, there are only 3 types of games
O In standard position, we can only have
O Type 1: a ≥ b ≥ c ≥ d
O Type 2: a ≥ c ≥ b ≥ d
O Type 3: a ≥ b ≥ d ≥ c
O Type 2 games have length ≤ 4 (why?)
O Type 3 games have length ≤ 6
O As expected, Type 1 is our only hope!
Long Games
O Inspired by Fibonacci creating long E.A.
games, let’s try something similar
O The E.A. used triples of Fibonacci numbers
in each step
O The Four-Number Game uses quadruples of
numbers in each step
O Fibonacci does not work, but his relative
Tribonacci might!
Long Games
O Tribonacci Numbers
O t0=0, t1=1, t2=1, and
O For n>2, tn=tn-1 + tn-2 +tn-3
O Activity 3
O Can you produce a game of length
3,000,000?
O Does this mean that there are game that do
not end?
Long Games
O We can now build games of any length that
are multiples of 3
O Can we build games of other lengths?
O Let’s be systematic– Activity 4
O Multiplying and shifting games does not
change the length
Long Games
O Focus on games in which a>b>c>d
O Start with the game (13, 7, 4, 2) which has
O
O
O
O
length 9.
Can you find a game (a, b, c, d) so that the
its first output is (13, 7, 4, 2)?
Try it! (Hint: a-d=13, a-b=7, etc)
(13, 6, 2, 0) works
Notice that 13 = 7 + 4 + 2 and that (13, 7,
4, 2) is strictly decreasing
Long Games
O Quadruples in which the first number is the
O
O
O
O
sum of the remaining numbers is called
additive.
Any strictly decreasing additive game can be
extended back one level to make a new
game that has length 1 longer.
(13, 7, 4, 2) has length 9
(13, 6, 2, 0) => (13, 7, 4, 2) has length 10
(13, 6, 2, 0) is strictly decreasing but not
additive.
Long Games
O (13, 6, 2, 0) can be turned into an additive
O
O
O
O
game with the same length!
Compute s=a-b-c-d= 13-6-2-0=5
Then, a’=2a+s, b’=2b+s, c’=2c+s, d’=2d+s
So, we get a’=31, b’=17, c’=9, d’=5
See if you can build games of length 11, 12,
13 off of this!
Loooooong Games
O So, can we build games that are infinitely
O
O
O
O
long?
Not if we use integers!
But, even irrational numbers can be
deceiving.
Consider the (π, ℮, √2, 0)-game
Has length 6.
Looooong Games
O Linear Algebra leads us to an infinite length
O
O
O
O
O
O
game
View the game steps as a matrix
D(a,b,c,d) = (|a-d|,|a-b|,|b-c|,|c-d|)
So, view this as an operation in R4.
But, this is not linear. Can’t use linear
algebra yet.
However, if a>b>c>d, then
D(a,b,c,d) = (a-d, a-b, b-c , c-d) is linear!
Looooong Games
O D(a,b,c,d) = (a-d, a-b, b-c , c-d) is
represented by a matrix, M:
Looooong Games
O Now, this is the eigenvalue problem!
O M has a real eigenvalue λ (between 0 and 1)
O If v=(a,b,c,d) is an eigenvector for M, then
O D(v)= λ*v≠(0,0,0,0) and
O For all n, Dn(v)= λn*v≠(0,0,0,0)
O So, the game never ends!
Looooong Games
O To find λ, we find the roots of the characteristic
polynomial of the matrix M:
O This has two complex roots, a root at x=0, and
Looooong Games
O v=((1+λ)3, (1+λ)2, (1+λ), 1) is a game of
O
O
O
O
infinite length
So, there are games of infinite length
But not easy to find
Another research question: what is the
probability that a game ends in N steps?
Or, investigate 3-number games, 5-number
games, etc