###################################################################### ## RiverCrossing.txt: Save this file as RiverCrossing.txt to use it,# # stay in the # ## same directory, get into Maple (by typing: maple ) # #then type: read `RiverCrossing.txt`: # ## Then follow the instructions given there # ## # ## Written by George Spahn and Doron Zeilberger, Rutgers University ,# ## DoronZeil@gmail.com . # ###################################################################### with(combinat): Digits:=100: print(`First Written: Oct. 2022: tested for Maple 20 `): print(): print(`This is RiverCrossing.txt, one of the Maple packages`): print(`accompanying George Spahn and Doron Zeilberger's article: `): print(` Variations on the Missionaries and Cannibals Puzzle `): print(`-------------------------------`): print(`-------------------------------`): print(): print(`The most current version is available on WWW at:`): print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/RiverCrossing.txt .`): print(`Please report all bugs to: DoronZeil at gmail dot com .`): print(): print(`-------------------------------`): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(`-------------------------------`): print(`For a list of the supporting functions type: ezra1();`): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(): print(`-------------------------------`): print(`-------------------------------`): print(`For a list of the STORY functions type: ezraS();`): print(`For help with a specific procedure, type "ezra(procedure_name);"`): print(): print(`-------------------------------`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): ezraS:=proc() if args=NULL then print(` The STORY procedures are: `): print(` Paper, RCnuV, SeqrGFs `): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(` Bn, CT, Deci, IGmc, Trim `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(` RiverCrossing.txt: A Maple package for solving genral River Crossing Problems, and for finding the number of solutions and detecting patterns.`): print(`The main procedures are : GuessRGF, LEGf, LEGmc, RC, RCnu, Seqr, SOLS `): elif nargs=1 and args[1]=Bn then print(`Bn(n): The n dimensional discrete unit cube. Try: `): print(`Bn(5);`): elif nargs=1 and args[1]=CT then print(`CT(f,var): The constant term of the polynomial f in the list of variables var. Try:`): print(`CT((x+y+1/x+1/y)^10,[x,y]):`): elif nargs=1 and args[1]=Deci then print(`Deci(mu): converts a monomial to a path.`): elif nargs=1 and args[1]=IGmc then print(`IGmc(S,M,C,d): Given a state S decides whether it is a good state. Try:`): print(`IGmc([3,3],3,3,1);`): elif nargs=1 and args[1]=GuessRGF then print(`GuessRGF(L,x): Guesses a rational generating function for the sequence L that starts at n=0. Try:`): print(`GuessRGF(Seqr(5,3,1,14),x);`): elif nargs=1 and args[1]=LEGf then print(`LEGf(): The vertices and edges of the [Farmer, Cabbage, Sheep, Wolf] puzzle. Type:`): print(`LEGf();`): elif nargs=1 and args[1]=LEGmc then print(`LEGmc(M,C,B,d): inputs posiitve integers M, C, B,d and finds all legal vertices and edges. Try:`): print(`LEGmc(3,3,2,0);`): elif nargs=1 and args[1]=Paper then print(`Paper(MaxR,MaxB,Maxd,K,x): Inputs positive integers MaxR, MaxB, Maxd, K, and a variable x and outputs a paper with conjectured generating functions, in terms of rational funcions of x`): print(`For Sum(a(r+i,i,B,d)*x^i,i=0..infinity), for r from d to MaxR, B from 2 to MaxB, and d from 0 to Maxd. K is a guessing parameter. It may not big enough to do everything. Try:`): print(`Paper(5,3,1,40,x);`): elif nargs=1 and args[1]=RC then print(`RC(INI,LEG,B): Given an initial state INI, and a pair LEG=[BankOccupancy,BoatOccupancy] and a variable x, tries to find all solutions`): print(`(in symbolic form) of starting with the initial state in the first bank and ending with the empty state at the first bank`): print(`x[i,b1] means: put b1 at the i-th forward crossing and x[-i,b1] means : put b1 at the i-th back crossing. `): print(`It also returns the number of crossings (always odd, of course). Try:`): print(`RC([3,3],LEGmc(3,3,2,0),B);`): elif nargs=1 and args[1]=RCnu then print(`RCnu(INI,LEG): Given an initial state INI, and a pair LEG=[BankOccupancy,BoatOccupancy] and a variable x, finds The NUMBER of solutions`): print(`starting with the initial state in the first bank and ending with the empty state at the first bank`): print(`It returns the number of crossings, and the number of solutions (paths). Try:`): print(`RCnu([3,3],LEGmc(3,3,2,0));`): elif nargs=1 and args[1]=RCnuV then print(`RCnuV(INI,LEG): a verbose form of RCnu(INI,LEG), (q.v.). Try:`): print(`RCnuV([3,3],LEGmc(3,3,2,0));`): elif nargs=1 and args[1]=Seqr then print(`Seqr(r,B,d,K): The sequence`): print(`#[seq(RCnu([i+r,i],LEGmc(i+r,i,B,d))[2],i=1..K)]`): print(` In other words the sequence whose i-th entry is the number of ways`): print(`i+r missionaries and i cannibals can cross a river with boat-size B and safey margin d. Try:`): print(`Seqr(5,3,1,10);`): print(`Seqr(0,2,0,6);`): elif nargs=1 and args[1]=SeqrGFs then print(`SeqrGFs(r,B,d,K,x): Tells the story of the generating function for the sequence enumerating the number of ways i+r missionaries and i cannibals can cross a river`): print(`with boat size B and safety margin d. K is a guessing parameter and x is the variable of the generating function.Try:`): print(`SeqrGFs(5,3,1,20,x);`): elif nargs=1 and args[1]=SOLS then print(`SOLS(INI,LEG): All the solutions of the river-crossing puzzle LEG starting with initial state INI. Try:`): print(`SOLS([3,3],LEGmc(3,3,2,0));`): elif nargs=1 and args[1]=Trim then print(`Trim(f,var,LE): Given a polynomial f in the list of variables var and a set LE of allowed exponents F, kicks out all monomials whose exponents do not`): print(`belong to F. Try:`): print(`Trim(m^3*c^3,[m,c],{[3,3],[2,2]});`): print(``): else print(`There is no such thing as`, args): fi: end: with(combinat): #IGmc(S,M,C,d): Given a state S decides whether it is a good state. Try: #IGmc([3,3],3,3,1); IGmc:=proc(S,M,C,d) : if not (S[1]>=0 and S[1]<=M and S[2]>=0 and S[2]<=C) then RETURN(false): fi: if S[1]>0 and S[2]>0 and S[1]-S[2]0 and C-S[2]>0 and (M-S[1])-(C-S[2])0 or e2>0) and not (e1>0 and e2>0 and e1-e20 then RETURN(2*k-1,lu): else f:=expand(f*add(B[-k,bo]*mul(x[i1]^bo[i1],i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): f:=expand(f*add(B[k+1,bo]/mul(x[i1]^bo[i1],i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): fi: od: FAIL: end: #RCnu(INI,LEG): Given an initial state INI, and a pair LEG=[BankOccupancy,BoatOccupancy] and a variable x, finds The NUMBER of solutions #starting with the initial state in the first bank and ending with the empty state at the first bank #It returns the number of crossings, and the number of solutions (paths). Try: #RCnu([3,3],LEGmc(3,3,2,0),B); RCnu:=proc(INI,LEG) local i,BA,BO,f,x,bo,i1,k,lu: BA:=LEG[1]: BO:=LEG[2]: f:=mul(x[i]^INI[i],i=1..nops(INI)): f:=expand(f*add(mul(x[i1]^(-bo[i1]),i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): for k from 1 to nops(BA) do lu:=CT(f,[seq(x[i1],i1=1..nops(INI))]): if lu<>0 then RETURN(2*k-1,lu): else f:=expand(f*add(mul(x[i1]^bo[i1],i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): f:=expand(f*add(mul(x[i1]^(-bo[i1]),i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): fi: od: [FAIL,0]: end: #RCnuV(INI,LEG): Given an initial state INI, and a pair LEG=[BankOccupancy,BoatOccupancy] and a variable x, finds The NUMBER of solutions #starting with the initial state in the first bank and ending with the empty state at the first bank #It returns the number of crossings, and the number of solutions (paths). Try: #RCnuV([3,3],LEGmc(3,3,2,0),B); RCnuV:=proc(INI,LEG) local i,BA,BO,f,x,bo,i1,k,lu,LI1,LI2: BA:=LEG[1]: BO:=LEG[2]: f:=mul(x[i]^INI[i],i=1..nops(INI)): LI1:=[f]: f:=expand(f*add(mul(x[i1]^(-bo[i1]),i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): LI2:=[f]: print(`the number of states is`, nops(BA)): for k from 1 to nops(BA) do lu:=CT(f,[seq(x[i1],i1=1..nops(INI))]): if lu<>0 then RETURN(2*k-1,lu,[LI1,LI2]): else f:=expand(f*add(mul(x[i1]^bo[i1],i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): LI1:=[op(LI1),f]: f:=expand(f*add(mul(x[i1]^(-bo[i1]),i1=1..nops(bo)),bo in BO)): f:=Trim(f,[seq(x[i1],i1=1..nops(INI))],BA): LI2:=[op(LI2),f]: fi: od: [[LI1,LI2],0]: end: #Deci(mu): converts a monomial to a path. Deci:=proc(mu1) local i,T,k: if not type(mu1,`*`) then RETURN(FAIL): fi: for i from 1 to nops(mu1) do T[op(1,op(i,mu1))]:=op(2,op(i,mu1)): od: k:=(nops(mu1)-1)/2: [seq(op([-T[i],T[-i]]),i=1..k),-T[k+1]]: end: #SOLS(INI,LEG): All the solutions of the river-crossing puzzle LEG starting with initial state INI. Try: #SOLS([3,3],LEGmc(3,3,2,0)); SOLS:=proc(INI,LEG) local B,gu,lu,i: gu:=expand(RC(INI,LEG,B)[2]): if not type(gu,`+`) then lu:=Deci(gu): if lu=FAIL then RETURN(FAIL): else RETURN({Deci(gu)}): fi: fi: {seq(Deci(op(i,gu)),i=1..nops(gu))}: end: #Seqr(r,B,d,K): The sequence #[seq(RCnu([i+r,i],LEGmc(i+r,i,B,d))[2],i=1..K)] # In other words the sequence whose i-th entry is the number of ways #i+r missionaries and i cannibals can cross a river with boat-size B and safey margin d. Try: #Seqr(5,3,1,10); #Seqr(0,2,0,6); Seqr:=proc(r,B,d,K) local i: option remember: [seq(RCnu([i+r,i],LEGmc(i+r,i,B,d))[2],i=0..K)]: end: #GuessRec1(L,d): inputs a sequence L and tries to guess #a recurrence operator with constant cofficients of order d #satisfying it. It returns the initial d values and the operator # as a list. For example try: #GuessRec1([1,1,1,1,1,1],1); GuessRec1:=proc(L,d) local eq,var,a,i,n: if nops(L)<=2*d+2 then print(`The list must be of size >=`, 2*d+3 ): RETURN(FAIL): fi: var:={seq(a[i],i=1..d)}: eq:={seq(L[n]-add(a[i]*L[n-i],i=1..d),n=d+1..nops(L))}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): else RETURN([[op(1..d,L)],[seq(subs(var,a[i]),i=1..d)]]): fi: end: #GuessRGF(L,x): Guesses a rational generating function for the sequence L that starts at n=0. Try: #GuessRGF(Seqr(5,3,1,14),x); GuessRGF:=proc(L,x) local D1, d,gu,Den1,Num1,f,f1,i,i1: if {op(trunc(nops(L)/2)..nops(L),L)}={0} then RETURN(add(L[i+1]*x^i,i=0..nops(L)-1)): fi: D1:= trunc((nops(L)-6)/2): for d from 1 to D1 do gu:=GuessRec1([op(nops(L)-2*d-6..nops(L),L)],d): if gu<>FAIL then gu:=gu[2]: Den1:=1-add(gu[i1]*x^i1,i1=1..d): Num1:=expand(add(L[i+1]*x^i,i=0..nops(L)-1)*Den1): Num1:=expand(Num1 -add(coeff(Num1,x,i)*x^i,i=nops(L)-1..degree(Num1,x))): f:=Num1/Den1: f1:=taylor(f,x=0,nops(L)+2): if {seq(coeff(f1,x,i)-L[i+1],i=0..nops(L)-1)}<>{0} then RETURN(FAIL): else RETURN(factor(f)): fi: fi: od: FAIL: end: #SeqrGFs(r,B,d,K,x): Tells the story of the generating function for the sequence enumerating the number of ways i+r missionaries and i cannibals can cross a river #with boat size B and safety margin d. K is a guessing parameter and x is the variable of the generating function.Try: #SeqrGFs(5,3,1,20,x); SeqrGFs:=proc(r,B,d,K,x) local f,a,i,gu: gu:=Seqr(r,B,d,K): f:=GuessRGF(gu,x): if f=FAIL or f=0 or f=1 then RETURN(FAIL): fi: print(``): print(`Proposition:`): print(`Let a(i) be the number of ways that`, i+r, `missionaries and `,i, `cannibals can cross a river safely where the boat can have at most`, B, `passendgers and whenevr both cannibals are missionaries are present`): print(`The number of missioanries should exceed the number of canniabls by at least`, d): print(``): print(`Then the ordinary generating function of the sequence a(i) is given by the following rational function of x`): print(``): print(Sum(a(i)*x^i,i=0..infinity)=f): print(``): print(`and in Maple notation `): print(``): lprint(f): print(``): end: #SeqrGFs1(r,B,d,K,x,C): Tells the story of the generating function for the sequence enumerating the number of ways i+r missionaries and i cannibals can cross a river #with boat size B and safety margin d. K is a guessing parameter and x is the variable of the generating function.Try: #SeqrGFs1(5,3,1,20,x); SeqrGFs1:=proc(r,B,d,K,x,C) local f,a,i,gu,F: gu:=Seqr(r,B,d,K): f:=GuessRGF(gu,x): if f=FAIL or f=0 or f=1 then RETURN(FAIL): fi: print(cat(Proposition,` `, C)): print(F(r,B,d,x)=f): print(``): print(`and in Maple notation `): print(``): lprint(f): print(``): end: #Paper(MaxR,MaxB,Maxd,K,x): Inputs positive integers MaxR, MaxB, Maxd, K, and a variable x and outputs a paper with conjectured generating functions, in terms of rational funcions of x`): #For Sum(a(r+i,i,B,d)*x^i,i=0..infinity), for r from d to MaxR, B from 2 to MaxB, and d from 0 to Maxd. K is a guessing parameter. Try: #Paper(5,3,1,40,x); Paper:=proc(MaxR, MaxB, Maxd,K,x) local F,i,C,r,B,d,f,t0: t0:=time(): print(`Enumerating the Number of Ways Missionaries and Cannibals can cross the river for many Infinite Families of Problems where the Boat Size and Safety Margin are fixed and the Excess of Missionaries to Canniabls is also fixed`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(` M missionaries and C cannibals have to cross a river. They have a boat that can have at most B passengers, and at no time, on either bank of the river, and in the boat should there be a scenario where `): print(`there are both missionaries and cannibals present, the excess of the number of missionaries to the number cannibals MUST BE AT LEAST d`): print(``): print(`Let a(M,C,B,d) be the number of ways of crossing safely`): print(``): print(`In this paper we will conjecture rational function expressions for the generating functions`): print(``): print(F(r,B,d,x) =Sum(a(r+i,i,B,d)*x^i,i=0..infinity) ): print(``): C:=0: for d from 0 to Maxd do print(``): print(`Doing Safety Margin`, d): print(``): print(`--------------------------------------------`): print(``): for B from 2 to MaxB do print(``): print(`--------------------------------------------`): print(``): print(`doing Boat size`, B): print(``): for r from d to MaxR do f:=GuessRGF(Seqr(r,B,d,K),x): if f<>FAIL and f<>0 and f<>1 then C:=C+1: print(``): print(cat(` Proposition ` ,` `, C)): print(``): print(F(r,B,d,x)=f): print(``): print(`and in Maple notation `): print(``): lprint(f): fi: od: od: od: print(``): print(`This ends this paper that took`, time()-t0, `seconds to generate `): print(``): end: