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