Three Glass Puzzle

Graph Theoretical Approach

Oystein Ore gave a worldly twist to the Three Glass puzzle and solved it in the framework of the Graph Theory.

Every distribution of wine in the three jugs A, B, and C, can be described by the quantities b and c of wine in the jugs B and C, respectively. Thus every possible distribution of wine is described by a pair (b,c). Initially b=c=0 so that one starts with the distribution (0,0). The target distribution is obviously (4,0).

puz(WaterPuzzle) in this case consists of all integer pairs (b,c) connected by edges wherever it's possible to move from one node to another by pouring wine between the jugs. Thus, from (0,0) we can move to (5,0) and (0,3). From (5,0) it's possible to move back to (0,0) but also to (2,3) by pouring from B to C and to (5,3) by pouring from A to C. Continuing in this manner we'll discover that the nodes of the graph corresponding to the feasible configurations of wine are located on the perimeter of the 6x4 rectangle in the first quadrant. (Why?)

On the diagram I only showed some of the edges. In particular, there is a walk from the starting node (0,0) to the target node (4,0), viz.

Complete puz(WaterPuzzle), as it follows from the proof of one of the statements derived previously, consists of all possible horizontal, vertical, and diagonal (upper-left-to-bottom-right) edges that connect perimeter points.

Remark

It's perhaps relevant to note that puz(WaterPuzzle) with nodes on the perimeter of the 6x4 rectangle resembles the diagram obtained in describing a slanted cut of the torus with a rational slope. In this case the cut here proceeds in the mirror direction of that on the torus. As I just noted all the diagonal lines connecting points on the perimeter are included. This shows that the serpentine band is indeed of constant width.

Reference

1. O.Ore (R.J.Wilson), Graphs And Their Uses, MAA, New Math Library, 1990.

• Graphs Fundamentals
  • Crossing Number of a Graph
  • Regular Polyhedra
  • 3 Utilities Puzzle: Water, Gas, Electricity
  • A Clique of Acquaintances
  • Round Robin Tournament
  • The Affirmative Action Problem
  • The Two Men of Tibet Problem
• Puzzles on graphs
  • Three Glass Puzzle (example)
  • Three Glass Puzzle in Barycentric Coordinates (example)
  • Sierpinski Gasket and Tower of Hanoi (example)
  • Sam Loyd's Fifteen
  • Sliders
  • Lucky 7
  • Happy 8
  • Blithe 12
  • Slider puzzles
• Permutations
  • Various ways to define a permutation
  • Counting and listing all permutations
• Transpositions
  • A Shuttle Puzzle
• Groups of Permutations
  • Group multiplication of permutations

Copyright © 1996-2009 Alexander Bogomolny