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