# Matthew Russell
# Experimental Math
# Homework 4
# I give permission to post this
#####################################################################################
# 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)
# We proceed by induction.
#
#
#
#
#
#####################################################################################
# Prove that a position is losing iff its Sprague-Grundy function is 0.
# We proceed by induction on the size of the induced digraph
# (the current position, along with all positions reachable from it).
#
# If the size of the induced digraph is 1, then no positions are reachable from it.
# This is clearly a losing position, and it clearly has Sprague-Grundy value 0.
#
# Now, suppose that the claim holds for all smaller induced digraphs.
#
# Suppose that we are in a losing position.
# That means that every adjacent vertex is a winning position.
# By the inductive hypothesis, these all have positive Sprague-Grundy values.
# Hence, the mex of all of these is 0,
# so this losing position has Sprague-Grundy value 0.
#
# Suppose we are in a winning position.
# That means that there is an adjacent vertex which is losing.
# By the inductive hypothesis, it has Sprague-Grundy value 0.
# Hence, the mex of the neighbors is positive,
# so this winning position has positive Sprague-Grundy value.
#####################################################################################
# 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)
option remember:
return mex({seq(SGwyt(i-a,j),a=1..i)} union {seq(SGwyt(i,j-b),b=1..j)} union {seq(SGwyt(i-c,j-c),c=1..min(i,j))}):
end:
#####################################################################################
# Write a program,
# WinningMove(G,i),
# that inputs a game given as a digraph G,
# and a position i (between 1 and nops(G)),
# and outputs a winning move (a member of G[i]) if one exists,
# or FAIL if i is a losing (alias P) position.
WinningMove:=proc(G,i) local j:
for j in G[i] do
if W(G,j)=0 then
return j:
fi:
od:
return FAIL:
end: