# Please do not post homework
# Kayla Gibson
# April 4, 2022
# Assignment 20


#1. Write a procedure ConjLP(R) which takes as input 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. For exmaple,
#	ConjLP({1,2})	should output	[3,{0}]
# Hint: first output LP(10000,R), call it, L, say, then look for the smallest M such that 
# convert(L mod M, set) has less than M elements. This is your conjectured M. Then, for that M,
# convert(L mod M,set) is your conjectured C.


ConjLP:= proc(R) local L,M,C,i,j: 
L:=LP(10000,R):
M:=2:

while nops(convert(L mod M,set))>=M do
M:=M+1:
od:

C:=convert(L mod M, set):

for j in R do
 if PR(j,R)[1]=0 and not j in C then
  C:=C union {j}:
  if j>=M then
   M:=j:
  fi:
 fi:
od:

for i from 0 to M-1 do
 if i in C and PR(i,R)[1]=1 then
  C:=C minus {i}:
 fi:
od:

[M,C]:
end:


#2. [A little bit challenging, but do your best] Write a procedure ProveLP(R,M,C) which 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.
# Hint: the defining property of the set of losing positions of a game is that every legal move
# (in this game, subtracting an element of R, is NOT in that set), and for every element, n, 
# NOT in that set, there exists an element r, in R, such that n-r is in the set.

ProveLP:=proc(R,M,C) local: end:

#3. The classical game of k-file Nim consists of k piles having n[1],..., n[k] pennies respectively,
# and a legal move consists of taking as many as one wishes (from 1 to the whole) from ONE pile.  
# For exmaple from the position [3,2,2] one can reach, in one move, 
#		[2,2,2],[1,2,2],[0,2,2];[3,1,2],[3,0,2];[3,2,1],[3,2,0];
# Write a procedure Nim(N) that inputs a list of non-negative integers of length k:=nops(N)
# and outputs 0,{} if it is a losing position, and 1,S, if it is a winning position where S is a
# list of pairs {[a,b]} meaning: remove b pennies from the a-th pile. For example
#	Nim([3,3]) should output 0,{}	Nim([7,3]) should output 1,{[1,4]}

Nim:=proc(N) local i,j,k,n,S,R: 
option remember:

n:=nops(N):
R:={seq(k, k=1..)}
S:={}:
for i from 1 to n do
for j from 1 to N[i] do
 if Nim(subsop(i=N[i]-j,N))[1]=0 then
   S:=S union {[i,j]}:
 fi:
od:
od:
if S={} then
 0,S:
else
 1,S:
fi:
end:


#4. Write a procedure NimL(k,N) which takes as input positive integers k and N and outputs the set
# of lists of length k with entries ≤ N that are losing positions for k-pile Nim. For example
# NimL(2,3) should output {[0,0],[1,1],[2,2],[3,3]}



#5. [Optional challenge, please do it all by yourself] Without looking it up, find a quick way 
# to decide whether a triple of non-negative integers [a,b,c] is a losing position in 3-pile Nim.

#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) which takes as input 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]. For example,
#	Nim2V(2,1) should output 0,{}	Nim2V(3,2) should output 1,{[1,1]}

Nim2V:=proc(a,b) local: end:

#7. Write a procedure Nim2VL(N) which takes as input 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: end:


#8. [Optional challenge, please no peeking in the literature] 
#	Characterize such losing pairs.