#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)
__