# Please do not post
# Daniela Elizondo
# Assignment 20
# April 10, 2022

read "C20.txt":
with(combinat):

##### 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, n:
M := 2:
L := LP(10000, R):
while nops(convert(L mod M, set)) >= M do:
    M += 1:
    od:

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

# check that PR(n,R)[1]=0??
[M,C]:
end:

##### Problem 2 #####

ProveLP := proc(R,M,C) local n, N, r, LPs, NLPs:
N := 10000:
LPs := LP(N,R):

for n in LPs do:
    if not member(n mod M, C) then return FAIL: fi:
    od:

NLPs := {}: # set of non-losing positions
for n from 0 to N do:
    for r in R do:
        if member(n-r, LPs) then
            NLPs := NLPs union {n-r}:
        fi:
    od:
od:
true:

end:

##### Problem 3 #####

Nim := proc(N) local Ncopy, k, S, a, b:
option remember:
k := nops(N):
S := {}:

for a from 1 to k do:
    Ncopy := N:
    for b from 1 to N[a] do:
        Ncopy[a] := N[a]-b:
        if Nim(Ncopy)[1] = 0 then
            S := S union {[a,b]}:
        fi:
    od:
od:

if S = {} then 
    0,S:
else   
    1,S:
fi:

end:

##### Problem 4 #####

NimL := proc(k,N) local S, opt, list, i, j:
S := {}:
opt := [seq(i, i=0..N)]:
opt := [seq(op(opt), j=1..k)]:

for list in permute(opt, k) do
    if Nim(list)[1] = 0 then
        S := S union {list}:
    fi:
od:
S:
end:

##### Problem 6 #####

Nim2V := proc(a,b) local S,i:
S := {}:
for i from 1 to max(a,b) do:
    if i <= a and Nim2V(a-i,b)[1]=0 then
        S := S union {[i,0]}: fi:
    if i<= b and Nim2V(a,b-i)[1]=0 then
        S := S union {[0,i]}: fi:
    if i<=a and i<=b and 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 := proc(N) local L, a, b:
L := []:
for a from 0 to N do:
    for b from a to N do:
        if Nim2V(a,b)[1] = 0 then
            L := [op(L), [a,b]]:
        fi:
    od:
od:

L:

end: