The 8-5-3 Milk Jug Problem

Charlene Chu - November 17, 2017

Question. Can the milkman measure out 4 litres?
Challenge. Draw the state graph of this problem (no spilling allowed!).

Here are all of the possible moves. Given the current state s = {a, b, c}, f[x, y, s] returns the state after pouring from the x-litre jug to the y-litre jug, where a, b, c is the number of litres in the 8-, 5-, 3-litre jug, respectively.

f[8,5,{a_,b_,c_}]:={a+b-5,5,c};
f[8,3,{a_,b_,c_}]:={a+c-3,b,3};
f[5,8,{a_,b_,c_}]:={a+b,0,c};
f[5,3,{a_,b_,c_}]:=If[b+c≥3,{a,b+c-3,3},{a,0,b+c}];
f[3,8,{a_,b_,c_}]:={a+c,b,0};
f[3,5,{a_,b_,c_}]:={a,b+c,0};

Here is the start state s.

s={8,0,0};

We can make the following moves to get 4 litres

s=f[8,5,s]

s=f[5,3,s]

s=f[3,8,s]

s=f[5,3,s]

s=f[8,5,s]

s=f[5,3,s]

I am stuck on how to get all of the possible outcomes...