2050.sagews

types = ['w', 'a', 'b', 'm', 'n']
n = {'w': 1, 'a': 1, 'b': 1, 'm': 2, 'n': 2}
o = {'w': 0, 'a': 1, 'b': 2, 'm': 1, 'n': 2}
z = {'w': 3, 'a': 3, 'b': 3, 'm': 5, 'n': 5}
def bonus(x, y):
    s = set([x, y])
    if (s==set(['a', 'b'])): return 1/10
    if (s==set(['a'])): return 2/10
    if (s==set(['w', 'b'])): return 13/30
    if (s==set(['w', 'a'])): return 8/15
    if (s==set(['w', 'm'])): return 1/12
    return 0
    
print("Calculations for Claim 15:")
for L in types:
    for R in types:
        if (types.index(L)<=types.index(R) and not (L=='w' and R=='w')):
            for x in range(2, 120):
                value = (n[L]+x+n[R])^2/(n[L]*o[L]+2*(3*(n[L]+x+n[R])-6)+n[R]*o[R]) - n[L]/(o[L]+n[L]+n[R]-1) - n[R]/(o[R]+n[L]+n[R]-1) + bonus(L, R) - 2/5*floor(x/3);
                if (value<0):
                    msg = "Case "+L+"-"+R+", x="+str(x)+": negative ("+str(value)+") when w="+str(floor(x/3))
                    if (value+2/5 >= 0): msg += " but ok for any smaller w"
                    print(msg)

Calculations for Claim 15: Case w-a, x=3: negative (-29/570) when w=1 but ok for any smaller w Case w-a, x=6: negative (-41/1110) when w=2 but ok for any smaller w Case w-b, x=3: negative (-1/20) when w=1 but ok for any smaller w Case w-b, x=6: negative (-3/190) when w=2 but ok for any smaller w Case w-m, x=3: negative (-77/780) when w=1 but ok for any smaller w Case w-m, x=6: negative (-7/165) when w=2 but ok for any smaller w Case w-n, x=3: negative (-4/35) when w=1 but ok for any smaller w Case w-n, x=6: negative (-9/230) when w=2 but ok for any smaller w Case a-m, x=3: negative (-1/15) when w=1 but ok for any smaller w Case b-m, x=3: negative (-13/420) when w=1 but ok for any smaller w

print("Calculations for Claim 18:")
msg=""
for L in types:
    for R in types:
        if (types.index(L)<=types.index(R) and not (L=='w' and R=='w')):
            x=6
            value = n[L]^2/(n[L]*(o[L]+n[L]-1)+z[L])+x^2/(z[L]+2*(3*x-6)+z[R])+n[R]^2/(n[R]*(o[R]+n[R]-1)+z[R]) -  n[L]/(o[L]+n[L]+n[R]-1) - n[R]/(o[R]+n[L]+n[R]-1) + bonus(L, R) - 2/5*floor(x/3)
            msg += str(value)+" "
            if (value<0): msg += "negative! "
print(msg)

Calculations for Claim 18: 1/60 1/30 7/360 29/1320 1/10 7/60 7/360 139/1320 2/15 19/360 61/440 113/765 2809/16830 174/935

print("Calculations by Bellman-Ford algorithm, Theorem 26:")
def S(i, j):
    if (set([i, j])==set([2, 3])): return 5
    else: return i*j
def C(a, b, c):
    E = S(a, b)+b*(b-1)+S(b, c)
    return (E % b)/ceil(E/b) + (b - E % b)/floor(E/b)
V = ['s', [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], 't']
from types import ListType
def cost(u, v):
    if (u=='s' and isinstance(v, ListType) and v[0]==1): return 1/v[1]
    if (isinstance(u, ListType) and isinstance(v, ListType) and u[1]==v[0]): return C(u[0], u[1], v[1])-2/5
    if (isinstance(u, ListType) and u[1]==1 and v=='t'): return 1/u[0]-2/5
    return infinity
def h(v): # hash tool to make code nicer
    if isinstance(v, ListType): return str(v[0])+str(v[1])
    return v 

# Bellman-Ford starts here    
dist = {}
for v in V: dist[h(v)] = infinity
dist[h('s')] = 0
for i in range(len(V)+1):
    newdist = {}
    for v in V: newdist[h(v)] = dist[h(v)]
    for u in V:
            for v in V: newdist[h(v)] = min(newdist[h(v)], dist[h(u)]+cost(u, v))
    if (dist==newdist):
        print("Distances stabilized, no negative cycles")
        break
    dist=newdist
print("Minimum s-t distance is "+str(dist[h('t')]))

Calculations by Bellman-Ford algorithm, Theorem 26: Distances stabilized, no negative cycles Minimum s-t distance is 37/60