######################################################################
## FakeCoin.txt Save this file as  FakeCoin.txt  to use it,          #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read FakeCoin <Enter>                             #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  DoronZeil at gmail dot com                                       # 
######################################################################


print(`First Written: Feb. 24, 2021: tested for Maple 2018 `):
print(`Version  : Feb. 24, 2021:  `):
print():
print(`This is FakeCoin.txt, A Maple package`):
print(`accompanying Doron Zeilberger's RUMA talk, Feb. 24, 2021 `):
print(`How to Get the Right Answer with as few questions as possible?`):

print(`  `):

print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/FakeCoin.txt `):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`For a list of the supporting functions type: ezra1();`):
print():
 



ezra1:=proc()
if args=NULL then

print(`The SUPPORTING procedures are:  BestNei, Bni,  CoinsA, CoinsG, IsCW, Pairs, RandStart, Score1, Vecs, Wt`):
print(``):

else
ezra(args):

fi:


end:

ezra:=proc()
if args=NULL then

print(` FakeCoin.txt: A Maple package for solving fake-coin weighing problem inspired by the famous 12 coin problem  `):

print(`The MAIN procedures are: Coins, CoinsD,  FindFake, MagicSet, SpellOut, Wei `):
print(``):

elif nargs=1 and args[1]=BestNei then
print(`BestNei(P,v): The set of best neighbors of v, with its score`):

elif nargs=1 and args[1]=Bni then
print(`Bni(n,i): the set of integers from  1 to 2^(n)-1 where 2^i shows up in the binary represnetaion`):

elif nargs=1 and args[1]=CoinsA then
print(`CoinsA(n,x): All the solutions to the n-weighing fake coin problem, using computer algebra. Try:`):
print(`CoinsA(3,x);`):

elif nargs=1 and args[1]=Coins then
print(`Coins(n,K): Inputs a positive integer n>=2 and a positive integer K>=10.`):
print(` Outputs ONE solution to deciding on the forgerd coin, using n weighing if you have (3^n-3)/3 coins.`):
print(`it tries up to K times. K should be at least 10. Try: `):
print(`Coins(3,10);`):

elif nargs=1 and args[1]=CoinsD then
 print(`CoinsD(n): Like Coins(n,K) but using 22-year-old Freeman Dyosn's ingenious method. `):
print(` "The problem of the pennies" (The Math. Gazette, Oct. 1946, vol. 30, No. 291, pp. 231-234), available from JSTOR`):
print(`Try`):
print(`CoinsD(3);`):


elif nargs=1 and args[1]=CoinsG then
print(`CoinsA(n,k,x): All the solutions to the n-weighing fake coin problem with k coins rather than (3^n-3)/2, using computer algebra. Try:`):
print(`CoinsG(3,10,x);`):


elif nargs=1 and args[1]=FindFake then
print(`FindFake(P,v,n): Inputs a weighing protocol P consising of the "dictionary" P[1],`):
print(`the protocol P[2], and the list of weights of the (3^n-3)/2 coins where there are all`):
print(`the same except for one that is heavier or lighther, and checks whether the weighinting`):
print(`protocol actually finds it . Try:`):
print(`P:=Coins(3,20); `):
print(`FindFake(P,[0$9,1,0,0],3);`):

elif nargs=1 and args[1]=IsCW then
print(`IsCW(w): Is the vector w in {-1,0,1} clockwise? Try:`):
print(`IsCW([1,1,-1]);`):

elif nargs=1 and args[1]=MagicSet then
print(`MagicSet(n): The magic set for 2^n-1`):

elif nargs=1 and args[1]=Pairs then
print(`Pairs(n): the set of (3^n-3)/2 pairs of vectors with entries in {-1,0,1},of length n, and their negatives`):

elif nargs=1 and args[1]=RandStart then
print(`RandStart(n): Random starting  vector of length n in {1,2}`):

elif nargs=1 and args[1]=Score1 then
print(`Score1(P,v): Given a list of pairs P and a vector of of the same length of 1-2`):
print(`finds the score of the vector by choosing according to v`):


elif nargs=1 and args[1]=SpellOut then
print(`SpellOut(M): Given the output of either Coins(n,K) or CoinsD(n), gives detailed instructions`):
print(`Try:`):
print(`SpellOut(CoinsD(3)):`):


elif nargs=1 and args[1]=Wei then
print(`Wei(v,n,P): inputs a vector of length (3^n-3)/2 indicating the weights of (3^n-3)/2 similar looking coins`):
print(`and a weighing instructions P which is a list of length n telling you to put the set of coins in P[i][1]`):
print(`on the left arm and the set of coins in P[i][2] on the right arm`):
print(`outputs the vector of length n in {0,1,-1} indicating the outcomes of the n weighings. Try`):
print(`Wei([0,1,0],2,[[{1}, {2}], [{2}, {3}]]);`):
print(`Wei([0$9,-1,0,0],3, [[{1, 4, 6, 8}, {2, 3, 5, 7}], [{1, 7, 10, 11}, {2, 6, 8, 9}], [{2, 5, 6, 12}, {3, 8, 9, 11}] ] );`):

elif nargs=1 and args[1]=Wt then
print(`Wt(V,x,y): the weight of the vectore V in terms of x and y`):

elif nargs=1 and args[1]=Vecs then
print(`Vecs(n): all vectors of length n in {-1,0,1}`):

else
 print(`There is no such thing as`, args):

fi:


end:



with(combinat):

#Vecs(n): all vectors of length n in {-1,0,1}
Vecs:=proc(n) local T,t,i:
option remember:
if n=0 then RETURN({[]}): fi:
T:=Vecs(n-1):{seq(seq([op(t),i],t in T),i=-1..1)}:
end:

#Pairs(n): the set of (3^n-3)/2 pairs
Pairs:=proc(n) local gu,gu1,i,mu:
option remember:
gu:=Vecs(n) minus {seq([i$n],i=-1..1)} :
mu:={}:

while gu<>{} do 
 gu1:=gu[1]:
 mu:=mu union {[gu1,-gu1]}:
 gu:=gu minus {gu1,-gu1}:
od:
convert(mu,list):
end:

#Wt(V,x,y)
Wt:=proc(V,x,y) local i: x[V]*mul(y[i]^V[i],i=1..nops(V)):end:

#CoinsA(n,x): All the solutions to the n-weighing fake coin problem, using computer algebra. Try:
#CoinsA(3,x);
CoinsA:=proc(n,x) local y,gu,mu,i:
gu:=Pairs(n):
mu:=mul(Wt(gu[i][1],x,y)+Wt(gu[i][2],x,y),i=1..nops(gu)):
for i from 1 to n do
mu:=coeff(mu,y[i],0):
od:
expand(mu):
end:


CoinsG:=proc(n,k,x) local y,gu,mu,i,t:
gu:=Pairs(n):
mu:=mul(1+t*(Wt(gu[i][1],x,y)+Wt(gu[i][2],x,y)),i=1..nops(gu)):
mu:=coeff(mu,t,k):
for i from 1 to n do
mu:=coeff(mu,y[i],0):
od:
expand(mu):
end:

#RandStart(n): Random starting  vector
RandStart:=proc(n) local i,ra:
ra:=rand(1..2):
[seq(ra(),i=1..(3^n-3)/2)]:
end:


#Score1(P,v): Given a list of pairs P and a vector of of the same length of 1-2
#finds the score of the vector by choosing according to v
Score1:=proc(P,v) local i,M,L:
M:=[seq(P[i][v[i]],i=1..nops(v))]:
L:=add(M[i],i=1..nops(M)):

add(L[i]^2,i=1..nops(L)):

end:

#BestNei(P,v): The set of best neighbors of v, with its score
BestNei:=proc(P,v) local gu,i,aluf,si,halev:
gu:={seq([op(1..i-1,v),3-v[i],op(i+1..nops(v),v)],i=1..nops(v))}:

aluf:={gu[1]}:
si:=Score1(P,gu[1]):


for i from 2 to nops(gu) do
 halev:=Score1(P,gu[i]):
 if halev<si then
  aluf:={gu[i]}:
  si:=halev:
 elif halev=si then
   aluf:=aluf union {gu[i]}:
 fi:
od:

aluf,si:

end:

#Coins(n,K): Finds ONE solution to deciding on the forgerd coin, using n weighing if you have (3^n-3)/3 coins.
#it tries up to K times
#Try:
#Coins(3,K);
Coins:=proc(n,K) local v,P,gu,i,M,Tleft,Tright,i1,j:

if not (type(n,integer) and n>=2 and type(K,integer) and type(K,integer)) then
print(`Bad input`):
 RETURN(FAIL):
fi:

if K<10 then
 print(K, `should be at least 10`):
 RETURN(FAIL):
fi:

v:=RandStart(n):
P:=Pairs(n):

gu:=BestNei(P,v):

for i from 1 to K while gu[2]>0 do
 gu:=BestNei(P,gu[1][1]):
od:

if gu[2]>0 then 
RETURN(FAIL):
fi:

v:=gu[1][1]:

M:=[seq(P[i][v[i]],i=1..nops(v))]:


for j from 1 to n do
Tleft[j]:={}:
Tright[j]:={}:
od:

for i1 from 1 to nops(M) do
v:=M[i1]:

for j from 1 to n do

if v[j]=1 then
 Tleft[j]:=Tleft[j] union {i1}:
fi:
if v[j]=-1 then
 Tright[j]:=Tright[j] union {i1}:
fi:
od:
od:

[M,[ seq([Tleft[j],Tright[j]],j=1..n)]]: 

end:



#Bni(n,i): the set of integers from  1 to 2^(n)-1 where 2^i shows up in the binary represnetaion
Bni:=proc(n,i) local j,S,s:
option remember:

if n=i then
  RETURN({seq(j,j=2^(n-1)..2^n-1)}):
fi:


S:=Bni(n-1,i):

S union {seq(s+2^(n-1),s in S)}:
end:


#vTm(v,n,j): converts a vector of length 2^n to matrix with 2^(n-j) rows and 2^j columns
vTm:=proc(v) local i,c,M:
if nops(v) mod 4<>0 then
 RETURN(FAIL):
fi:

M:=[]:

c:=0:
for i from 0 to nops(v)/4-1 do
 M:=[op(M),[op(c+1..c+4,v)]]:
c:=c+4:
od:
M:
end:



#MagicSet(n): The magic set for 2^n-1
MagicSet:=proc(n) local i:

if n=1 then
print([1]):
RETURN():
fi:

if n=2 then
 print([1,3]):
print(``):
 print([2,3]):
RETURN():
fi:

  
for i from 1 to n do
print(``):
 print( matrix(vTm(Bni(n,i)))):
print(``):
od:

end:


#Wei(v,n,P): inputs a vector of length (3^n-3)/2 indicating the weights of (3^n-3)/2 similar looking coins
#and a weighing instructions P which is a list of length n telling you to put the set of coins in P[i][1]
#on the left arm and the set of coins in P[i][2] on the right arm
#outputs the vector of length n in {0,1,-1} indicating the outcomes of the n weighings. Try
#Wei([0,1,0],2,[[{1}, {2}], [{2}, {3}]]);
#Wei([[0$9,-1,0,0],3, [[{1, 4, 6, 8}, {2, 3, 5, 7}], [{1, 7, 10, 11}, {2, 6, 8, 9}], [{2, 5, 6, 12}, {3, 8, 9, 11}]]);

Wei:=proc(v,n,P) local i, j,out1:

if not (type(n,integer) and n>=2 and nops(v)=(3^n-3)/2 and type(P,list) and nops(P)=n) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

out1:=[]:

for i from 1 to n do
if add(v[j],j in P[i][1])>add(v[j],j in P[i][2]) then
 out1:=[op(out1),1]:
elif add(v[j],j in P[i][1])=add(v[j],j in P[i][2]) then
 out1:=[op(out1),0]:
else
 out1:=[op(out1),-1]:
fi:
od:

out1:

end:


#FindFake(P,v,n): Inputs a weighing protocol P consising of the "dictionary" P[1],
#the protocol P[2], and the list of weights of the (3^n-3)/2 coins where there are all
#the same except for one that is heavier or lighther, and checks whether the weighinting
#protocol actually finds it . Try:
#P:=Coins(3,20); 
#FindFake(P,[0$9,1,0,0],3);
FindFake:=proc(P,v,n) local i,j,P1,P2,T,w:
 P1:=P[1]:
 P2:=P[2]:

 for i from 1 to nops(P1) do
  T[P1[i]]:=i:
  T[-P1[i]]:=-i:
 od:



w:=Wei(v,n,P2):


j:=T[w]:

if j>0 then
 print(` Coin `, j, `is fake and it is heavier than the rest`):
else
 print(` Coin `, -j, `is fake and it is lighter than the rest`):
fi:

end:



#IsCW(w): Is the vector w in {-1,0,1} clockwise? Try:
#IsCW([1,1,-1]);

IsCW:=proc(w) local i:
for i from 1 to nops(w)-1 while w[i]=w[i+1] do od:
if i=nops(w) then
 RETURN(FAIL):
fi:
if ( ( w[i]=-1 and w[i+1]=0) or ( w[i]=0 and w[i+1]=1) or ( w[i]=1 and w[i+1]=-1))then
 true:
else
 false:
fi:

end:



#CoinsD(n): Like Coins(n,K) but using 22-year-old Freeman Dyosn's ingenious method
CoinsD:=proc(n) local gu,M,i,Tleft,Tright,v,j,i1:
gu:=Pairs(n):

M:=[]:

for i from 1 to nops(gu) do
 if IsCW(gu[i][1]) then
  M:=[op(M),gu[i][1]]:
else
  M:=[op(M),gu[i][2]]:
 fi:
od:


for j from 1 to n do
Tleft[j]:={}:
Tright[j]:={}:
od:

for i1 from 1 to nops(M) do
v:=M[i1]:

for j from 1 to n do

if v[j]=1 then
 Tleft[j]:=Tleft[j] union {i1}:
fi:
if v[j]=-1 then
 Tright[j]:=Tright[j] union {i1}:
fi:
od:
od:

[M,[ seq([Tleft[j],Tright[j]],j=1..n)]]: 

end:




#SpellOut(M): Given the output of either Coins(n,K) or CoinsD(n), gives detailed instructions
#Try:
#SpellOut(CoinsD(3)):

SpellOut:=proc(M) local P1,P2,n,i,j,t0,w:

t0:=time():


P1:=M[1]:
P2:=M[2]:

n:=nops(P2):

print(``):
print(`How to Detect a Fake Coin if you have`, (3^n-3)/2, `identically looking coins all of the same weight except one that is heavier or lighter`):
print(`with ONLY`, n, `weighings using a BALANCE scale, and also determining whether it is heavier or lighter`):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):

print(`Label the coins with numbers from 1 to`, (3^n-3)/2 ):
print(``):

for i from 1 to nops(P2) do
 print(`In the weighing Number`, i , `place the coins in`, P2[i][1] , `on the left side and the coins in`, P2[i][2], `on the right side `):
 print(``):
od:

for i from 1 to nops(P1) do
print(``):
print(`------------------------------------`):
print(``):
 w:=P1[i]:
 for j from 1 to nops(w) do
  if w[j]=1 then
   print(`If in weighing number`, j, ` the left side was heavier`):
  elif w[j]=0 then
   print(`If in weighing number`, j, ` both sides weighed the same`):
 else
   print(`If in weighing number`, j, ` the left side was lighter`):
 fi:
 od:
print(`then the fake coin is coin number`, i, `and it is HEAVIER than the rest`):

 w:=-P1[i]:
 for j from 1 to nops(w) do
  if w[j]=1 then
   print(`If in weighing number`, j, ` the left side was heavier`):
  elif w[j]=0 then
   print(`If in weighing number`, j, ` both sides weighed the same`):
 else
   print(`If in weighing number`, j, ` the left side was lighter`):
 fi:
 od:

print(`then the fake coin is coin number`, i, `and it is LIGHTER than the rest`):

od:
print(``):
print(`-----------------------`):
print(``):
print(`This ends this article that took`, time()-t0, `seconds to produce`):
end: