# OK to post homework
# Vikrant, Apr 10 2022, Assignment 20

# ================================================================================
# 0. Code that has been given.
# ================================================================================

read("C20.txt"):

# ================================================================================
# 1. Automated conjectures for losing positions.
# ================================================================================

ConjLP:=
    proc(R)
        local lps:= LP((mul(R)+1)^2,R):
        local M:= min(convert(lps,set) minus {1}):
        while nops(convert(lps mod M,set))>=M do
            M:= M+1:
        od:
        M,convert(lps mod M,set):
    end:

# ================================================================================
# 2. Automated proofs for losing positions.
# ================================================================================

ProveLP:=
    proc(R,M,C)
        local r,l,w,i:
        # Do conjectured losing positions always lead to winning positions?
        if {seq(seq((l-r) mod M,l in C),r in R)} intersect C<>{} then
            return(FAIL):
        fi:
        # Can conjectured winning positions lead to losing positions?
        if 0 in {seq(nops({seq((w-r) mod M,r in R)} intersect C), w in {seq(i,i=0..M-1)} minus C)} then
            return(FAIL):
        fi:
        true:
    end:

# ================================================================================
# 3. k-pile Nim.
# ================================================================================

Nim:=
    proc(P)
        option remember:
        local i,n:
        local S:= {}:
        for i from 1 to nops(P) do
            for n from 1 to P[i] do
                if Nim(P-[0$(i-1),n,0$(nops(P)-i)])[1]=0 then
                    S:= S union {[i,n]}:
                fi:
            od:
        od:
        subs([false=0,true=1],evalb(S<>{})),S:
    end:

# ================================================================================
# 4. Losing positions for k-pile Nim.
# ================================================================================

NimPs:=
    proc(k,N,s)
        local i,x:
        if k=1 then
            return {seq([i],i=s..N)}:
        fi:
        {seq(seq([i,op(x)],x in NimP(k-1,N,i)),i=s..N)}:
    end:

NimL:=
    proc(k,N)
        local P:
        {seq(`if`(Nim(P)[1]=0,P,NULL),P in NimPs(k,N,0))}:
    end:

# ================================================================================
# 5. Losing positions for 3-pile Nim.
# ================================================================================

(*
    # Played Nim before, so this is mostly from memory: 
    # the losing positions are when the bitwise xor of the 3 piles is 0.

    # Why?
    #
    # Suppose that the xor of the 3 piles is 0.
    # Then it is clear that any move changes the xor of the 3 piles to non-0.
    #
    # Suppose, conversely, that the xor of the 3 piles is non-0.
    # We show a move that changes the xor of the 3 piles to 0.
    # Look at the most significant bit of the xor of the 3 piles; call this position J.
    # At least one of the piles must have a 1 in position J in its binary representation.
    # Pick any such pile arbitrarily; call it P.
    # Set X to just enough so that the Jth bit of (P-X) is 0.
    # Set Y to the xor of (P-X) and the other two piles to X.
    # Remove X+Y from P.
    # This is possible since (P-X)>=Y since the 0th through (J-1)st bits of (P-X) are all 1s.
*)

# ================================================================================
# 6. 2-pile Nim where you can remove the same number from each pile in one turn.
# ================================================================================

Nim2V:=
    proc(a,b)
        option remember:
        local i:
        local S:= {}:
        for i from 1 to min(a,b) do
            if Nim2V(a-i,b-i)[1]=0 then
                S:= S union {[i,i]}:
            fi:
        od:
        for i from 1 to a do
            if Nim2V(a-i,b)[1]=0 then
                S:= S union {[i,0]}:
            fi:
        od:
        for i from 1 to b do
            if Nim2V(a,b-i)[1]=0 then
                S:= S union {[0,i]}:
            fi:
        od:
        subs([false=0,true=1],evalb(S<>{})),S:
    end:

# ================================================================================
# 7. Losing positions for 2-pile Nim variation above.
# ================================================================================

Nim2VL:=
    proc(N)
        local a,b:
        {seq(seq(`if`(Nim2V(a,b)[1]=0,[a,b],NULL),b=a..N),a=0..N)}:
    end:

# ================================================================================
# 8. Losing positions for 2-pile Nim variation above.
# ================================================================================

# Let P_0 = {[0,0]}.
# Let P_i = P_{i-1} union {[m_i,m_i+i]}
#  where m_i = min(N \ ({a|[a,b] in P_{i-1}} union {b|[a,b] in P_{i-1}})).
#  and N is the natural numbers.

# The losing positions are P_infinity.

# To see this, first observe that every natural number > 0 occurs as exactly one of the left or right coordinate of exactly one member of P_infinity.
# Why?
# By definition a number n>0 cannot not be a coordinate of some member of P_infinity (it will be some m_i eventually if not a right coordinate).
# So consider the smallest i such that n>0 is the coordinate of one of its members.
# If n>0 is a right coordinate, it will not be a right coordinate of any other member of P_infinity since all members of P_j \ P_i for j>i have greater right coordinates.
#  That n>0 is not a left coordinate of some member of P_infinity is clear to see.
# If n>0, on the other hand, is a left coordinate, it is easy to see it will never be another coordinate of another member of P_infinity.
# We summarize this observation by saying that every n>0 has a pairing in P_infinity.

# Finally, observe the following (a <= b wlog):
# If [a,b] is in P_infinity, any available move sends it outside of P_infinity.
#  Removing from only one pile sends it outside of P_infinity by the above observation.
#  Taking i from both piles sends it to [a-i,b-i], but a-i is paired in P_infinity with b-i-j for some j>0.
# If [a,b] is not in P_infinity, conversely:
#  If b is greater than a's pairing in P_infinity, we can send b to a's pairing.
#  If b is less than a's pairing in P_infinity, we can send a to m_{b-a} and b to m_{b-a}+b-a, which are paired in P_infinity.