#OK to post homework 
#Natalya Ter-Saakov, April 10, Assignment 20
read "C20.txt":

#Problem 1

#ConjLP(R): inputs a finite set of positive integers R, and outputs the pair [M,C] where M is a positive integer ≥ 2 and C is a subset of {0,1,...,M-1} such that PR(n,R)[1]=0 if and only if n mod M belongs to C

ConjLP:=proc(R) local M,C,L:
M:=1:
L:=LP((nops(R))^3,R):
do M+=1: C:=convert(L mod M,set): until nops(C)<M:
[M,C]:
end:

#Problem 2

#ProveLP(R,M,C): proves automatically the conjecture that indeed n is a losing position for the R-game iff n mod M belongs to C, or returns FAIL.

ProveLP:= proc(R,M,C) local n,m,c:
for n from 0 to M-1 do
	if n in C then
		for m in R do
			if member((n-m) mod M,C) then
				return(FAIL): 
			fi:
		od:
	else
		c:={}:
		for m in R do
			if (n-m) mod M in C then
				c:=c union {m}:
			fi:
		od:
		if nops(c)=0 then
			return(FAIL):
		fi:
	fi:
od:
return(TRUE)
end:

#Problem 3

#Nim(N): inputs a list of non-negative integers if length k:=nops(N) and outputs 0,{} if it is a losing position, and 1,S, if it is a winning positiion where S is a list of pairs {[a,b]} meaning: remove b pennies from the a-th pile.

Nim:=proc(N) local k,i,S,a,b:
option remember:
k:=nops(N):
if N=[0$k] then return(0,{}): fi:
S:={}:
for a from 1 to k do
	for b from 1 to N[a] do
		if Nim([op(1..a-1,N),N[a]-b,op(a+1..nops(N),N)])[1]=0 then 
			S:= S union {[a,b]}:
		fi:
	od:
od:
if S={} then 0,S: else 1,S: fi:
end:


#Problem 4

#NimL(k,N): inputs a positive integer k, another positive integer N and outputs the set of lists of length k with entries ≤ N that are losing positions for k-pile Nim.

AllLists:=proc(k,N) local S,Sk1,a,l:
option remember:
S:={}:
if k=1 then return({seq([a],a=0..N)}): fi:
Sk1:=AllLists(k-1,N):
for a from 0 to N do
for l in Sk1 do
	S:=S union {[op(l),a]}:
od:
od:
S:
end:

NimL:= proc(k,N) local L, S:
S:={}:
for L in AllLists(k,N) do
if Nim(L)[1]=0 then S:=S union {L}: fi:
od:
S:
end:

#Problem 5

#(From prior knowledge) Convert the piles to binary and take the element-wise symmetric difference. If the result is all zero, then this is a losing position.

#Problem 6

#Conisder a variant of 2-pile Nim where in addition to the Nim moves of removing any number of pennies in one of the piles, a player is also allowed to remove the SAME number of pennies from both piles. Write a procedure Nim2V(a,b) that inputs non-negative integers a and b and outputs 0,{} or 1,S where the members of S are either of the form [i,0],[0,i],[i,i].

Nim2V:=proc(a,b) local S,i:
option remember:
S:={}:
if a=0 and b=0 then return(0,S): fi:
if a=0 and b<>0 then return(1,{[a,0]}): fi:
if a<>0 and b=0 then return(1,{[0,b]}): fi:
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:
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:
if S={} then 
0,S:
else
1,S:
fi:
end:

#Problem 7

#Nim2VL(N): inputs a positive integer N and outputs the LIST of pairs [a,b], 0 ≤ a ≤ b ≤ N, that are losing positions for the above game. with increasing order of the first component.

Nim2VL:=proc(N) local a,b,S:
option remember:
S:=[]:
for a from 0 to N do
	for b from a to N do
		if Nim2V(a,b)[1]=0 then 
			S:=[op(S),[a,b]]:
		fi:
	od:
od:
S:
end:

#Problem 8

#Characterize such losing pairs.