# 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: