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