#Nathan Fox #Homework 3 #I give permission for this work to be posted online #Read C3.txt for necessary procedures read(`C3.txt`): #Help procedure Help:=proc() : print(` F(k,N) , Wyt(a,b) , SeqA(n) , kWyt(Li) `): end: #Inputs positive integers k and N and #returns all the triples [k,a,b] such that #[k,a,b] is a LOSING position with 0<=a<=b<=N. #The return value is a list of the triples F:=proc(k,N) local a,b,L: L:=[]: for a from 0 to N do for b from a to N do if Nim3([k,a,b])=0 then L:=[op(L), [k,a,b]]: fi: od: od: L: end: ##Guesses for set F(k,infinity) ##for k=0,1,2,3,4, .. up to k=10. ##(assuming we can talk about infinity in this way) #0: All triples of the form [0,m,m] #1: All triples of the form [1,2m,2m+1] #2: All triples of the form [2,4m,4m+2] or [2,4m+1,4m+3] #3: All triples of the form [3,4m,4m+3] or [3,4m+1,4m+2] #4: All triples of the form [4,8m,8m+4], [4,8m+1,8m+5], # [4,8m+2,8m+6], or [4,8m+3,8m+7] #5: All triples of the form [5,8m,8m+5], [5,8m+1,8m+4], # [5,8m+2,8m+7], or [5,8m+3,8m+6] #6: All triples of the form [6,8m,8m+6], [6,8m+1,8m+7], # [6,8m+2,8m+4], or [6,8m+3,8m+5] #7: All triples of the form [7,8m,8m+7], [7,8m+1,8m+6], # [7,8m+2,8m+5], or [7,8m+3,8m+4] #8: All triples of the form [8,16m,16m+8], [8,16m+1,16m+9], # [8,16m+2,16m+10], [8,16m+3,16m+11], # [8,16m+4,16m+12], [8,16m+5,16m+13], # [8,16m+6,16m+14], or [8,16m+7,16m+15] #9: All triples of the form [9,16m,16m+9], [9,16m+1,16m+8], # [9,16m+2,16m+11], [9,16m+3,16m+10], # [9,16m+4,16m+13], [9,16m+5,16m+12], # [9,16m+6,16m+15], or [9,16m+7,16m+14] #10: All triples of the form [10,16m,16m+10], [10,16m+1,16m+11], # [10,16m+2,16m+8], [10,16m+3,16m+9], # [10,16m+4,16m+14], [10,16m+5,16m+15], # [10,16m+6,16m+12], or [10,16m+7,16m+13] #Inputs 0(1) according to whether [a,b] is a #losing (winning) position in the Wythoff game #The Wythoff game is like 2-pile Nim #with the extra move that one can remove #the SAME number of pennies from BOTH piles. Wyt:=proc(a,b) local i: option remember: 1-mul(Wyt(a-i,b),i=1..a)* mul(Wyt(a,b-i),i=1..b)* mul(Wyt(a-i,b-i),i=1..min(a,b)): end: ##Proof that for every non-negative integer n, ##there is exacty one Wythoff Losing position ##[a,b] with b=a+n. #Uniqueness: Assume for a contradiction that there are #two such positions for some n. Let's call them [a,b] and #[a',b']. Without loss of generality, a'>a (so then b'>b, since #a'-a=b'-b). The player to move in position [a',b'] #could remove a'-a pennies from each pile, leaving [a,b] #for the other player. Since the player to move was able #to leave a losing position, [a',b'] could not have been #a losing position. This is a contradiction, so it must #be that at most one of [a,b] or [a',b'] is losing. #Existence: The proof is by induction on n. We see that #[0,0] is losing, so there is a losing position for n=0. #Now, assume that there exists a losing position all m