# Matthew Russell # Experimental Math # Homework 8 # I give permission to post this ##################################################################################### # Study carefully the simplified NuGames1(n) # procedure in the revised version of C8.txt , # and convince yourself that it is OK. ##################################################################################### # Check empirically procedure RollLD(L), # by doing # add(x[RollLD([1,1,1,1,1,1])],i=1..6000); # add(x[RollLD([1,2,3])],i=1..6000); # and quite a few other L. ##################################################################################### # Test the procedure # RandGame1(n): # (that I added after class), by doing # add(x[RandGame1(10)],i=1..NuGames1(10)*100); # and see if you get roughly 100 for each of the thinkless games of size 10. ##################################################################################### # Write a (recursive) program # that inputs a list in the alphabet {B,T,F} # where B denotes a Blank square, T denotes Toad, and F denotes Frogs, # and outputs the kind of Frogs and Toads game it is # ("Positive", "Negative", "Fuzzy", or "Zero"). FTWhatType:=proc(L) local a,b: option remember: a:=FTCanLeftWin(L): b:=FTCanRightWin(L): if a and b then return "Fuzzy": fi: if a and not b then return "Positive": fi: if not a and b then return "Negative": fi: if not a and not b then return "Zero": fi: end: FTCanLeftWin:=proc(L) local A, Opt: option remember: Opt:=FT(L)[1]: return evalb(true in {seq(not FTCanRightWin(A), A in Opt)}): end: FTCanRightWin:=proc(L) local A, Opt: option remember: Opt:=FT(L)[2]: return evalb(true in {seq(not FTCanLeftWin(A), A in Opt)}): end: FT:=proc(L) option remember: return [FTMoves(L,"Left"),FTMoves(L,"Right")]: end: FTMoves:=proc(L,M) local Poss, i: option remember: Poss:={}: if M="Left" then for i from 1 to nops(L)-1 do if L[i]=T and L[i+1]=B then Poss:=Poss union {[op(1..i-1,L),B,T,op(i+2..nops(L),L)]}: fi: od: for i from 1 to nops(L)-2 do if L[i]=T and L[i+1]=F and L[i+2]=B then Poss:=Poss union {[op(1..i-1,L),B,F,T,op(i+3..nops(L),L)]}: fi: od: fi: if M="Right" then for i from 2 to nops(L) do if L[i-1]=B and L[i]=F then Poss:=Poss union {[op(1..i-2,L),F,B,op(i+1..nops(L),L)]}: fi: od: for i from 3 to nops(L) do if L[i-2]=B and L[i-1]=T and L[i]=F then Poss:=Poss union {[op(1..i-3,L),F,T,B,op(i+1..nops(L),L)]}: fi: od: fi: return Poss: end: # Let a0(n), ap(n), am(n), af(n) # be the number of Frogs and Toads games of board-length n # (there are of course 3^n of them altogher), # that are zero, positive, negative, and fuzzy respectively. # Is any of them in Sloane? FTBoards:=proc(n) option remember: if n=0 then return {[]}: fi: S:={}: for f in FTBoards(n-1) do S:=S union {[op(f),B],[op(f),F],[op(f),T]}: od: end: a0:=proc(n) counter:=0: for f in FTBoards(n) do if FTWhatType(f)="Zero" then counter:=counter+1: fi: od: return counter: end: ap:=proc(n) counter:=0: for f in FTBoards(n) do if FTWhatType(f)="Positive" then counter:=counter+1: fi: od: return counter: end: an:=proc(n) counter:=0: for f in FTBoards(n) do if FTWhatType(f)="Negative" then counter:=counter+1: fi: od: return counter: end: af:=proc(n) counter:=0: for f in FTBoards(n) do if FTWhatType(f)="Fuzzy" then counter:=counter+1: fi: od: return counter: end: # a0: 3, 7, 16, 37, 85, 199, 470, 1122 # Not in OEIS # ap: 0, 1, 5, 20, 71, 238, 775, 2468 # Not in OEIS # an: 0, 1, 5, 20, 71, 238, 775, 2468 # Not in OEIS # af: 0, 0, 1, 4, 16, 54, 167, 503 # Not in OEIS ##################################################################################### # A thinkless game of size n is either # [{},{g1}] for some thinkless game g1 of size n-1, # or [{g1},{}], # or has the form [{g1},{g2}] # for some thinkless games g1 and g2 # with size(g1)+size(g2)=n-1. # That's how we constructed recursively Games1(n). # Define a level-2 game as a game # where at any instance both players # have either no option, exactly one option, or exactly two options. # Write a (recursive) procedure, # G2(n), # that inputs a positive integer n and outputs the set of all level-2 games of size n. # Hint: the format of a level-2 game is one of the following # [{},{}] (only if n=1) # [{g1},{}], [{},{g1}], [{},{g1,g2}], [{g1,g2},{}], [{g1},{g2}], # [{g1},{g2,g3}], [{g2,g3},{g1}],[{g1,g2},{g3,g4}] # where g1,g2, etc. are level-2 games whose sizes add up to n. G2:=proc(n) local Games, S, S1, S2, S3, S4, m, p, q: option remember: if n=0 then return {}: fi: if n=1 then return {[{},{}]}: fi: Games:={}: S:=G2(n-1): Games:=Games union {seq([{g1},{}],g1 in S)} union {seq([{},{g1}],g1 in S)}: for m from 1 to n-2 do S1:=G2(m): S2:=G2(n-m-1): Games:=Games union {seq(seq([{g1},{g2}], g1 in S1), g2 in S2)} union {seq(seq([{g1,g2},{}], g1 in S1 minus {g2}), g2 in S2)} union {seq(seq([{},{g1,g2}], g1 in S1 minus {g2}), g2 in S2)}: od: for m from 1 to n-3 do for p from 1 to n-m-2 do S1:=G2(m): S2:=G2(p): S3:=G2(n-m-p-1): Games:=Games union {seq(seq(seq([{g1,g2},{g3}], g3 in S3), g2 in S2 minus {g1}), g1 in S1)} union {seq(seq(seq([{g3},{g1,g2}], g3 in S3), g2 in S2 minus {g1}), g1 in S1)}: od: od: for m from 1 to n-4 do for p from 1 to n-m-3 do for q from 1 to n-m-p-2 do S1:=G2(m): S2:=G2(p): S3:=G2(q): S4:=G2(n-m-p-q-1): Games:=Games union {seq(seq(seq(seq([{g1,g2},{g3,g4}], g4 in S4 minus {g3}), g3 in S3), g2 in S2 minus {g1}), g1 in S1)}: od: od: od: return Games: end: ##################################################################################### # We saw in class that the sequence # of number of zero thinkless games is in Sloane, # but with a different meaning. # Prove that they are the same for all n. ##################################################################################### # We saw in class that the sequence # of number of fuzzy thinkless games is in Sloane, # but with a different meaning. # Prove that they are the same for all n.