#OK to post homework #Jason Saied, March 31, 2019, Assignment 16 Help:=proc(): print(`GuessWho(x,N), ProfileMod(n,k), ABTmod(N,k), BT(n), OT(n)`): end: #####Problem 1 #If there are 2^k numbers in an ordered list, it should actually take k questions to figure out which one your opponent is thinking of. #Also, it's N=2^k-1 that gives us a list with 2^k numbers, #so really we want N=2^k-1 to return k. This code will do that! GuessWho:=proc(x,N) local co, L, U, U0: #the case where N=0 is degenerate: no questions needed if N=0 then return 0: fi: L:=0: U:=trunc(N/2): co:=0: while L=0. ###Problem 4 #Note that the problem statement as written is false. The number of vertices of [T1, ..., Tk] is actually 1 plus the numbers of vertices of each Ti. The definition in the statement doesn't make sense, since [[[...]]] would be said to have 1 vertex. OT:=proc(n) local S,a,T1, T2: option remember: if n<=0 then return {}: fi: if n=1 then return {[]}: fi: S:={}: #let a be the number of vertices in the tree we are adding on for a from 1 to n-1 do #take a tree with n-a vertices #take another tree with a vertices #put them together into one tree (putting the a one as a subtree under the n-a one's root node) for T1 in OT(n-a) do for T2 in OT(a) do S:=S union {[op(T1), T2]}: od: od: od: return S: end: #Interestingly, we again have the recursion for the Catalan numbers. If T(n):=nops(OT(n)), we have T(1)=1, and for n>1 we have T(n)=add(T(a)*T(n-a), a=1..n-1). #So with the notation from Problem 3, C(n)=B(n+1)=T(n+1). Then we have closed form T(n+1)=B(n+1)=C(n)=binomial(2n,n)/(n+1)