The brainbuster

One for the festive season:

There are three thirsty elves and 12 litres of mulled wine in a 12-litre measure filled to the brim.

They want to share out the wine equally. (Normally there'd be a lot of squabbling but, hey, it's the season of goodwill.)

They have a 5-litre measure and a 3-litre measure, and a jug each. The jugs are all definitely bigger than 4 litres but their exact volumes are unknown - so they can't be used for measuring, just as receptacles.

What is the minimum number of steps the elves can take to share out the wine into the jugs? (Pouring the wine from one measure to another counts as a single step, as does pouring from a measure into one of the jugs.)

And can you show it's the minimum?

You can make the usual unrealistic assumptions, such as the elves being sober enough to pour without spilling.

Show your workings. Only complete entry forms will be considered. The judge's decision is final.

The entries

There was a fair number of entries for this competition, with most coming up with a correct solution (although quite a few said 12 steps). There were some clever entries demonstrating that the answer given was the minimum number of moves. Well done to all who found the right answer.

The solution

Here is the answer as given by our winner:

11 pours is the minimum number of pours needed to achieve 4 jugs of 4 litres of wine.

Assume that the configuration is 12l jug, 5l jug, 3l jug - elf jug1, elf jug2, elf jug3 and that the starting configuration is 12,0,0 - 0,0,0 then one example set of pours is:

1: 7,5,0 - 0,0,0
2: 4,5,3 - 0,0,0
3: 0,5,3 - 0,0,4
4: 0,5,0 - 0,3,4
5: 0,2,3 - 0,3,4
6: 0,0,3 - 2,3,4
7: 0,3,0 - 2,3,4
8: 0,5,0 - 2,1,4
9: 0,2,3 - 2,1,4
10: 0,0,3 - 4,1,4
11: 0,0,0 - 4,4,4.

By defining the pour "rules" for the jugs of different volumes we can construct a graph where each node is a possible wine distribution configuration and each directed edge shows that you can move between these nodes in a single pour.

Doing this we can run a graph shortest path algorithm (e.g. Dijkstra's) to find the shortest path between the 12,0,0 - 0,0,0 and 0,0,0 - 4,4,4 nodes. This proves that you can't do it in anything less than 11 pours.

And the winner is...

The winner of ecm's brainbuster no. 39 is Adam Hill, a senior data scientist with a PhD in Physics. Adam wins £200 of Amazon vouchers to spend on high-tech.

Congratulations again to Adam, and watch out for ecm's next brainbuster!