Teaser 2497: [Measuring jugs]
From The Sunday Times, 1st August 2010 [link] [link]
I have two jugs that hold whole numbers of pints, and together they hold two gallons [= 16 pints]. Using only the two jugs and a tap, discarding water as necessary, I can end up with a total of any whole number of pints from 1 to 16 in the two jugs combined. If I want to end up with exactly one pint in the most economical way possible, I have to draw more water than if I want to end up with exactly four pints.
What are the capacities of the two jugs?
This puzzle was originally published with no title.
[teaser2497]
Frits and 
S2T2 
Jim Randell 9:22 am on 28 October 2025 Permalink |
This Python program runs in 73ms. (Internal runtime is 450µs).
from enigma import (Enumerator, irange, printf) # solve for capacities A and B # n = max number of steps to consider def solve(A, B, n=50): k = 0 r = dict() # r maps (vA + vB) positions to minimal measure (volume drawn) p = dict() # p maps (vA, vB) to minimal measure vs = {(0, 0, 0)} # (vol in A, vol in B, vol drawn) while vs and k < n: ss = Enumerator(vs) vs = set() for (vA, vB, vD) in ss: # skip positions where we have already check a lower measure if (vA, vB) in p and p[(vA, vB)] <= vD: continue p[(vA, vB)] = vD # check current amounts vT = vA + vB # record vT -> vD in r, if vD is minimal if vT not in r or (vD < r[vT]): r[vT] = vD # move some water around: # fill A from the tap if vA < A: vs.add((A, vB, vD + A - vA)) # fill B from the tap if vB < B: vs.add((vA, B, vD + B - vB)) # discard A if vA: vs.add((0, vB, vD)) # discard B if vB: vs.add((vA, 0, vD)) # transfer water from A to B if vA and vB < B: if vT > B: vs.add((vT - B, B, vD)) else: vs.add((0, vT, vD)) # transfer water from B to A if vB and vA < A: if vT > A: vs.add((A, vT - A, vD)) else: vs.add((vT, 0, vD)) # move to the next step k += 1 # return result return r # make all values from 1 to 16 pints ts = set(irange(1, 16)) # consider the capacity of the smaller jug for A in irange(1, 8): # capacity of the larger jug B = 16 - A # find minimal configurations r = solve(A, B) # check we can make all target values if not ts.issubset(r.keys()): continue # and that making 1 pint requires drawing more water than 4 pints if not (r[1] > r[4]): continue # output configuration printf("capacities = [{A}, {B}]") for k in irange(1, 16): printf(" {k} pints -> {d} pints drawn", d=r[k]) printf()Solution: The jugs have capacities of 7 pints and 9 pints.
We can make 1 pint by drawing 28 pints (and discarding 27 pints) as follows (13 steps):
And we can make 4 pints by drawing 18 pints (and discarding 14 pints) as follows (7 steps):
There are a couple of shortcuts we could use:
If the capacities have a GCD > 1, then it will be impossible to make an amount that is not a multiple of that GCD, so we could just consider co-prime capacities.
If one of the capacities is 1 (and the other is 15), and we we can make all amounts from 1 – 16 without any wastage, so we could skip checking this arrangement.
LikeLike
Frits 5:05 am on 1 November 2025 Permalink |
I did this recursion in a different way than my other recursion code. Normally I would do all checks before the next recursion call. Now the first thing I do in the recursion is to check the new values v1, v2 and w.
The code to check other targets has been set up so that solve() doesn’t have to be called anymore.
from math import gcd # try go get to target by filling, discarding or transfering water # parameters: volumes, target and water drawn def solve(v1, v2, tgt, w=0, ss=set()): global mw, c1, c2 # skip if we have already drawn more water than another solution if w >= mw or (v1, v2) in ss: return t = v1 + v2 ss_ = ss | {(v1, v2)} # end up with the target of whole number of pints in the two jugs combined if t == tgt: mw = min(w, mw) yield w else: # fill 1st jug from tap, don't allow (c1, 0) at a late stage if v1 < c1 and (not w or v2): yield from solve(c1, v2, tgt, w + c1 - v1, ss_) # fill 2nd jug from tap, don't allow (0, c2) at a late stage if v2 < c2 and (not w or v1): yield from solve(v1, c2, tgt, w + c2 - v2, ss_) # empty 1st jug if v1 and v2 < c2: yield from solve(0, v2, tgt, w, ss_) # empty 2nd jug if v2 and v1 < c1: yield from solve(v1, 0, tgt, w, ss_) # fill 1st jug as much as possible from 2nd jug if v1 < c1 and v2: m = min(v2, c1 - v1) yield from solve(v1 + m, v2 - m, tgt, w, ss_) # fill 2nd jug as much as possible from 1st jug if v2 < c2 and v1: m = min(v1, c2 - v2) yield from solve(v1 - m, v2 + m, tgt, w, ss_) M = 10**9 # maximum of number of pints of water available # assume capacity of jug 1 is not more than capacity of jug 2 for c1 in range(1, 9): c2 = 16 - c1 # all possible solutions are a mutiple of the gcd if gcd(c1, c2) > 1: continue m, mw = M, M # minimum water drawn # check for one pint for m in solve(0, 0, 1, 0, set()): pass if (m1 := m) == M: continue # check for four pints m, mw = M, M # minimum water drawn for m in solve(0, 0, 4, 0, set()): pass if m >= m1 or m == M: continue # check other targets within 1-16 doable = {1, 4, c1, c2, 16, c1 + 1, # 1 in J2, fill J1 c1 + 4, # 4 in J2, fill J1 c2 - c1, # fill J2, transfer to J1, empty J1 c2 - c1 + 1, # 1 in J1, fill J2, transfer to J1, empty J1 c2 - c1 + 4, # 4 in J1, fill J2, transfer to J1, empty J1 2 * c1 - c2, # c1 in both jugs, transfer to J2, empty J2 2 * c1} # check feasability of other targets for t in [i for i in range(1, 16 - c1) if i not in doable]: mw = M # minimum water drawn if any(solve(0, 0, t, 0, set())): continue break else: # no break print(f"answer: {c1} and {c2} pints")LikeLike