#Tim Naumovitz
#Homework for Monday, Feb 4
#I give permission to post this

#Problem 2
#If f(m,n) is the Sprague-Grundy function for two-pile Nim, then
#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)
#Proof: Follows from Lemma 1
#Lemma 1: f(m,n)=m+n, where + represents bitwise xor.
#Proof: induction on m,n
#Base Case: f(0,0)=0+0=0
#Induction Step:
#Let S be such that f(m,n)=mex(S).
#Let r=m+n, and let i be the index of the most significant bit of r
#(indexing starts with the least significant bits).  Let s<r, and let j be
#the index of the most significant bit of t=r+s.  Note that since
#s<r, the most significant bit where r and s differ (i.e. index j) must be
#1 in r and 0 in s.  Since the jth bit of r is 1, either m or n has a 1 at
#index j, WLOG m has a 1 at index j.  As such, consider p=t+m. 
#Since m has a 1 at the index (j) of the most significant bit of t, p has
#a 0 at index j. Because the most significant bit where p and m differ is
#1 for m and 0 for p, we have p<m.  By the rules of nim, (p,n) is a
#reachable position from (m,n), and
#p+n=t+m+n=t+r=s.  By the inductive hypothesis,
#f(p,n)=p+n=s, so s is in S.
#
#Furthermore, any valid move must remove some chips from one of the piles,
#WLOG from the 1st pile.  This yields a configuration (x,n) for some
#m>=y>0, m=x+y.  By the inductive hypothesis,
#f(x,n)=x+n=(m-y)+n.  Since m-y <> m, m and m-y differ in some
#bit h.  This means (m-y)+n and m+n=r differ in some bit h, so
#f(x,n)<>r.  This gives us that r is not in S, and s is in S for s<r. 
#Thus, f(m,n)=m+n by the mex definition of f.

#Problem 3
#A position P is Losing iff its Sprague-Grundy function is 0.
#Proof: induction on the DAG of the game
#Base Case: P is a sink
#There are no positions reachable from P, so f(P)=mex({})=0 in this case. 
#P is a Losing position since #it is a sink.
#Induction Step:
#Assume that f(P)=0, so by the mex definition of f, f(Q)<>0 for any Q
#reachable from P.  By the inductive hypothesis, f(Q) is a Winning
#position.  This means that f(P) is a Losing position, since every
#position reachable from P is Winning.
#
#Now assume that P is a Losing position.  This means that every position Q
#reachable from P is a Winning position, so f(Q)<>0.  By the mex
#definition of f, f(P)=0.

#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) local k:
option remember:
mex({ seq(SGwyt(i-k,j),k=1..i), seq(SGwyt(i-k,j-k),k=1..i),
seq(SGwyt(i,j-k),k=1..j)}):
end:
#WinningMove(G,i): 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 k:

if SG(G,i)=0 then
 RETURN(FAIL):
fi:

for k in G[i] do
 if SG(G,k)=0 then
  RETURN(k):
 fi:
od:

end: