# Joey Reichert # 640:640 Spring 2013 # February 4, 2013 # hw4.txt # I give permission to post Help:=proc() : print(`SGwyt(i,j)`): end: # Problem #1 # (For novices only) Read and do all the examples, # plus make up similar ones, in the pages 91 to the very end # of Frank Garvan's awesome Maple booklet ( part 1, part 2) # This time I decided to do all of the examples in the Maple window, # so this problem is located at hw4.mw # Problem #2 # [for everyone, purely human problem] # 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 # (a) f(2m,2n)=2f(m,n), # (b) f(2m+1,2n)=2f(m,n)+1, # (c) f(2m,2n+1)=2f(m,n)+1, # (d) 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) # Proof: # Base Case: # (a) f(2*0,2*0) = f(0,0) = 0 = 2*f(0,0) # (b) f(2*0+1,2*0) = f(1,0) = 1 = 2*f(0,0) + 1 # (c) f(2*0,2*0+1) = f(0,1) = 1 = 2*f(0,0) + 1 # (d) f(2*0+1,2*0+1) = f(1,1) = 0 = 2*f(0,0) # Inductive Step: # Assume (a-d) are true for some m,n. # Proceeding should not be terribly difficult, # but every attempt I have made (trying the # case of m+1,n, for instance) has led to # a term of the form f(m+2,n), which will not be # applicable via the recurrence. It is likely that the # way to resolve this is to then go to the definition # of f(m,n), but I cannot see a straightforward way # to do so. In any case, all four proofs should be similar. # Problem #3: # [for everyone, purely human problem] Prove that a position # is Losing iff its Sprague-Grundy function is 0 # Proof: # SG=0 => losing position # Pick any vertex i in a graph s.t. SG(i) = 0. If i is a sink, # then this is a losing position, so we are done. # If i is not a sink, then pick any edge, and that vertex j will # have SG(j) != 0. Since j is not a sink, we can take some edge to # a vertex k that has SG(k) = 0. If k is a sink, then this is a # losing position. If not, we can repeat this process until reaching # a sink, and thus k was a losing position, which ultimately makes i # a losing position. # Losing position => SG=0 # Suppose i is a losing position but SG(i) != 0. Then i must have # an edge to a vertex j s.t. SG(j) = 0, so j must be a losing # position from before. As i has an edge to this losing position, # i must be a winning position, which is a contradiction # since i cannot be both a losing and winning position at # the same time. Maple Booklet # Problem #4 # [For everyone] # 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) local k: option remember: # print("here"); 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)) }); end: ### OLD STUFF ### # (For everyone) The Wythoff game is like 2-pile Nim # with the extra move that one can remove the SAME # number of pennies from BOTH piles. Write a procedure # Wyt(a,b) that inputs 0(1) according to whether [a,b] # is a losing (winning) position Wyt:=proc(a,b) local i: option remember: 1-mul(Wyt(a-i,b),i=1..a)* mul(Wyt(a,b-i),i=1..b)* mul(Wyt(a-i,b-i),i=1..min(a,b)): end: #mex(S): inputs a set of non-neg. integers and outputs #the minimum of the set {0,1,2,3,...}\S mex:=proc(S) local i: for i from 0 to nops(S) while i in S do od: i: end: #SG2N(i,j): The S-G function of positon [i,j] in 2-pile Nim SG2N:=proc(i,j) local k: option remember: mex({ seq(SG2N(i-k,j),k=1..i), seq(SG2N(i,j-k),k=1..j)}): end: ### END OLD STUFF ###