# Viraj Pandya, Experimental Mathematics, Spring 2013
# Homework Assignment 4
# I give Dr. Z permission to post this file on his website.
# See hw4.mw for the examples from pages 91-end of Garvan's Maple tutorial.
# Begin Dr. Z's homework problems:
Help:=proc():
print(`SGwyt(i,j)`):
end:
#### Importing Dr. Z's programs mex(S), SG(G,i), SG2N(i,j) from C4.txt
#mex(S): inputs a set of non-neg. integers and 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:
i:
end:
#SG(G,i): inputs a digraph (representing a cycle-less
#combinatorial game with positions 1, 2, ..., nops(G)
#and G[i] is the subset of {1, ..., nops(G)} rechable
#in one legal move
#outputs the value of the Sprague-Grundy function
#at vertex i
SG:=proc(G,i) local m:
option remember:
mex({seq(SG(G,m), m in G[i])}):
end:
#SG2N(i,j): The S-G function of positon [i,j] in 2-pile Nim
SG2N:=proc(i,j) local k:
option remember:
mex({ seq(SG2N(i-k,j),k=1..i), seq(SG2N(i,j-k),k=1..j)}):
end:
#### Importing Nim2(L), Nim(Li), Wyt(a,b) from hw4.txt
#Nim2(Li): inputs a list of length 2 of non-neg.
#integers, representing a Nim-3 position with
#Li[1],Li[2] counters, outputs whether it
#is losing (0) or winning (1)
#A legal move consist of picking ONE of the piles
#and removing any number of pennies (up to the total)
#from that pile
Nim2:=proc(Li) local i:
option remember:
1-mul(Nim2([Li[1]-i,Li[2]]),i=1..Li[1])*
mul(Nim2([Li[1],Li[2]-i]),i=1..Li[2]):
end:
#Nim(Li): L of any length
Nim:=proc(Li) local i,j:
option remember:
1-mul(
mul(
Nim([ op(1..j-1, Li), Li[j]-i, op(j+1..nops(Li),Li) ]),
i=1..Li[j]),
j=1..nops(Li)):
end:
# The Wythoff game is like 2-pile Nim with the extra move that one can remove the SAME
# number of pennies from BOTH piles. Write a procedure Wyt(a,b) that inputs 0(1) according
# to whether [a,b] is a losing (winning) position.
# I used the convention here where if both piles have 0 pennies, it
# is a losing position since nothing can be removed. Else, if both
# piles have the same number of pennies, then it is a winning position
# since you can remove the same number of pennies from both piles leaving
# [0,0] for the next player (a losing position for them). Else, if
# a<>b (not equal), then Nim2([a,b]) should be called.
Wyt:=proc(a,b) option remember:
if [a,b]=[0,0] then
0:
elif a=b then
1:
else
Nim2([a,b]):
fi:
end:
##### PROBLEM 2
#Starting from the recursive definition of the Sprague-Grundy
#function for two-pile Nim (let's call it f(m,n))
#f(m,n)=mex({f(m-1,n),f(m-2,n), ..., f(0,m), f(m,n-1),f(m,n-2), ..., f(m,0)} ),
#prove, by induction on m and n, the recurrences
#f(2m,2n)=2f(m,n) , f(2m+1,2n)=2f(m,n)+1 , f(2m,2n+1)=2f(m,n)+1 , f(2m+1,2n+1)=2f(m,n)
#(that are equivalent to the fact that f(m,n) is the sum-without-carry of m and n in binary)
# Need to think about the fast recurrence implementation further.
##### PROBLEM 3
# Prove that a position is Losing iff its Sprague-Grundy function is 0
# Assume a position is Losing. Then, by definition,
# there are no edges connecting that position to
# another position in that game's directed graph.
# Thus, by construction of the S-G function,
# f(v) = mex({empty}) = 0.
# Conversely, assume the S-G function,
# f(v) = mex({f(w)|vw in E}) = 0.
# Then, the only way mex(S) where S is a set
# can return 0 is if S is the empty set or S
# does not contain 0. If S is the empty set,
# then that means v is a sink for there are no
# outgoing edges from v, and so v is a Losing position.
# Else if S does not contain 0, then there is an
# outgoing edge from v to another vertex w where
# f(w)<>0 (not equal to). But this means that
# the corresponding set T of f(w) (analagous
# to S of f(v)) contains 0, i.e., a player can
# move from w to another vertex x s.t. f(x)=0
# and so x is a Losing position. In this case then,
# v is also a Losing position.
##### PROBLEM 4
# SGwyt(i,j) inputs two non-negative integers i and j
# and outputs the Sprague-Grundy function of
# position (i,j) in Wythoff's game, where a legal move
# consists of taking a positive number of pennies from
# either pile, or the Same number from both.
SGwyt:=proc(i,j) option remember:
if [i,j]=[0,0] then
0:
elif i=j then
SG2N(i,i):
else
SG2N(i,j):
fi:
end: