Two hourglasses, no clock and an interval to measure: is adding and subtracting their durations enough? The connection with the water-jug problem and Diophantine equations is natural, but a numerical identity is different from a physically executable sequence of moves.
The general method, explained step by step
To understand when ax + by = c has integer solutions, how to find Bézout’s identity and how to obtain every solution, read Linear Diophantine equations: theory and example with extended Euclid.
Open the general Diophantine-equation laboratory: enter the three integer coefficients a, b and c and follow the divisions, substitutions and constraints without skipping any steps.
The hourglass problems and protocols remain here: the equation certifies arithmetic compatibility, but does not replace checking the turns and the instant at which measurement begins.
Open the hourglass laboratory: choose a, b and d; inspect extended Euclid, a proof of existence or impossibility, all integer solutions and a visual turning protocol.
1. Rules: measuring immediately or after preparation
The ideal hourglasses have integer durations a and b and initially all sand is at the bottom. At the initial instant you may start one or both. Afterwards, act only when at least one empties: turn one, both or neither. Turning a glass that is still running is allowed. Estimating the sand by eye or using another clock is not allowed.
If a glass of duration a has r minutes remaining, turning it leaves a − r minutes. For example, a 7-minute glass that has run for 1 minute has r = 6; turning it leaves 7 − 6 = 1 minute. However, the turn must occur at an instant identified by an emptying event.
- Measurement from the initial start: start at t = 0 and require a signal exactly at t = d.
- Measurement after preparation: prepare the system, start measuring at an emptying, and finish at another emptying d minutes later.
These are different requests. With 3- and 5-minute glasses, no signal can mark 1 minute after the initial start: the first event cannot precede 3 minutes. Yet 1 minute can be measured later, for example between minutes 9 and 10, using three 3-minute cycles and two 5-minute cycles.
2. The mathematical test: the GCD must divide d
Seek integers x and y satisfying ax + by = d. Integers include positive numbers, zero and negative numbers. If g = GCD(a,b), every ax + by is a multiple of g, since both a and b are. Thus, if g does not divide d, the equation is impossible.
The converse also holds. Bézout’s identity gives integers u and v satisfying au + bv = g. If d = gh, multiply by h: a(uh) + b(vh) = d. Therefore ax + by = d has integer solutions if and only if GCD(a,b) divides d.
For hourglasses, all observable event times and remaining times stay multiples of g: this holds initially and is preserved by subtraction and turning. If g does not divide d, the interval is impossible even with preparation.
If g divides d, the interval can always be measured when preparation is allowed: choose a solution with opposite signs and read d as the difference between two full-cycle completion times. Start both cycle counts together, restart each glass at its emptyings until its prescribed count is reached, and measure between the two final emptyings. The criterion alone does not guarantee measurement starting already at t = 0.
3. Extended Euclid: from 4 and 7 to a solution of 4x + 7y = 9
First find the GCD through division with remainder:
7 = 1 × 4 + 34 = 1 × 3 + 13 = 3 × 1 + 0
The last nonzero remainder is 1. Work backwards: 1 = 4 − 3 = 4 − (7 − 4) = 2 × 4 − 7. We have u = 2 and v = −1. Since 9 = 9 × 1, multiply by 9: 9 = 18 × 4 − 9 × 7. One solution is (x₀,y₀) = (18,−9).
The laboratory also expresses each remainder as a combination of a and b: this is the same Bézout back-substitution, maintained during the calculation. For the impossible case 6x + 10y = 7 it instead finds g = 2 and writes 7 = 3 × 2 + 1: remainder 1 proves that no solution exists.
4. Not just one pair: all solutions
Starting from a solution (x₀,y₀), all others are x = x₀ + (b/g)k and y = y₀ − (a/g)k, with integer k. The extra terms cancel: a(b/g)k − b(a/g)k = 0. Conversely, subtracting two solutions and using the fact that a/g and b/g are coprime yields exactly this family.
Here x = 18 + 7k and y = −9 − 4k. Setting k = −2 gives (4,−1): 4 × 4 − 7 = 9. Setting k = −3 gives (−3,3): −3 × 4 + 3 × 7 = 9. Both are correct.
A negative coefficient means a difference of durations, not negative time or a negative number of turns. If we only concatenate full cycles we must impose x ≥ 0 and y ≥ 0, namely ceil(−x₀/(b/g)) ≤ k ≤ floor(y₀/(a/g)): ceil rounds upwards to an integer, floor downwards. For 4x + 7y = 9 there are no nonnegative pairs. Yet turning partly full glasses allows 9 minutes to be measured from the initial start, as problem 3 shows. Do not confuse these two tests.
5. Twelve problems with explained solutions
1. A first step: 3 and 5 to measure 8
Use 3- and 5-minute glasses to measure 8 minutes from the initial start.
Solution
Start only the 3-minute glass. When it empties at t = 3, start the 5-minute glass. It empties at t = 8. The equation is 3x + 5y = 8 with x = y = 1: here full cycles are added in succession.
Try 3, 5 → 8 in the laboratory
2. A difference: 4 and 7 to measure 3
Measure a 3-minute interval using 4- and 7-minute glasses. Preparation is allowed.
Solution
Start both together. Begin measuring at t = 4 and finish at t = 7. The duration is 7 − 4 = 3, so (x,y) = (−1,1). This is not 3 minutes from the initial start: the first event only occurs at t = 4.
Try 4, 7 → 3 in the laboratory
3. Turning a partly full glass: 4 and 7 to measure 9
Measure 9 minutes from the initial start using 4- and 7-minute glasses.
Solution
- At t = 0 start both.
- At t = 4 turn the 4-minute glass.
- At t = 7 turn the 7-minute glass; the other continues with 1 minute remaining.
- At t = 8 the 4-minute glass empties. The 7-minute glass has run for 1 minute: turn it, leaving 1 minute.
- At t = 9 the 7-minute glass empties: finish.
4 × 4 − 7 = 9 certifies arithmetic compatibility, but does not describe these turns. Check the physical protocol separately.
Try 4, 7 → 9 in the laboratory
4. Another partial turn: 7 and 11 to measure 15
Measure 15 minutes from the initial start using 7- and 11-minute glasses.
Solution
Start both. At t = 7 turn the 7-minute glass. At t = 11 the 11-minute glass empties and the other has 3 minutes remaining. Turn the 7-minute glass: now 7 − 3 = 4 minutes remain. It empties at t = 15. The identity −7 + 2 × 11 = 15 solves the equation.
Try 7, 11 → 15 in the laboratory
5. A GCD greater than 1: 6 and 10 to measure 4
Measure 4 minutes using 6- and 10-minute glasses, allowing preparation.
Solution
GCD(6,10) = 2 and 2 divides 4. Start both and measure from t = 6 to t = 10. The identity is −6 + 10 = 4. Durations need not be coprime: their GCD must divide the target.
Try 6, 10 → 4 in the laboratory
6. A genuine impossibility: 6 and 10 to measure 7
Can you measure 7 minutes using 6- and 10-minute glasses, even after preparation?
Solution
No. 6x + 10y = 2(3x + 5y) is always even, whereas 7 is odd. Every observable emptying stays at an even time; the difference between two such times is even too. Finding a cleverer move cannot fix this.
Check the impossibility in the laboratory
7. Just one minute: 5 and 8
Measure a 1-minute interval using 5- and 8-minute glasses. Preparation is allowed.
Solution
−3 × 5 + 2 × 8 = 1. Start both. Restart the 5-minute glass at t = 5 and t = 10, and the 8-minute glass at t = 8. At t = 15 the third 5-minute cycle ends: begin measuring. At t = 16 the second 8-minute cycle ends: finish. This measures from 15 to 16, not 1 minute after the initial start.
Try 5, 8 → 1 in the laboratory
8. Full cycles: 8 and 12 to measure 20
Measure 20 minutes from the initial start using 8- and 12-minute glasses.
Solution
8 + 12 = 20. Start the 8-minute glass; when it empties at t = 8, start the 12-minute glass. It finishes at t = 20. GCD(8,12) = 4 divides 20; (x,y) = (1,1).
Try 8, 12 → 20 in the laboratory
9. A blocking remainder: 8 and 12 to measure 10
Can you measure 10 minutes using 8- and 12-minute glasses, even after preparation?
Solution
No. The GCD is 4, but 10 = 2 × 4 + 2. Every 8x + 12y is a multiple of 4; 10 is not. All events and their differences remain multiples of 4.
Check 8, 12 → 10 in the laboratory
10. Larger durations: 9 and 14 to measure 23
Measure 23 minutes from the initial start using 9- and 14-minute glasses.
Solution
Start the 9-minute glass. When it empties, start the 14-minute glass. It finishes at t = 9 + 14 = 23. The pair (1,1) solves 9x + 14y = 23.
Try 9, 14 → 23 in the laboratory
11. Same glasses, another target: 9 and 14 to measure 5
Measure 5 minutes with the same glasses. Preparation is allowed.
Solution
Start both. Begin measuring when the 9-minute glass empties at t = 9, and finish when the other empties at t = 14. The identity is −9 + 14 = 5. Changing the target changes the protocol even with the same glasses.
Try 9, 14 → 5 in the laboratory
12. A coarser time unit: 10 and 15 to measure 5
Measure 5 minutes using 10- and 15-minute glasses, allowing preparation. Could you measure 1 minute?
Solution
Start both and measure from t = 10 to t = 15: −10 + 15 = 5. The GCD is 5, so 5 is possible but 1 is not. The accessible arithmetic unit is not always one minute: here it is 5 minutes.
Try 10, 15 → 5 in the laboratory
6. Reading the laboratory
The calculation separates two tasks. First it solves the equation: Euclidean divisions, Bézout’s identity, multiplication by d/g, the parametric family and a nonnegative-coefficient test. Changing k checks other pairs without changing ax + by.
Next it searches states (t,rA,rB), where rA and rB are the minutes remaining. At each emptying it considers the four allowed moves and waits for the next event: no skipped instants or hidden clock. It searches all reachable states up to t = d. If it finds a signal at d, it displays a measurement from the initial start; otherwise, if the GCD divides d, it constructs a measurement after preparation by comparing full cycles. It does not promise the fewest moves or shortest preparation.
The controls step through events, play, pause and reset. The sand shown is the sand after the move; the table lists time, event, turn and remaining times. For prepared measurements the logical timer’s starting point is highlighted: elapsed preparation time is not the requested interval.
For the theorem used here, see Raji, Elementary Number Theory, Linear Diophantine Equations. These problems and explanations develop that criterion within the hourglass model.