Thread: Pouring Water into Glasses Using Graphs

1. Pouring Water into Glasses Using Graphs

Hello,

I have a question about transferring water into different glasses. Suppose the capacities of three different glasses are X + Y, X and Y liters respectively where both X and Y are integers with X >= Y > 0 where the largest glass (X+Y) starts full and the others are empty.

How can I show using methods of graph theory that when Y = 1 any configuration is attainable, but that if Y>1, then configurations exist which are unattainable?

I have tried different amounts for X and Y and have noticed that the attainable solutions are always on the boundary but I am having trouble with formalizing the proof. Any help would be awesome!

Thanks

2. Welcome to the forum.

I have tried different amounts for X and Y and have noticed that the attainable solutions are always on the boundary
This is correct. Each configuration can be described by two numbers (a, b) which say how much water is in the bigger and in the smaller glasses, respectively. The configuration space, i.e., all attainable configurations lie on the border of the X x Y rectangle $\{(a,b)\mid 0\le a\le X, 0\le b\le Y, a=0\mbox{ or }a=X\mbox{ or }b=0\mbox{ or }b=Y\}$. Indeed, we start with (0, 0), which is on the border. Also, after each move, one of the two smaller glasses is either full or empty (we pour until the recipient is full or the source is empty). This means that when X >= Y > 1, there are unattainable configurations. I'll leave it to you to confirm that when Y = 1, every configuration is attainable.

Another way to see that there are unattainable configurations is to make X and Y even. Then one can show that each attainable configuration is expressed by even numbers.