#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 9
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

Help := proc(): print(`LegalMoves(a,b,i), BestMove(a,b,i), WinningTime(a,b), FS(a,b), avg(L), FR(a,b), LegalMovesGreedy(a,b,i), FG(a,b), LegalMovesL(a,b,L), LegalMovesD(a,b,i,j), FD(a,b)`): end:

# From c9.txt


LegalMoves := proc(a,b,i):
    if i = 1 then:
        if a > 0 and b > 0 then:
            return {[a-1, b+1], [a, b-1]}:
        elif a = 0 and b > 0 then:
            return {[a, b-1]}:
        elif a > 0 and b = 0 then:
            return {[a-1, b+1]}:
        else:
            return {}:
        fi:
    fi:
    if i = 2 then:
        if a > 0 then:
            return {[a-1, b]}:
        elif a = 0 and b > 0 then:
            return {[a, b-1]}:
        else:
            return {}:
        fi:
    fi:
end:

BestMove := proc(a,b,i):
    return (map(x->x[1], sort(map(x->[x, WinningTime(op(x))], LegalMoves(a,b,i)), (x,y)->x[2]<y[2])))[1]:
end:


WinningTime := proc(a,b) local p: option remember:
    if a = 0 and b = 0 then:
        return 0:
    fi:
    return 1+add(min(seq(WinningTime(p[1], p[2]), p in LegalMoves(a,b,j))), j in {1,2})/2:
end:

#############
# Problem 1 #
#############

# Expected time to win if you make the worst move possible at each stage
FS := proc(a,b) local p: option remember:
    if a = 0 and b = 0 then:
        return 0:
    fi:
    return 1+add(max(seq(FS(p[1], p[2]), p in LegalMoves(a,b,j))), j in {1,2})/2:
end:

# For each piece on point 2, if you roll a 1, it takes you 2 turns to remove that
# piece (one now, plus one later when all the pieces on point 2 are
# gone). If you roll a 2, it takes you 1 turn to remove the piece. So
# the expected number of turns to remove each piece is 3/2. Therefore,
# FS(i, 0) = 3*i/2.

# For the normal game where you try to win as fast as possible, let's
# observe what happens when you roll the die. If you get a 2, a piece
# is borne off from point 2. If you get a 1, there is a "50% chance"
# that there is a piece on point 1, which is borne off, and a 50%
# chance that there is not, in which case a piece is transferred to
# point 1. So you bear off an average of 3/4 of a piece per move. This
# means that the expected time to bear off all the pieces is 4*i/3, to
# within 1 move.

# So the limit is (3/2)/(4/3) = 9/8.

#############
# Problem 2 #
#############

# By the above discussion, c1 = 4/3. Then a simple experiment shows
# that c2 = 2/9.

#############
# Problem 3 #
#############

avg := proc(L) local i:
    return add(i, i in L)/nops(L):
end:

FR := proc(a,b) local p: option remember:
    if a = 0 and b = 0 then:
        return 0:
    fi:
    return 1+add(avg([seq(FR(p[1], p[2]), p in LegalMoves(a,b,j))]), j in {1,2})/2:
end:

# The limit appears to be 1. This makes sense because most stupid
# moves, where we move from point 2 to point 1 instead of bearing off,
# don't cost us, since we just get to bear off that piece with a 1
# anyway. The number of those stupid moves that do cost us in the end
# should grow like O(sqrt(i)).

#############
# Problem 4 #
#############

# We could just put FG = F, of course, but that seems like cheating.

LegalMovesGreedy := proc(a,b,i):
    if i = 1 then:
        if a > 0 and b > 0 then:
            return {[a, b-1]}:
        elif a = 0 and b > 0 then:
            return {[a, b-1]}:
        elif a > 0 and b = 0 then:
            return {[a-1, b+1]}:
        else:
            return {}:
        fi:
    fi:
    if i = 2 then:
        if a > 0 then:
            return {[a-1, b]}:
        elif a = 0 and b > 0 then:
            return {[a, b-1]}:
        else:
            return {}:
        fi:
    fi:
end:

FG := proc(a,b) local p: option remember:
    if a = 0 and b = 0 then:
        return 0:
    fi:
    return 1+add(min(seq(FG(p[1], p[2]), p in LegalMovesGreedy(a,b,j))), j in {1,2})/2:
end:

# Of course, the limit is 1.

#############
# Problem 5 #
#############

# Make nops(L) legal moves of type L[1], L[2], ...
LegalMovesL := proc(a,b,L):
    if nops(L) = 0 then:
        return {[a,b]}:
    elif a = 0 and b = 0 then:
        return {[0,0]}:
    else:
        return map(x->op(LegalMovesL(x[1], x[2], subsop(1=NULL, L))), LegalMoves(a,b,L[1])):
    fi:
end:

LegalMovesD := proc(a,b,i,j) local m,n:
    if i = j then:
        return LegalMovesL(a,b, [i,i,i,i]):
    fi:
    if i <> j then:
        return apply(`union`, seq(LegalMovesL(a,b,m), m in {[i,j], [j,i]})):
    fi:
end:

FD := proc(a,b) local p: option remember:
    if a = 0 and b = 0 then:
        return 0:
    fi:
    return 1+add(min(seq(FD(p[1], p[2]), p in LegalMovesD(a,b,j[1], j[2]))), j in {[1,1], [1,2], [2,1], [2,2]})/4:
end:

# It appears that FD(n,0) -> 4/9. This makes sense because you get 9/4
# pips per roll, on average.

#############
# Problem 6 #
#############

# Definition: A rooted identity matched tree is a tree with a
# single distinguished vertex (the root), with the following
# properties: (1) there is no nonidentity isomorphism that preserves
# the root, and (2) there exists a complete matching on the vertices
# that is a subgraph of the tree.

# Lemma 1 (in Simion, '91): By deleting the root and the vertex matched
# to it, a rooted identity matched tree with 2n vertices is decomposed
# into two forests of rooted identity matched trees, having a total of
# 2(n-1) vertices, with the
# additional property that no two trees in a single forest are
# isomorphic. One forest consists of all the rooted trees with roots
# reviously adjacent to the root of the original tree. The other
# forest consists of all the rooted trees with roots previously
# adjacent to the vertex matched to the root of the original tree.

# Lemma 2: If a tree has a complete matching, that matching is unique.

# Proof: Each edge connected to a leaf must be in the matching. Delete
# all matched vertices and find the rest of the matching on this
# smaller tree. By induction, it is unique, so the entire matching is
# unique.

# Lemma 3: By deleting the starting position, a game with n positions
# can be decomposed into two collections of games having a total of
# (n-1) positions, with the property that no game appears more than
# once in each collection. One collection consists of the left options
# of the original game, and the other collection consists of the right
# options of the original game.

# This lemma is obvious from the definition of a game.

# Theorem: The number of games with n positions is equal to the number
# of rooted identity matched trees with 2n vertices.

# Proof: Induction on n. When n = 1 the theorem is trivial since there
# is exactly 1 such tree and 1 such game.

# Suppose the theorem is true for 1, 2, ..., k-1, and further suppose
# we have bijections between the sets of games of size i and of rooted
# identity matched trees with 2i vertices. We will build a bijection
# between the games of size k and the rooted identity matched trees
# with 2k vertices.

# To go from a game to a tree, convert all the left options to rooted
# identity matched trees and all the right options to rooted identity
# matched trees. Create new vertices u and v, and attach all the trees
# corresponding to left options to u and the trees corresponding to
# right options to v. Put an edge between u and v, and make u the
# root. The edge uv can be added to the union of matchings on the
# subtrees, so the new tree is matched. By Lemma 3, no two of the
# left options were isomorphic, so none of the subtrees attached to u
# are isomorphic. Similarly, none of the subtrees attached to v are
# isomoprhic. So the new tree is an identity tree. We now
# have a rooted identity matched tree.

# To go from a tree to a game, let u be the root and let v be the
# vertex adjacent to the root by the unique matching (recall Lemma
# 2). Convert all the subtrees adjacent to u to games, and let these
# be the left options. Convert all the subtrees adjacent to v to
# games, and let these be the right options. By Lemma 1, no two of the
# subtrees attached to u were isomorphic, so none of the games left
# options are equal. Similarly, none of the right options are
# equal. Therefore, we now have a game.

# Any donations to OEIS should be made anonymously since I do not feel
# like this proof was original enough to warrant an award.