# restart; read `\G:/My Drive/MyNote/Talks/26.3 O6B
# /OOOOOB.txt`;

with(combinat):

# First version: December 9, 2025

# Accompany paper:
# GENERALIZING OOOOOOB
# by Alon Danai, Paul Ellis and myself

####################################
# Section 1: General Functions
#
# Functions:
# Mex(S), 
# AllPos(N,p), AllPile(N,p)
# GenOE(P,N), OE(P,N),
#
####################################

# Input: The set of non-negative
# integers S
# Output: Mex function of S, i.e.
# the first non-negative integer
# missing
# Try: Mex({0,1,3,6,2,4,12});
Mex := proc(S) option remember;
local s;

s := 0;

while member(s,S) do 
	s := s+1;
od:

return(s);
end:

# Input: positive integer N and p.
# Output: List of all positions 
# (increasing order) of p piles where 
# each pile has a max token N. 
# Try: AllPos(4,2);
AllPos := proc(N,p) option remember;
local i,P;

if p = 1 then
	return({seq([i],i=1..N)});
fi:	

[seq(seq([i,op(P)],i=1..P[1]) ,P in AllPos(N,p-1))];
end:

# Input: N maximum number of piles for each token  
# and p maximum number of tokens i.e. number of tuples
# Output: List of all positions [a1,...,ap] 
# where a_i is the number of piles with 
# i tokens
# Try: AllPile(2,3);
AllPile := proc(N,p) option remember;
local i,P;

if p = 1 then
	return({seq([i],i=0..N)});
fi:	

{seq(seq([i,op(P)],i=0..N) ,P in AllPile(N,p-1))};
end:

###################################################
# Input: the list P of "0 or 1" 
# and positive integer N
# Output: The set of all odd-even 
# positions according to P (with 
# maximum N tokens for each pile).
# Try: 
# GenOE([0,0],10);
# A:= GenOE([0,0,0,0,0,0],10) union GenOE([1,1,1,0,0,0],10):
# VerC(10,6) minus A:
GenOE := proc(P,N) option remember;
local a,b,p2,A,newP,S;

if nops(P) = 1 then
	return({seq([P[1]+2*i],i=0..floor((N-P[1])/2))});
fi:	

A := [seq(P[1]+2*i,i=0..floor((N-P[1])/2))];
S := {};

for a in A do
	p2 := P[2]+2*max(0,ceil((a-P[2])/2));
	newP := [p2,op(3..nops(P),P)];
	S := S union 
	{seq([a,op(b)],b in GenOE(newP,N))};
od:

S;
end:

# Input: the list P of "0 or 1" 
# and positive integer N
# Output: The set of all odd-even 
# positions according to the 
# permutation of P (with maximum 
# N tokens for each pile).
# Try:
# OE([0,1,1,1],5);
OE := proc(P,N) option remember;
local Q;

`union`(seq(GenOE(Q,N), Q in permute(P)));	
end:


####################################
# Section 2: Version B
#
# Functions:
# ValB(P), Lem21(G), Lem22(G),
# VerB(N,p), 
# SolB(N,p), CountOdd(o,S),
#
# ShortB(N,p), SolShortB3(N),
# SolShortB4(N), SolShortB5(N),
# TestOE(M,Mod1),
#
####################################

# Version B:
# A player may remove any one token or 
# remove one token from each pile.
# The last player to move wins.


# Input: list of tokens in each pile
# Output: 0 if losing position (P-position)
# and positive if winning position (N-position)
# Try:
# [seq(ValB([i]),i=1..10)];
ValB := proc(P) option remember;
local i,Q,p,S;

if min(P) <= 0 then
	ERROR("NotSupposeToHave0");
elif P = [] then
	return(0);
fi:

p := nops(P);
S := {};

for i from 1 to p do
	Q := P;
	if Q[i] = 1 then
		Q := [op(1..i-1,Q),op(i+1..p,Q)];
		S := S union {ValB(Q)};
	else
		Q[i] := Q[i]-1;
		S := S union {ValB(sort(Q))};	
	fi:
	
od:

Q := [seq(P[i]-1,i=1..p)];
i:=1:
while i<=p and Q[i]=0 do
	i:=i+1;
od:
Q := [op(i..p,Q)];	
S := S union {ValB(Q)};

Mex(S);	
end:


# Lemma2.1
# Input: Position G
# Output: True if 1,1,G and G
# have the same outcome class
# Try:
# Lem21([2,3,5]);
# {seq(Lem21(A), A in AllPos(7,7))};
Lem21 := proc(G) option remember;
local o1,o2; 

o1 := ValB(sort([1,1,op(G)]));
o2 := ValB(G);
#print(o1,o2);
if (o1=0 and o2=0) or (o1>0 and o2 >0) then
	return(true);
else
	return(false);
fi	
end:

# Lemma2.2
# Input: Position G
# Output: True if 2,2,G and G
# have the same outcome class
# Try:
# Lem22([2,3,5]);
# {seq(Lem22(A), A in AllPos(7,7))};
Lem22 := proc(G) option remember;
local o1,o2; 

if max(G) < 2 then
	return("max(G)<2");
fi:	

o1 := ValB(sort([2,2,op(G)]));
o2 := ValB(G);
#print(o1,o2);
if (o1=0 and o2=0) or (o1>0 and o2 >0) then
	return(true);
else
	return(false);
fi	
end:

##############################################

# Input: maximum number of token N 
# and number of piles p
# Output: the P-positions of version B
# Try:
# VerB(5,2);
VerB := proc(N,p) option remember;
local P,S;

S := {};
for P in AllPos(N,p) do
	if ValB(P) = 0 then
		S := S union {P};
	fi:
od:

S;	
end:

# Input: maximum number of token N 
# and number of piles p.
# Output: Solution of P-positions to version B 
# Try:
# SolB(10,2); VerB(10,2); evalb(SolB(10,2)=VerB(10,2));
# SolB(10,3); VerB(10,3); evalb(SolB(10,3)=VerB(10,3));
# SolB(15,4); VerB(15,4); evalb(SolB(15,4)=VerB(15,4));
# SolB(18,5); VerB(18,5); evalb(SolB(18,5)=VerB(18,5));
# seq(evalb( VerB(n,6)=SolB(n,6)),n=1..15);
SolB := proc(N,p) option remember;
local a,S;

if p =2 then
	S := GenOE([2,2],N);
elif p =3 then
	S := OE([2,2,2],N) union OE([2,1,1],N);
elif p =4 then
	S := OE([2,2,2,2],N)    					#0Odd 
	union {seq([1,1,op(a)],a in OE([2,2],N))} 	#2Odds 
	union OE([2,3,3,3],N);   					#3Odds 
elif p =5 then
	S := OE([2,2,2,2,2],N)   					#0Odd
	union {seq([1,1,op(a)],a in OE([2,2,2],N))} #2Odds
	union {seq([1,2,op(a)],a in OE([2,2,3],N))} 
	union OE([2,2,2,3,3],N)
	minus {seq([2,op(a)],a in OE([4,4,5,5],N))} 
	union {seq([1,op(a)],a in OE([4,4,5,5],N))} #3Odds
	union {seq([1,1,op(a)],a in OE([1,1,2],N))} #4Odds
	union OE([2,3,3,3,3],N);
elif p =6 then
	S := OE([2,2,2,2,2,2],N)  # 0 Odd
	union {seq([1,1,op(a)],a in OE([2,2,2,2],N))} #2Odds
	union {seq([1,2,op(a)],a in OE([3,4,4,4],N))}
	union {seq([2,3,op(a)],a in OE([5,6,6,6],N))}
	union OE([3,3,4,4,4,4],N)
	union {seq([2,op(a)],a in OE([2,2,3,3,3],N))} #3Odds
	minus {seq([2,3,op(a)],a in OE([5,5,6,6],N))} 
	union {seq([1,1,1,1,op(a)],a in OE([2,2],N))} #4Odds
	union {seq([1,3,op(a)],a in OE([5,5,6,6],N))} 
	union {seq([1,1,op(a)],a in OE([2,3,3,3],N))} #5Odds
	union OE([2,3,3,3,3,3],N);
	
else
	return("NoCaseYet");
fi:	

return(S);
end:

CountOdd := proc(o,S) option remember;
local s,c;

c := add( s mod 2, s in S);
if c =o then
	return(S);
else
	return();
fi:	
end:

########################################

# Input: N maximum number of piles for each token  
# and p maximum number of tokens i.e. number of tuples
# Output: List of P-positions [a1,...,ap] 
# where a_i is the number of piles with 
# i tokens of version B
# Try:
# ShortB(2,3);
ShortB := proc(N,p) option remember;
local i,R,P,S;

S := {};
for R in AllPile(N,p) do
	P := [seq(i$R[i],i=1..p)];
	if ValB(P) = 0 then
		S := S union {R};
	fi:
od:

S;	
end:

# Input: positive integer N
# Output: (with #of token in each 
# pile is {1,2,3}). Set of P-positions 
# with at most N piles for each token. 
# Try:
# A:=ShortB(5,3);
# B:=SolShortB3(5);
# evalb(A=B);
# 
# [seq(evalb(ShortB(n,3)=SolShortB3(n)),n=0..20)];
SolShortB3 := proc(N) option remember;
local i,j,k;

{[0,0,0]
,seq(seq([2*i,j,0],j=1..N),i=0..floor(N/2))
,seq(seq([2*i-1,2*j-1,1],j=1..ceil(N/2)),i=1..ceil(N/2))
,seq(seq(seq([2*i,2*j-1,k],k=2..N)
,j=1..ceil(N/2)),i=0..floor(N/2))};

end:

# Input: N maximum number of piles for each token 
# Output: (with #of token in each 
# pile is {1,2,3,4}). Set of P-positions 
# with at most N piles for each token. 
# Try:
# SolShortB4(5);
# [seq(evalb(ShortB(n,4)=SolShortB4(n)),n=1..12)];
SolShortB4 := proc(N) option remember;
local i,j,k,m,E,E4,O,O3,All,A,B;

A := {seq([op(M),0], M in SolShortB3(N))};

E := {seq(2*i,i=0..floor(N/2))};
E4 := {seq(2*i,i=2..floor(N/2))};
O := {seq(2*i-1,i=1..ceil(N/2))};
O3 := {seq(2*i-1,i=2..ceil(N/2))};
All := E union O;

B := { seq(seq([i,j,1,1],j in E),i in O)
,seq(seq(seq([i,j,k,1],k=2..N),j in E),i in E)
,seq(seq(seq([i,j,0,m],m=1..min(2,N)),j in E),i in E)
,seq(seq(seq([i,j,0,m],m=1..min(3,N)),j in O),i in E)
,seq(seq(seq([i,j,1,m],m=2..min(3,N)),j in O),i in O)
,seq(seq(seq(seq([i,j,k,m],m=3..N),k in E),j in E),i in E)
,seq(seq(seq(seq([i,j,k,m],m=4..N),k in E),j in O),i in E)
,seq(seq(seq(seq([i,j,k,m],m=4..N),k in O),j in O),i in O)
};

if N >= 2 then
	B := B union {
	seq(seq(seq([i,j,k,2],k in E4),j in All),i in O)	
	,seq(seq(seq([i,j,k,2],k in O3),j in O),i in E)
	,seq(seq([i,j,2,2],j in O),i in E)
	} 
fi:

A union B;
end:


# Input: N maximum number of piles for each token 
# Output: (with #of token in each 
# pile is {1,2,3,4,5}). Set of P-positions 
# with at most N piles for each token. 
# Try:
# SolShortB5(5);
# seq(print(n,evalb(ShortB(n,5)=SolShortB5(n))),n=1..9);
SolShortB5 := proc(N) option remember;
local s,i,j,k,m,n,E,O,All,ES,OS,AS,A,B,C,S,T;

A := {seq([op(M),0], M in SolShortB4(N))};

E := {seq(2*i,i=0..floor(N/2))};
O := {seq(2*i-1,i=1..ceil(N/2))};
All := E union O;
ES := s->{seq(2*i,i=s/2..floor(N/2))};
OS := s->{seq(2*i-1,i=(s+1)/2..ceil(N/2))};
AS := s-> {seq(i,i=s..N)};

B := { 
# Group 1: [e,e,e]
seq(seq(seq(seq([i,j,k,m,2]
,m in ES(4)),k in E),j in E),i in E)
,seq(seq(seq(seq([i,j,k,m,2]
,m in O),k in E),j in E),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in AS(4)),m in O),k in E),j in E),i in E)
,seq(seq(seq(seq([i,j,k,1,n],
n in {1,3}),k in E),j in E),i in E)
# Group 2: [e,e,o]
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {1,3}),m in ES(4)),k in O),j in E),i in E)
,seq(seq(seq(seq([i,j,k,1,n],
n in {2,4}),k in O),j in E),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in AS(5)),m in O),k in O),j in E),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {1,3}),m in O),k in O),j in E),i in E)
# Group 3: [e,o,e]
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in AS(6)),m in E),k in E),j in O),i in E)
,seq(seq(seq(seq([i,j,k,m,4],
m in ES(4)),k in E),j in O),i in E)
,seq(seq(seq(seq([i,j,k,0,n],
n in {2,4}),k in E),j in O),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in O),m in {0,2}),k in E),j in O),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {2,4}),m in OS(5)),k in E),j in O),i in E)
,seq(seq(seq([i,j,k,3,3],k in E),j in O),i in E)
# Group 4: [e,o,o]
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in AS(5)),m in E),k in O),j in O),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {2,4}),m in {0,2}),k in O),j in O),i in E)
,seq(seq(seq(seq([i,j,k,m,3],
m in ES(6)),k in O),j in O),i in E)
,seq(seq(seq(seq([i,j,k,m,1],
m in ES(4)),k in O),j in O),i in E)
,seq(seq(seq(seq([i,j,k,0,n],
n in {1,3}),k in O),j in O),i in E)
,seq(seq([i,j,1,2,1],j in O),i in E)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {1,3}),m in OS(5)),k in O),j in O),i in E)
# Group 5: [o,e,e]
,seq(seq(seq([i,j,k,2,2],k in E),j in E),i in O)
,seq(seq(seq(seq([i,j,k,m,3],
m in OS(5)),k in E),j in E),i in O)
,seq(seq([i,j,0,1,1],j in E),i in O)
# Group 6: [o,e,o]
,seq(seq(seq(seq([i,j,k,m,2],
m in ES(4)),k in O),j in E),i in O)
,seq(seq(seq(seq([i,j,k,2,n],
n in {1,3}),k in O),j in E),i in O)
,seq(seq(seq(seq([i,j,k,m,4],
m in OS(3)),k in O),j in E),i in O)
# Group 7: [o,o,e]
,seq(seq(seq(seq([i,j,k,2,n],
n in {2,4}),k in E),j in O),i in O)
,seq(seq(seq([i,j,0,m,1],m in {0,2}),j in O),i in O)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {1,3,5}),m in ES(4)),k in E),j in O),i in O)
,seq(seq(seq(seq(seq([i,j,k,m,n],
n in {1,3}),m in OS(5)),k in E),j in O),i in O)
,seq(seq([i,j,0,3,1],j in O),i in O)
# Group 8: [o,o,o]
,seq(seq(seq(seq([i,j,k,m,4]
,m in ES(4)),k in O),j in O),i in O)
,seq(seq(seq(seq([i,j,k,2,n]
,n in {1,3}),k in O),j in O),i in O)
,seq(seq(seq(seq([i,j,k,m,2]
,m in OS(5)),k in O),j in O),i in O)
,seq(seq(seq([i,j,k,3,3],k in O),j in O),i in O)
};

C := {seq(seq([i,j,0,1,1],j in E),i in E)
,seq(seq(seq([i,j,k,3,3],k in O),j in E),i in E)
,seq(seq(seq([i,j,0,m,1],m in {0,2}),j in O),i in E)
,seq(seq([i,j,1,2,1],j in E),i in O)
,seq(seq([i,j,0,2,2],j in O),i in O)
,seq(seq(seq([i,j,k,4,3],k in E),j in O),i in O)
,seq(seq([i,j,1,2,1],j in O),i in O)
};

S := (A union B) minus C;
T := {};
for s in S do
	if max(s) <= N then
		T := T union {s};
	fi:
od:

T;	
end:


##############################################
# Test odd even of elements in the set M
# Try: TestOE(M,[{0},{0},{0},{0,1}]);
TestOE := proc(M,Mod1) option remember;
local m,S;

S :={};
for m in M do
	if member(m[1] mod 2,Mod1[1]) 
	and member(m[2] mod 2,Mod1[2]) 
	and member(m[3] mod 2,Mod1[3])
	and member(m[4] mod 2,Mod1[4]) 
	and member(m[5] mod 2,Mod1[5]) 
	then
		S := S union {m}; 
	fi:
od:
return(S);	
end:


####################################
# Section 3: Version C
#
# Functions:
# ValC(P), RemoveZero(P), 
# VerC(N,p), SolC(N,p),
#
# ShortC(p), SolShortC3(p),
# Start1(P), 
#
####################################

# Version C:
# A player may remove any one token or 
# select two piles and remove one token from each.
# The last player to move wins.

# Input: list of tokens in each pile
# Output: 0 if losing position (P-position)
# and positive if winning position (N-position)
# Try:
# [seq(ValC([i]),i=1..10)];
# A:=[seq([seq([seq(ValC([i,j,k])
# ,k=j..10)],j=i..10)],i=1..10)];
ValC := proc(P) option remember;
local i,j,p,Q,S;

if min(P) <= 0 then
	ERROR("NotSupposeToHave0");
elif P = [] then
	return(0);
fi:

p := nops(P);
S := {};

for i from 1 to p do
	Q := P;
	if Q[i] = 1 then
		Q := [op(1..i-1,Q),op(i+1..p,Q)];
		S := S union {ValC(Q)};
	else
		Q[i] := Q[i]-1;
		S := S union {ValC(sort(Q))};	
	fi:
	
od:

# choose 2 piles and remove 1 
# token from these piles
for i from 1 to p do
for j from i+1 to p do
	Q := P;
	Q[i] := Q[i]-1;
	Q[j] := Q[j]-1;
	Q := RemoveZero(Q);
	S := S union {ValC(sort(Q))};
od; od;

Mex(S);	
end:

# Input: list of numbers P
# Output: The same list P but 
# zeros are removed.
# Try:
# RemoveZero([0,4,7,2,0,1,3,0,2]);
RemoveZero := proc(P) option remember;
local i,Q;

if min(P) >0 then
	return(P);
fi:

Q := [];
for i from 1 to nops(P) do
	if P[i]<>0 then
		Q := [op(Q),P[i]];
	fi:
od:

Q;	
end:

#################################################

# Input: maximum number of token N 
# and number of piles p.
# Output: the P-positions of version C
# Try:
# VerC(10,1);
# VerC(10,2);
VerC := proc(N,p) option remember;
local P,S;

S := {};
for P in AllPos(N,p) do
	if ValC(P) = 0 then
		S := S union {P};
	fi:
od:

S;	
end:


# Input: maximum number of token N 
# and number of piles p.
# Output: Solution of P-positions to version C
# Try:
# VerC(5,2); SolC(5,2);
# evalb(SolC(6,3)=VerC(6,3));
# evalb(SolC(15,4)=VerC(15,4));
# evalb(SolC(20,5)=VerC(20,5));
SolC := proc(N,p) option remember;
local a,S;

if p =2 then
	S := GenOE([2,2],N);
elif p =3 then
	S := GenOE([1,1,1],N) union GenOE([2,2,2],N);
elif p =4 then
	S := GenOE([2,1,1,1],N) union GenOE([2,2,2,2],N);
elif p =5 then
	S := GenOE([2,2,2,2,2],N) union GenOE([2,2,1,1,1],N)
   union GenOE([1,1,2,2,1],N) union GenOE([1,1,1,1,2],N);
elif p =6 then    
	S := GenOE([2,2,2,2,2,2],N) 
	union {seq([1,1,op(a)],a in GenOE([2,2,3,3],N))}  
	union {seq([1,1,op(a)],a in GenOE([2,3,4,4],N))}  ;
	# Complicated for 6 piles. This is not done!    
else
	return("NoCaseYet");
fi:	

return(S);
end:

########################################

# Input: maximum number of 
# piles p for each 1,2,3 tokens.
# Output: List of P-positions [n1,n2,n3] of version C
# Try:
# ShortC(3,3);
#
# seq( print(n,ShortC(n,3) minus SolShortC3(n)),n=1..11);
# seq( print(SolShortC3(n) minus ShortC(n,3)),n=1..11);
#
# A:=ShortC(4,5):
# [seq( (a[1]+2*a[2]+4*a[4]+5*a[5]) mod 3, a in A)];
ShortC := proc(N,p) option remember;
local R,P,S;

S := {};
for R in AllPile(N,p) do
	P := [seq(i$R[i],i=1..p)];
	if ValC(P) = 0 then
		S := S union {R};
	fi:
od:

S;	
end:

# Input: positive integer p
# Output: (with #of token in each 
# pile is {1,2,3}). Set of P-positions 
# with at most p piles for each token. 
# Try: SolShortC3(7);
SolShortC3 := proc(p) option remember;
local a,a1,a2,B,C,S;

S := {};

# Step1: add exception
B := {[0,1,3],[0,2,3],[1,0,2],[1,0,5],[2,0,1]};
for a in B do
	if max(a) <= p then
		S := S union {a};
	fi:
od:	

# Step2: add another exception
S := S union {seq([0,i,0],i=0..p)};

# Step3: Main case: if (a1+2*a2) divisible by 3.
for a1 from 0 to p do
for a2 from 0 to p do
	if (a1+2*a2) mod 3 = 0 then
		S := S union {seq( [a1,a2,i],i=Start1([a1,a2])..p)};
	fi:
od: od:	

# Step4: delete something that I added
C:= {[0,0,4],[0,0,5],[1,1,2],[1,1,3],[1,1,4],[1,1,5]
,[2,2,3],[3,0,1],[3,0,2],[3,0,5]};	
S minus C;	
end:

Start1 := proc(P) option remember;

if P[1]=0 and P[2] mod 3=0 then
	3;
elif P[1]=1 and P[2] mod 3=1 then
	2;
elif P[1]=2 and P[2] mod 3=2 then
	1;	
else
	0;
fi:	

end:

IsMod3 := proc(A) option remember;
local i,n;

n := nops(A);
if add( i*A[i],i=1..n) mod 3 = 0 then
	return(A);
fi:
return();	
end: