#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 4
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

Help := proc(): print(`mex(S), SGWyt(i,j), WinningPosition(G, i), WinningMove(G, i)`): end:

#############
# Problem 2 #
#############

# Definition: For any set S of nonnegative integers, let T(S) = 2S
# union (2S+1).

# Lemma:
# Let S be a set of nonnegative integers. Then mex(T(S)) = 2*mex(S).

# Proof: Let k = mex(S). Then S = {0, 1, ..., k-1} union L, where L is
# a set of elements greater than K. Then
# T(S) = {0, 1, ..., 2k-1} union T(L). Since T(L) does not contain 2k,
# mex(T(S)) = 2k = 2*mex(S), as claimed.

# Proof of Main Theorem:

# Induction on m+n. The base case is m+n = 0 and is trivial.

# Consider f(2m, 2n). From this position we can move to positions with
# various Sprague-Grundy values, which we group into 4 sets:

# A0 = {f(0, 2n), f(2, 2n), ..., f(2m-2, 2n)}
# A1 = {f(1, 2n), f(3, 2n), ..., f(2m-1, 2n)}
# B0 = {f(2m, 0), f(2m, 2), ..., f(2m, 2n-2)}
# B1 = {f(2m, 1), f(2m, 3), ..., f(2m, 2n-1]}

# Observe that by induction:
# A0 = {2f(0,n), ..., 2f(m-1, n)}
# A1 = {2f(0,n)+1, ..., 2f(m-1, n)+1}
# B0 = {2f(m,0), ..., 2f(m, n-1)}
# B1 = {2f(m,0)+1, ..., 2f(m, n-1)+1}

# Now, if S is the set of options of f(m,n), then A0 union A1 union B0
# union B1 = T(S). So, by Lemma 1,
# mex(A0 union A1 union B0 union B1) = 2*mex(S) = 2*f(m,n), as desired.

# The other cases are similar.

#############
# Problem 3 #
#############

# We previously (HW 0) demonstrated that if positions are divided into two
# sets P and N such tha the following properties hold:

# 1. Any position with all options in N is in P.
# 2. Any position with an option in P is in N.

# then all P-positions are losing and all N-positions are winning.

# Let P be the set of all positions with Sprague-Grundy value 0. Let N
# be the set of all positions with Sprague-Grundy value not equal to
# 0. Then N and P satisfy the above properties, since mex(S) = 0 if
# and only if 0 is not in S. So N is the set of winning positions and
# P is the set of losing positions, as claimed.

#############
# Problem 4 #
#############

mex := proc(S) local i:
    for i from 0 while i in S do od:
    return i:
end:

SGWyt := proc(i,j) local k: option remember:
    if i = 0 and j = 0 then:
        return 0:
    else:
        return 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))}):
    fi:
end:

#############
# Problem 6 #
#############

WinningPosition := proc(G, i) local j: option remember:
    if G[i] = {} then:
        return 0:
    else:
        return 1-mul(WinningPosition(G, j), j in G[i]):
    fi:
end:

WinningMove := proc(G, i) local k:
    for k in G[i] do:
        if WinningPosition(G,k) = 0 then:
            return k
        fi:
    od:
    return FAIL:
end: