This is a well known practical puzzle and it comes in many versions. Probably the most famous version is the one used in the movie Die Hard With A Vengeance, starring Bruce Willis and Samuel L. Jackson (1995). They are given a five gallon jug and a three gallon jug, and must put exactly four gallons of water on a scale to keep a bomb from exploding. This is serious stuff!
The version we use here is applicable to certain sections of Melbourne. It is used as a framework for examining the dynamic programming "general purpose" approach to a large class of problems addressing the following generic problem:
You are given a system whose state dynamics is governed by a known rule depending on your actions. Your are required to transform the system from its present (given) state to another (prescribed) state. Needless to say, if you are an optimization freak, you may consider the case where the objective is to achieve the desired transformation in a minimum number of transitions. |
The instance we shall examine here is as follows:
The famous Student Prince Pub offers a special deal on Friday nights. You can drink as much beer as you wish/can provided that you consume 4 oz at a time. The Pub provides the beer in 8 oz mugs. At your disposal there are also one 3 oz mug and one 5 oz mug. |
In case you already had some beer today and are unclear about the problem, here it is in a crystal clear form: Device a plan that will produce a mug containing exactly 4 oz of beer given that you start with a full 8 oz mug, an empty 3 oz mug, and an empty 5 oz mug.
Needless to say, if you decide to pour beer from mug A to mug B, then the volume you pour the smaller of
- The volume of beer in A
- The free volume remaining in B
In due course we shall analyse this problem from a dynamic programming perspective.
In preparation for this we suggest you do the following:
- First, practice your virtual beer pouring skills on the special apparatus we constructed for you.
- Second, read the preliminary analysis of this problem.
- Third, have a look at the dynamic programming treatment of the problem.
Should you decide to play this game, please use milk not beer!
