Periodicity (focus on subtraction games)

What is periodicity?

The tendency of a function to repeat itself in a regular pattern at established intervals. To be periodic there must be a consistent repetition of values over the entire domain of the function

Periodicity of Subtraction Games 

I will focus on periodicity of nim-sequences of subtraction games, denoted SUBTRACTION(S).  In order to be a subtraction game the following conditions must be satisfied:

•  two-player game involving a pile of chips.

• a finite set S of positive integers called the subtraction set. Subtraction sets S = s1, s2, ..., sk will be ordered s1 < s2 < < sk.

• The two players move alternately, subtracting some s chips such that s ∈ S.

• The game ends when a position is reached from which no moves are possible for the player whose turn it is to move. The last player to move wins

finite subtraction game denoted SUBTRACTION(­­­­a1, a2, . . . , ak), if S = {a1, a2, . . . , ak} is finite

all-but subtraction game denoted ALLBUT({a1, a2, . . . , ak}, if S = {1,2,3,…} | {a1, a2, . . . , ak} consists of all the positive integers except a finite set

subtraction game is periodic as we will prove later and ALLBUT() is another name for NIM and is arithmetic periodic with saltus 1

Types of periodicity:

1)   periodic – if there is some l >= 0 and p > 0 so that G(n +p) = G(n) for all n>=1

2)   arithmetic periodic – if there is l >=0 , p > 0, and s > 0 so that G(n +p) =

G(n) + s for all n >= l

3)   sapp regular (split arithmetic periodic/periodic)- if there exist integers

            l >= 0, s >0, p > 0, and a set S ⊆ {0, 1, 2, . . . , p − 1} such that for all n ≥ l,

            G(n + p)  = ( G(n) if (n mod p) ∈ S,

                                    G(n) + s if (n mod p) not in S.

 purely periodic, purely arithmetic periodic, or purely Sapp regular just infers that there is no pre-period along with previous stated conditions

Subsequence G(0), G(1),..G((l-1) is called pre-period and its elements are the exceptional values l  is pre-period length, p is period length, and s is saltus

Practice:

Match each sequence on the left one-to-one to a category on the right:

1231451671 . . . periodic

1123123123 . . . purely periodic

1122334455 . . . sapp regular

0123252729 . . . arithmetic periodic

0120120120 . . . purely sapp regular

1112233445 . . . purely arithmetic periodic

In each case, identify the period and pre-period

Finding the pre-period and period of subtraction games:

Ex.1: S = {2,4,7}

The Grundy Sequence starts G = 01122003102102102102, this means G(1)=0, G(2) = 1, G(3)=1, and G(4)=2 etc.

From the pattern forming we can see G = 0112203$\overline{102}$so the pre-period is 0112203 and it has a period of 3, 102

Ex.2: S = {1,9,10} G =$\overline{101010101232323232}$,} this example has no pre-period and a period of 19, it can also be written as G = $\overline{(10)^41(23)^420}$

Theorem:  The nim-sequences of finite subtraction games are periodic.

Proof: Consider the finite subtraction game subtraction(a1, a2, . . . , ak) and its nim-sequence. From any position there are at most k legal moves. So, using Observation 7.22, G(n) ≤ k for all n. Define a = max{ai}. Since G(n) ≤ k for all n there are only finitely many possible blocks of a consecutive values that can arise in the nim-sequence. So we can find positive integers q and r with a ≤ q < r such that the a values in the nim-sequence immediately preceding q are the same as those immediately preceding r. Then G(q) = G(r) since G(q) = mex{G(q − ai) | 1 ≤ i ≤ k} = mex{G(r − ai) | 1 ≤ i ≤ k} = G(r). In fact, for such q and r and all t ≥ 0, G(q + t) = G(r + t). This is easily shown by induction — we have just seen the base case, and the inductive step is really just an instance of the base case translated t steps forwards. Now set l = q and p = r − q and we see that the above says that for all n ≥ l, G(n + p) = G(n); that is, that the nim-sequence is periodic.

Corollary: Let G = subtraction(a1, a2, . . . , ak) and let a = max{ai}. If l and p are positive integers such that G(n) = G(n + p) for l ≤ n < l + a, then the nim-sequence for G is periodic with period length p and pre-period length l.

Why it’s important :

Periodicity is important because by representing a game as a periodic nim sequence we can compute the value of any single heap efficiently. The value of any sums of heaps and therefore a perfect winning strategy can be computed using nim-addition rule. Once the game is known to be periodic it is solved

Sources:

https://books.google.com/books?id=VUVrAAAAQBAJ&pg=PA187&lpg=PA187&dq=periodicity+of+subtraction+games&source=bl&ots=c8oH_d0Oze&sig=HSncfV6ayK5IVDIpDxvlhMt6Dys&hl=en&sa=X&ved=0CEIQ6AEwBWoVChMIndDet5jlxwIVSx0-Ch3aRwTy#v=onepage&q=periodicity%20of%20subtraction%20games&f=false

https://subtractiongames.files.wordpress.com/2012/02/subgames2.pdf

http://myslu.stlawu.edu/~nkomarov/450/LIP-subgames.pdf