January 2025 - Challenge
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.
- V_C is a rational number: V_C = \frac{p}{q}, where p and q are integers.
- V_C < V_B.
- 1\pm 10^{-8} liters can be measured with 11 steps.
- 11 is the minimum possible number of steps.
- q has the smallest possible value.
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:
Submit V_C in the form \frac{p}{q} and a description of the steps in the above format.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
31/12/2024 @ 10:50 AM EST
Solution:
05/02/2025 @ 12:00 AM EST
List Updated:
12/02/2025 @ 12:35 AM EST
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)