# Matthew Russell # Experimental Math # Homework 4 # I give permission to post this ##################################################################################### # Starting from the recursive definition # of the Sprague-Grundy function # for two-pile Nim (let's call it f(m,n)) # f(m,n)=mex({f(m-1,n),f(m-2,n), ...,f(0,m),f(m,n-1),f(m,n-2),...,f(m,0)}), # prove, by induction on m and n, the recurrences # f(2m,2n)=2f(m,n), # f(2m+1,2n)=2f(m,n)+1, # f(2m,2n+1)=2f(m,n)+1, # f(2m+1,2n+1)=2f(m,n) # (that are equivalent to the fact that f(m,n) is the sum-without-carry of m and n in binary) # We proceed by induction. # # # # # ##################################################################################### # Prove that a position is losing iff its Sprague-Grundy function is 0. # We proceed by induction on the size of the induced digraph # (the current position, along with all positions reachable from it). # # If the size of the induced digraph is 1, then no positions are reachable from it. # This is clearly a losing position, and it clearly has Sprague-Grundy value 0. # # Now, suppose that the claim holds for all smaller induced digraphs. # # Suppose that we are in a losing position. # That means that every adjacent vertex is a winning position. # By the inductive hypothesis, these all have positive Sprague-Grundy values. # Hence, the mex of all of these is 0, # so this losing position has Sprague-Grundy value 0. # # Suppose we are in a winning position. # That means that there is an adjacent vertex which is losing. # By the inductive hypothesis, it has Sprague-Grundy value 0. # Hence, the mex of the neighbors is positive, # so this winning position has positive Sprague-Grundy value. ##################################################################################### # Write a program # SGwyt(i,j) # that inputs two non-negative integers i and j # and outputs the Sprague-Grundy function # of position (i,j) in Wythoff's game, # where a legal move consists of # taking a positive number of pennies from either pile, # or the same number from both. SGwyt:=proc(i,j) option remember: return mex({seq(SGwyt(i-a,j),a=1..i)} union {seq(SGwyt(i,j-b),b=1..j)} union {seq(SGwyt(i-c,j-c),c=1..min(i,j))}): end: ##################################################################################### # Write a program, # WinningMove(G,i), # that inputs a game given as a digraph G, # and a position i (between 1 and nops(G)), # and outputs a winning move (a member of G[i]) if one exists, # or FAIL if i is a losing (alias P) position. WinningMove:=proc(G,i) local j: for j in G[i] do if W(G,j)=0 then return j: fi: od: return FAIL: end: