# You can post my homework online. Help := proc(`SGWyt(i, j) mex(S) `) end: # problem 3: # Let's pick an arbitrary vertex i in a game such that SG(i) = 0. # We will attempt to prove that i is a losing position. # # If i is a sink, it is already a losing position. We are done. # If i is not a sink, pick any edge from i to a node j. SG(j) cannot equal 0, because of the definiti on of mex. # Now j cannot be a sink (because SG(j) > 0), and it must have an edge to a node k such that SG(k) = 0. # # I assert that k must be a losing position. If k is a sink, this is clearly true. If it is not a sin k, we repeat the above argument for i using k, and continue the argument until we arrive at a sink. # # Since the graph is acyclic, we must eventually hit a k that is a losing position which proves that i is a losing position (since j is winning.) # Now we consider an arbitrary vertex i that is a losing position and SG(i) > 0. # # By definition of SG, i must have an edge to a vertex j such that SG(j) = 0. j must be a losing posi tion, by our previous proof. # Hence, i cannot be a losing position since it has a direct edge to a losing position. SGWyt := proc(i,j) local x, y, z: option remember: if i <= 0 and j <= 0 then return 0: fi: return mex({seq(SGWyt(i - x, j), x in 1..i), seq(SGWyt(i, j - y), y in 1..j), seq(SGWyt(i - z, j - z), z in 1..min(i, j))}) end: # Minimal excluded set # mex(S): inputs a set of nonnegative integers. # 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: return i: end: # SG(G, i) - inputs a directed graph representing a cycle-less combinatorial game # with positions 1,2...nops(G), and a vertex i. # outputs: 0-nops(G). The value of the sprague grundy function at vertex i. SG := proc(G, i) local x: option remember: return mex({seq(SG(G, x), x in G[i])}): end: WinningMove := proc(G, i) local m: option remember: if G[i] = {} or SG(G, i) = 0 then return FAIL: fi: for m in G[i] do if SG(G, m) = 0 then return m: fi: od: return FAIL: end: