Ponder This Challenge - January 2025 - The irrational three-jug problem

This puzzle was suggested by Latchezar Christov - thanks!

Three jugs A, B, and C have volumes $V_A=\sqrt{5}$, $V_B=\sqrt{3}$, and $V_C=\sqrt{2}$ liters, respectively. There is a tap from which we can fill the jugs, and a sink into which we can empty them. At the beginning of the problem, the three jugs are empty.

To achieve the solution of the problem, we perform a sequence of steps that can only be one of the following:

• Pour water from the tap into a jug until it is filled to the top.
• Empty a jug into the sink.
• Pour water from one jug into another until either the source jug is empty or the receiving jug is filled to the top, whichever happens first.

We assume that these steps are performed with absolute accuracy and no water is spilled.

Our goal is to measure a specific amount of water, meaning we seek to arrive at a state where any one of the jugs (no matter which one) contains this specific amount. As it is impossible to measure with these jugs any rational, non-zero volume with a finite number of steps, we will relax the condition: Instead of measuring a volume of $1$, we measure a volume of $1 \pm 0.0003$ liters, i.e., any volume in the interval $[0.9997, 1.0003]$ will suffice.

The solution should be presented as a list of two-letter strings that represent the steps of the solution, in which the first letter denotes the source, and the second letter denotes the recipient. The tap is denoted by T and the sink by S. The list should also be preceded by a number representing the minimum number of steps.

For example: If the task is to measure $1 \pm 0.01$ liters, the fastest solution would require six steps and could be described as
6 TA AB BS AB TA AB
Upon completion of the above sequence of six steps, jug A would contain 1.00803 liters of water, a volume within the specified tolerance.

Your goal: Find a sequence of steps measuring $1 \pm 0.0003$ liters such that the number of steps is minimal. Submit your answer using the above format.

A bonus "*" will be given for solving the following problem: Keeping the same jugs A and B, replace jug C with one of the volume $V_C$ such that:

1. $V_C$ is a rational number: $V_C = \frac{p}{q}$, where $p$ and $q$ are integers.
2. $V_C < V_B$.
3. $1\pm 10^{-8}$ liters can be measured with 11 steps.
4. 11 is the minimum possible number of steps.
5. $q$ has the smallest possible value.

Submit $V_C$ in the form $\frac{p}{q}$ and a description of the steps in the above format.

Solution

• Click here to view the solution

  January 2025 Solution:

  One possible solution for the main problem is:

  39 TC CA TC CA AS CA TC CB TC CB CA BC CA AS CA TC CA AS CA TC CA TC CA AS CA TC CA TC CA AS CA TC CA AS CA
  TC CA TC CA
  

  The solution of the bonus is

  4224/3187
  11 TA AB AC TA AC CS AC CS AC TA AC
  

  A relatively simple approach to the problem is to model the contents of a jug as a tuple $(a,b,c)$ where $a,b,c\in\mathbb{Z}$ which means the contents of the jug are $aV_{A}+bV_{B}+cV_{C}$.

  We can then describe each state of the system as a triple of such tuples, and work with a directed graph whose nodes are those triples, and edges can be computed relatively easy given the concrete values of $V\_A, V\_B, V\_C$. On this graph, as simple BFS can provide the shortest path to a "good" node.

  For the bonus part, some of the solvers used continued fractions in order to determine the desired fraction, due to the amazing power of continued fractions to provide the best approximations (denominator size wise) for a given irrational number.

Solvers

• Nadir S. (31/12/2024 1:39 PM IDT)
• Rudy Cortembert (31/12/2024 2:01 PM IDT)
• Ashfaque Shaikh (31/12/2024 2:18 PM IDT)
• *Lazar Ilic (31/12/2024 2:44 PM IDT)
• *Alper Halbutogullari (31/12/2024 3:33 PM IDT)
• Daniel Chong Jyh Tar (31/12/2024 4:58 PM IDT)
• *Harald Bögeholz (31/12/2024 6:03 PM IDT)
• Gary M. Gerken (31/12/2024 6:51 PM IDT)
• *Yi Jiang (31/12/2024 7:08 PM IDT)
• *King Pig (31/12/2024 9:22 PM IDT)
• *Arthur Vause (31/12/2024 10:14 PM IDT)
• *Sanandan Swaminathan (31/12/2024 10:50 PM IDT)
• Harold Gutch (1/1/2025 12:44 AM IDT)
• John Tromp (1/1/2025 2:15 AM IDT)
• Blaine Hill (1/1/2025 2:25 AM IDT)
• Evan Semet (1/1/2025 3:02 AM IDT)
• Jenna Talia (1/1/2025 2:03 PM IDT)
• Gyozo Nagy (1/1/2025 2:41 PM IDT)
• Juergen Koehl (1/1/2025 5:54 PM IDT)
• Lorenz Reichel (1/1/2025 6:48 PM IDT)
• *Stéphane Higueret (1/1/2025 7:01 PM IDT)
• Julian Ma (1/1/2025 8:54 PM IDT)
• Dwij Mehta (1/1/2025 9:37 PM IDT)
• Shirish Chinchalkar (1/1/2025 11:17 PM IDT)
• *John Spurgeon (2/1/2025 1:29 AM IDT)
• José Eduardo Gaboardi de Carvalho (2/1/2025 2:52 AM IDT)
• *Guangxi Liu (2/1/2025 7:56 AM IDT)
• Alex Izvalov (2/1/2025 9:41 AM IDT)
• Balakrishnan V (2/1/2025 3:37 PM IDT)
• Jonathan de Koning (2/1/2025 8:56 PM IDT)
• Robin Guilliou (2/1/2025 8:57 PM IDT)
• Jordan Rinder (3/1/2025 1:58 AM IDT)
• Michael Schuresko (3/1/2025 5:04 AM IDT)
• *Peter Moser (3/1/2025 11:01 AM IDT)
• *Guglielmo Sanchini (3/1/2025 12:32 PM IDT)
• *Paul Lupascu (3/1/2025 1:58 PM IDT)
• *Bertram Felgenhauer (3/1/2025 4:25 PM IDT)
• *Sanjay Rao (3/1/2025 5:04 PM IDT)
• Michael Vahle (3/1/2025 7:08 PM IDT)
• Mathias Schenker (4/1/2025 1:00 AM IDT)
• *David F.H. Dunkley (4/1/2025 1:44 AM IDT)
• *Marcelo De Barros (4/1/2025 3:22 AM IDT)
• Adrian Neacsu (4/1/2025 9:12 AM IDT)
• Reiner Martin (4/1/2025 2:13 PM IDT)
• *Lorenzo Gianferrari Pini (4/1/2025 2:39 PM IDT)
• Soonho You (4/1/2025 2:59 PM IDT)
• *Alexander Daryin (4/1/2025 8:00 PM IDT)
• Andrew Hom (4/1/2025 11:57 PM IDT)
• *Rogerio Ponce da Silva (5/1/2025 6:29 AM IDT)
• Carl Londahl (5/1/2025 12:20 PM IDT)
• *Amos Guler (5/1/2025 12:28 PM IDT)
• *Ankit Aggarwal (5/1/2025 1:37 PM IDT)
• Christian Pfaffenzeller (5/1/2025 1:45 PM IDT)
• Mihai Stancu (5/1/2025 3:38 PM IDT)
• Tamir Ganor & Shouky Dan (5/1/2025 3:42 PM IDT)
• Sri Mallikarjun J (5/1/2025 6:44 PM IDT)
• *Marco Bellocchi (5/1/2025 8:50 PM IDT)
• Arnav Avad (5/1/2025 10:12 PM IDT)
• *Li Li (6/1/2025 1:34 AM IDT)
• *Charles Carroll (6/1/2025 2:36 AM IDT)
• Dan Ismailescu (6/1/2025 3:18 AM IDT)
• *Franciraldo Cavalcante (6/1/2025 10:29 AM IDT)
• Quentin Higueret (6/1/2025 2:33 PM IDT)
• *Klaus Nagel (6/1/2025 2:57 PM IDT)
• Robert Eeksman Tobias (6/1/2025 3:40 PM IDT)
• *Dieter Beckerle (6/1/2025 6:54 PM IDT)
• Marcel Caria (6/1/2025 9:57 PM IDT)
• *Hugo Pfoertner (6/1/2025 10:43 PM IDT)
• Erik Hostens (7/1/2025 1:07 PM IDT)
• *Vladimir Volevich (7/1/2025 1:50 PM IDT)
• Arjun Sharma (7/1/2025 5:16 PM IDT)
• *Dan Dima (7/1/2025 7:08 PM IDT)
• Thomas Egense (7/1/2025 7:08 PM IDT)
• *Andreas Stiller (8/1/2025 7:45 PM IDT)
• Simon Foster (8/1/2025 10:37 PM IDT)
• Clive Tong (9/1/2025 1:30 PM IDT)
• *Kipp Johnson (9/1/2025 8:00 PM IDT)
• *Wenjie Yang (10/1/2025 4:37 AM IDT)
• *Asaf Zimmerman (10/1/2025 10:43 AM IDT)
• *Dominik Reichl (10/1/2025 2:59 PM IDT)
• *Daniel Bitin (10/1/2025 6:10 PM IDT)
• William Han (11/1/2025 3:52 PM IDT)
• Terry Lee (11/1/2025 7:05 PM IDT)
• *Rémi Pérenne (12/1/2025 12:48 PM IDT)
• *David Greer (12/1/2025 8:39 PM IDT)
• Hakan Summakoğlu (13/1/2025 6:19 PM IDT)
• Avi Levin (15/1/2025 9:41 PM IDT)
• *Tim Walters (17/1/2025 3:07 AM IDT)
• *Kang Jin Cho (17/1/2025 7:26 AM IDT)
• John Khoo (17/1/2025 8:48 PM IDT)
• Suyeong Hahn (18/1/2025 5:53 PM IDT)
• *Eran Vered (18/1/2025 7:46 PM IDT)
• Fabio Michele Negroni (18/1/2025 9:53 PM IDT)
• *Bert Dobbelaere (19/1/2025 4:41 PM IDT)
• *Karl-Heinz Hofmann (19/1/2025 6:03 PM IDT)
• *Peter Huggins (19/1/2025 10:41 PM IDT)
• Matt Cristina (20/1/2025 2:14 AM IDT)
• *Nyles Heise (20/1/2025 4:15 AM IDT)
• Jason Kim (20/1/2025 10:01 PM IDT)
• Bharat Kumar Aryasomayajula (21/1/2025 1:37 PM IDT)
• *Fakih Karademir (22/1/2025 1:00 AM IDT)
• Benjamin Cha (22/1/2025 3:22 AM IDT)
• Emmanuel Lazard (22/1/2025 6:23 PM IDT)
• Abhinav Bana (23/1/2025 7:04 AM IDT)
• Michael Liepelt (23/1/2025 1:53 PM IDT)
• Ralf Jonas (24/1/2025 10:29 AM IDT)
• Noam Zaks (24/1/2025 8:54 PM IDT)
• *Ward Beullens (25/1/2025 11:17 PM IDT)
• *Ido Meisner (26/1/2025 12:49 PM IDT)
• *Andrea Andenna (27/1/2025 1:54 AM IDT)
• Vassili Chesterkine (27/1/2025 2:57 PM IDT)
• Karl Mahlburg (28/1/2025 4:08 AM IDT)
• *Motty Porat (29/1/2025 12:08 AM IDT)
• Posa Bogdan (29/1/2025 4:29 PM IDT)
• Kevin Bauer (29/1/2025 6:47 PM IDT)
• Jared Kittleson (29/1/2025 7:47 PM IDT)
• *Károly Csalogány (30/1/2025 1:37 AM IDT)
• *Chris Shannon (1/2/2025 1:42 AM IDT)
• Dezhi Zhao (1/2/2025 5:50 AM IDT)
• Erik Wünstel (1/2/2025 6:32 PM IDT)
• *Oscar Volpatti (2/2/2025 6:49 AM IDT)
• *Stephen Ebert (4/2/2025 1:04 AM IDT)
• *Alex Newman & Eric Niblock (4/2/2025 4:27 AM IDT)
• *Radu-Alexandru Todor (5/2/2025 2:34 AM IDT)
• Kai Guttmann (6/2/2025 2:27 PM IDT)