How to model 3 glass problem to graph?The barman gives you three glasses whose sizes are 1000ml, 700ml, and 400ml, respectively. The 700ml and 400ml glasses start out full of beer, but the 1000ml glass is initially empty. You can get unlimited free beer if you win the following game: Game rule: You can keep pouring beer from one glass into another, stopping only when the source glass is empty or the destination glass is full. You win if there is a sequence of pourings that leaves exactly 200ml in the 700ml or 400 ml glass.

Question

bibliothecaqz · Accepted Answer

Step 1I would model your problem as a rather huge graph with nodes       v          i      j      k       which correspond to the state where   i  ⋅  100 ml of beer are in the 1000ml glass,   i  ⋅  100 ml of beer are in the 700ml glass, and   k  ⋅  100 ml of beer are in the 400ml glass. Of course,   i  ≤  10,   j  ≤  7, and   k  ≤  4. Two nodes u and v are connected by a directed edge if the state corresponding to u can be transformed to the state corresponding to v by a valid move.Step 2As an example, your initial node will be       v          0      ,      7      ,      4       and will be connected to       v          7      ,      0      ,      4       and       v          4      ,      7      ,      0       since you can either pour the full 700ml glass into the 1000ml glass or the 400ml glass into the 1000ml glass.Inside this graph you have to find a path from       v          0      ,      7      ,      4       to       v          i      ,      2      ,      k       or       v          i      ,      j      ,      2       for some   i  ≤  10,   j  ≤  7, and   k  ≤  4. To simplify your task you can connect all these possible end nodes to an artifitial node v and look for a       v          0      ,      7      ,      4      -v-path instead.

Answered question

Answer & Explanation

New Questions in Algebra II