Results 1 to 2 of 2

Math Help - Pouring Water into Glasses Using Graphs

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    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.

    There are several pages about this problem on the cut-the-knot site. This link describes the puzzle in graph-theoretic terms.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 29th 2010, 10:25 PM
  2. Replies: 3
    Last Post: February 15th 2010, 11:53 AM
  3. In deep water!
    Posted in the Geometry Forum
    Replies: 5
    Last Post: February 6th 2010, 07:02 PM
  4. A tank of water.
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: October 16th 2008, 11:11 AM
  5. Replies: 4
    Last Post: October 22nd 2007, 04:19 PM

Search Tags


/mathhelpforum @mathhelpforum