# Joey Reichert
# 640:640 Spring 2013
# February 4, 2013
# hw4.txt
# I give permission to post
Help:=proc() : print(`SGwyt(i,j)`): end:
# Problem #1
# (For novices only) Read and do all the examples,
# plus make up similar ones, in the pages 91 to the very end
# of Frank Garvan's awesome Maple booklet ( part 1, part 2)
# This time I decided to do all of the examples in the Maple window,
# so this problem is located at hw4.mw
# Problem #2
# [for everyone, purely human problem]
# 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
# (a) f(2m,2n)=2f(m,n),
# (b) f(2m+1,2n)=2f(m,n)+1,
# (c) f(2m,2n+1)=2f(m,n)+1,
# (d) 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)
# Proof:
# Base Case:
# (a) f(2*0,2*0) = f(0,0) = 0 = 2*f(0,0)
# (b) f(2*0+1,2*0) = f(1,0) = 1 = 2*f(0,0) + 1
# (c) f(2*0,2*0+1) = f(0,1) = 1 = 2*f(0,0) + 1
# (d) f(2*0+1,2*0+1) = f(1,1) = 0 = 2*f(0,0)
# Inductive Step:
# Assume (a-d) are true for some m,n.
# Proceeding should not be terribly difficult,
# but every attempt I have made (trying the
# case of m+1,n, for instance) has led to
# a term of the form f(m+2,n), which will not be
# applicable via the recurrence. It is likely that the
# way to resolve this is to then go to the definition
# of f(m,n), but I cannot see a straightforward way
# to do so. In any case, all four proofs should be similar.
# Problem #3:
# [for everyone, purely human problem] Prove that a position
# is Losing iff its Sprague-Grundy function is 0
# Proof:
# SG=0 => losing position
# Pick any vertex i in a graph s.t. SG(i) = 0. If i is a sink,
# then this is a losing position, so we are done.
# If i is not a sink, then pick any edge, and that vertex j will
# have SG(j) != 0. Since j is not a sink, we can take some edge to
# a vertex k that has SG(k) = 0. If k is a sink, then this is a
# losing position. If not, we can repeat this process until reaching
# a sink, and thus k was a losing position, which ultimately makes i
# a losing position.
# Losing position => SG=0
# Suppose i is a losing position but SG(i) != 0. Then i must have
# an edge to a vertex j s.t. SG(j) = 0, so j must be a losing
# position from before. As i has an edge to this losing position,
# i must be a winning position, which is a contradiction
# since i cannot be both a losing and winning position at
# the same time.
Maple Booklet
# Problem #4
# [For everyone]
# Write a program SGwyt(i,j) that 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) local k: option remember:
# print("here");
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))
});
end:
### OLD STUFF ###
# (For everyone) 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
Wyt:=proc(a,b) local i: option remember:
1-mul(Wyt(a-i,b),i=1..a)*
mul(Wyt(a,b-i),i=1..b)*
mul(Wyt(a-i,b-i),i=1..min(a,b)):
end:
#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:
#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:
### END OLD STUFF ###