#Nathan Fox #Homework 4 #I give permission for this file to be posted online, #though I do NOT give permission to post hw4.pdf #Help procedure Help:=proc() : print(` mex(S) , SG(G,i) , RandGame(n,k) `): print(` SGwyt(i,j) , WinningMove(G,i) `): end: ##Auxiliary Procedures #mex(S): inputs a set of nonnegative 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: #SG(G,i): inputs a digraph (representing a cycle-less #combinatorial game with positions 1, 2, ..., nops(G) #and G[i] is the subset of {1, ..., nops(G)} reachable #in one legal move #outputs the value of the Sprague-Grundy function #at vertex i SG:=proc(G,i) local m: option remember: mex({seq(SG(G,m), m in G[i])}): end: #RandGame(n,k): inputs positive integers n and k #and outputs a random directed graph that has the #property that out of vertex i all the labels are #less than i, and there are (usually) k outgoing #edges RandGame:=proc(n,k) local L,tomas,i: L:=[{}]: for i from 2 to n do tomas:={seq(rand(1..i-1)(),j=1..k)}: L:=[op(L), tomas]: od: L: end: ##Problem 2 #See file hw4.pdf for solution to this problem. ##Problem 3 #See file hw4.pdf for solution to this problem. ##Problem 4 #SGwyt(i,j): 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: 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: ##Problem 6 #WinningMove(G,i): 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 SG(G,j)=0 then return j: fi: od: return FAIL: end: