#!/usr/local/bin/maple # -*- maplev -*- # Nathaniel Shar # HW 4 # Experimental Mathematics # It is okay to link to this assignment on the course webpage. Help := proc(): print(`mex(S), SGWyt(i,j), WinningPosition(G, i), WinningMove(G, i)`): end: ############# # Problem 2 # ############# # Definition: For any set S of nonnegative integers, let T(S) = 2S # union (2S+1). # Lemma: # Let S be a set of nonnegative integers. Then mex(T(S)) = 2*mex(S). # Proof: Let k = mex(S). Then S = {0, 1, ..., k-1} union L, where L is # a set of elements greater than K. Then # T(S) = {0, 1, ..., 2k-1} union T(L). Since T(L) does not contain 2k, # mex(T(S)) = 2k = 2*mex(S), as claimed. # Proof of Main Theorem: # Induction on m+n. The base case is m+n = 0 and is trivial. # Consider f(2m, 2n). From this position we can move to positions with # various Sprague-Grundy values, which we group into 4 sets: # A0 = {f(0, 2n), f(2, 2n), ..., f(2m-2, 2n)} # A1 = {f(1, 2n), f(3, 2n), ..., f(2m-1, 2n)} # B0 = {f(2m, 0), f(2m, 2), ..., f(2m, 2n-2)} # B1 = {f(2m, 1), f(2m, 3), ..., f(2m, 2n-1]} # Observe that by induction: # A0 = {2f(0,n), ..., 2f(m-1, n)} # A1 = {2f(0,n)+1, ..., 2f(m-1, n)+1} # B0 = {2f(m,0), ..., 2f(m, n-1)} # B1 = {2f(m,0)+1, ..., 2f(m, n-1)+1} # Now, if S is the set of options of f(m,n), then A0 union A1 union B0 # union B1 = T(S). So, by Lemma 1, # mex(A0 union A1 union B0 union B1) = 2*mex(S) = 2*f(m,n), as desired. # The other cases are similar. ############# # Problem 3 # ############# # We previously (HW 0) demonstrated that if positions are divided into two # sets P and N such tha the following properties hold: # 1. Any position with all options in N is in P. # 2. Any position with an option in P is in N. # then all P-positions are losing and all N-positions are winning. # Let P be the set of all positions with Sprague-Grundy value 0. Let N # be the set of all positions with Sprague-Grundy value not equal to # 0. Then N and P satisfy the above properties, since mex(S) = 0 if # and only if 0 is not in S. So N is the set of winning positions and # P is the set of losing positions, as claimed. ############# # Problem 4 # ############# mex := proc(S) local i: for i from 0 while i in S do od: return i: end: SGWyt := proc(i,j) local k: option remember: if i = 0 and j = 0 then: return 0: else: return mex({seq(SGWyt(i-k,j), k=1..i), seq(SGWyt(i,j-k), k=1..j), seq(SGWyt(i-k, j-k), k=1..min(i,j))}): fi: end: ############# # Problem 6 # ############# WinningPosition := proc(G, i) local j: option remember: if G[i] = {} then: return 0: else: return 1-mul(WinningPosition(G, j), j in G[i]): fi: end: WinningMove := proc(G, i) local k: for k in G[i] do: if WinningPosition(G,k) = 0 then: return k fi: od: return FAIL: end: