The Traveller and Three Kegs

I wish I could say that I've found a great way to solve this problem, but I have not.

The way to calculate the expected value of the water in the last keg is to actually trace all possible ways to reach the last keg weighted by their probabilities and sum them up.

Also I will use a rational number library to store this value as a rational number, so as to not loose out on accuracy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import Data.List
import Data.Ratio

type Keg = Rational
type State = [Keg]

rots :: [a] -> [[a]]
rots xs = init (zipWith (++) (tails xs) (inits xs))

calculate :: State -> Rational
calculate kegs = go 0.0 1.0 kegs
    where
        go :: Rational -> Rational -> State -> Rational
        go e p [w]  = e + p*w
        go e p kegs         = foldr (\st e' -> go e' p' st) e newStates
            where
                newStates = [ f s | s <- (rots kegs) ]
                f (1.0:ks) = ks
                f (w:ks) = (w-1):ks
                p' = p/(fromIntegral $ length newStates)

ans = calculate [1,2,3]

Also, I used a monte-carlo simulation to double check my answer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from random import choice

def simulate(kegs):
    while len(kegs) > 1:
        n = choice(range(len(kegs)))
        kegs[n] -= 1;
        if kegs[n] == 0:
            del kegs[n]
    return kegs[0]

ans = sum((simulate([1,2,3]) for i in range(1000000)))/1000000

With the same method as @Agnishom, but in python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

"The Traveller and Three Kegs"

from fractions import Fraction as F

def expct(lst, w):
    lst0 = [x for x in lst if x != 0]
    n = len(lst0)
    if  n == 0:
        return 0
    elif n == 1:
        return lst0[0]*w
    else:
        return sum(expct(lst0[0:i]+[lst0[i] - 1] + lst0[i+1:], w/n) for i in range(n))

print(expct([1,2,3], F(1,1)))

Output:

1

125/72

For the bonus, we need a more optimized solution. We'll be here soon

A code snippet in Julia to calculate the probability of any final configuration recursively (unoptimised; we should add memoisation for larger problems):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function prb(p, q, r)
    if p > 1 || q > 2 || r > 3
       return 0
    elseif p == 1 && q == 2 && r == 3
       return 1
    end
    if p == 0 && q == 0
       return 1//2 * prb(1,0,r) + 1//2 * prb(0,1,r)
    elseif p == 0 && r == 0
       return 1//2 * prb(1,q,0) + 1//2 * prb(0,q,1)
    elseif q == 0 && r == 0
       return 1//2 * prb(p,1,0) + 1//2 * prb(p,0,1)
    elseif p == 0
       return 1//3 * prb(1,q,r) + 1//2 * prb(0,q+1,r) + 1//2 * prb(0,q,r+1)
    elseif q == 0
       return 1//3 * prb(p,1,r) + 1//2 * prb(p+1,0,r) + 1//2 * prb(p,0,r+1)
    elseif r == 0
       return 1//3 * prb(p,q,1) + 1//2 * prb(p+1,q,0) + 1//2 * prb(p,q+1,0)
    else
       return 1//3 * prb(p+1,q,r) + 1//3 * prb(p,q+1,r) + 1//3 * prb(p,q,r+1)
    end
end

The amount of water(in liters) left in the one last keg has 3 possible values: 1, 2, and 3. Let P(n)=the probability that the amount of water in the keg is n(n=1, 2 or 3). To get the expected amount of water, we need to determine 1 * P(1) + 2 * P(2) + 3 * P(3) .

Note that if there is water in all the 3 kegs, the probability of picking any keg at random is $\frac{1}{3}$ . Once a keg is emptied and thrown away, however, the probability of picking a keg becomes $\frac{1}{2}$ . In my solution, there are a lot of notations such as p(1-2-2) . This represents the probability of picking keg # on day 1, 2, 3. etc. For example, p(1-2-3-2) is the probability that the traveler picks the 1st, 2nd, 3rd and 2nd keg on day 1, 2, 3 and 4 respectively.

I. P(3) --- Let's calculate P(3) first since it's the most straightforward of all. The only last keg which could have 3 liters of water left is the 3rd keg . Therefore, P(3) = p(1-2-2) + p(2-1-2) + p(2-2-1) = $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ = $\frac{7}{36}$ .

II. P(2) --- If there are 2 liters of water left in the last keg, then it must be either the 2nd or the 3rd keg . We can break down the calculation into the following 2 scenarios:

a. 2 liters of water left and the last keg is the 2nd keg = p(1-3-3-3) + p(3-1-3-3) + p(3-3-1-3) + p(3-3-3-1) = $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ = $\frac{23}{216}$ .
b. 2 liters of water left and the last keg is the 3rd keg = p(1-2-3-2) + p(1-3-2-2) + p(2-1-3-2) + p(2-3-1-2) + p(2-2-3-1) + p(2-3-2-1) + p(3-1-2-2) + p(3-2-1-2) + p(3-2-2-1) = $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ + $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{3}$ * $\frac{1}{2}$ = $\frac{13}{54}$ .

Now, add the two fractions in a and b, we get P(2) = $\frac{23}{216}$ + $\frac{13}{54}$ = $\frac{25}{72}$ .

III. P(1) --- If there is only 1 liter of water left, it could be in any of the 3 kegs. If we try to dig out all the possible situations, the calculation will get convoluted. However, there is a trick! Since 1, 2 and 3 are the only possible values, then P(1) + P(2) + P(3) must be equal to one! In other words, P(1) = 1 - P(2) - P(3). Therefore, in this case, P(1) = 1 - $\frac{7}{36}$ - $\frac{25}{72}$ = $\frac{11}{24}$ .

Now the expected amount of water = 1 * $\frac{11}{24}$ + 2 * $\frac{25}{72}$ + 3 * $\frac{7}{36}$ = $\frac{125}{72}$ . Since 125 and 72 are coprime positive integers, the final answer is: 125 + 72 = $\boxed{197}$