xxx. Rope Burning and Hourglasses

Timing puzzles: the only clock is an object that “runs out”, and you may act only at the moments when something runs out. Model them as a search over states at event times.

Two ropes, 45 minutes

Problem. Each of two ropes burns in exactly 60 minutes, but unevenly (half the rope need not take 30 minutes). Measure 45 minutes.

Answer. At time 0 light rope A at both ends and rope B at one end. A burns out at 30 (the two flames together consume 60 minutes of rope at double speed). At that moment light the other end of B: its remaining 30 minutes of rope burn in 15. B burns out at 45.

Ropes	Times measurable from the start (minutes)
1	30, 60
2	30, 45, 60, 90, 120
3	30, 45, 52.5, 60, 67.5, 75, 90, 105, 120, 150, 180
$n$	all of them are multiples of $60/2^n$

Hourglasses

Problem. With a 4-minute and a 7-minute hourglass, measure 9 minutes.

Answer. Start both. At 4 flip the 4-glass. At 7 the 7-glass runs out; the 4-glass has 1 minute of sand left. At 8 the 4-glass runs out: flip the 7-glass, which has run for exactly 1 minute since 7, so it now holds 1 minute of sand. It runs out at 9. (With 7 and 11, measure 15: start both, flip the 7 at 7, flip it again at 11 when it holds 4 minutes, it runs out at 15.)

Glasses $a,b$	Measurable from the start (computed for $T\le 200$)
4, 7	4 and every $T\ge 7$
7, 11	7, 11, 14, 15 and every $T\ge 17$
4, 6	every even $T\ge 4$
any $a,b$, measuring between two events	exactly the multiples of $\gcd (a,b)$

// Hourglasses of a and b minutes, idle at time 0. At time 0 and whenever a glass runs out you may flip any subset.
// Returns every event time <= H: the durations measurable from the start.
set<int> hourglassTimes(int a, int b, int H) {
    set<int> times; set<array<int, 3>> seen;
    auto go = [&](auto&& self, int t, int x, int y) -> void {       // x, y: sand in the upper bulbs (0 = stopped)
        if (t > H || !seen.insert({t, x, y}).second) return;
        for (int fa = 0; fa < 2; fa++) for (int fb = 0; fb < 2; fb++) {
            int nx = fa ? a - x : x, ny = fb ? b - y : y;
            if (!nx && !ny) continue;                                // nothing running: no further events
            int dt = min(nx ? nx : INT_MAX, ny ? ny : INT_MAX);
            if (t + dt <= H) times.insert(t + dt);
            self(self, t + dt, nx ? nx - dt : 0, ny ? ny - dt : 0);
        }
    };
    go(go, 0, 0, 0);
    return times;
}
 
// n ropes of 60 minutes. At time 0 and whenever a rope burns out you may light unlit ends.
// Returns all burn-out times (exact: they are dyadic rationals).
set<double> ropeTimes(int n) {
    set<double> res; set<pair<double, vector<pair<double, int>>>> seen;
    auto go = [&](auto&& self, double t, vector<pair<double, int>> st) -> void {   // per rope: (rope left, ends lit)
        if (!seen.insert({t, st}).second) return;
        int opts = 1; for (auto [r, e] : st) opts *= r > 0 ? 3 - e : 1;
        for (int c = 0; c < opts; c++) {
            auto s = st; int x = c;
            for (auto& [r, e] : s) if (r > 0) { int k = 3 - e; e += x % k; x /= k; }   // light 0..2-e new ends
            double dt = 1e18;
            for (auto [r, e] : s) if (r > 0 && e > 0) dt = min(dt, r / e);
            if (dt == 1e18) continue;                                // nothing burning
            for (auto& [r, e] : s) if (r > 0 && e > 0) r -= e * dt;
            res.insert(t + dt); self(self, t + dt, s);
        }
    };
    go(go, 0, vector<pair<double, int>>(n, {60.0, 0}));
    return res;
}

Proof: event times are multiples of 60/2^n (ropes) and of gcd(a, b) (hourglasses)

Ropes. Only the amount of “burn time” left in a rope matters, since a flame consumes burn time at rate 1 whatever the rope’s thickness: with both ends lit, a rope with $r$ minutes left burns out after $r/2$. Let $u$ be a unit such that the current time and every rope’s remaining burn time are multiples of $u$; initially $u=60$. The next event is after $dt=r$ or $dt=r/2$ for some burning rope, a multiple of $u/2$, and every remaining time decreases by $dt$ or $2dt$; so all quantities stay multiples of $u/2$, and of $u$ itself unless the event is a rope burning out from two ends. Each rope burns out once, so the unit halves at most $n$ times: every event time is a multiple of $60/2^n$.

Hourglasses. Let $g=\gcd (a,b)$. Inductively, at each event the time and both upper-bulb amounts are multiples of $g$: the next event comes after the smaller positive amount (a multiple of $g$), subtracting it keeps multiples of $g$, and flipping maps $x\mapsto a-x$ or $b-y$, again multiples of $g$. So only multiples of $g$ can be measured.

Between events, every multiple of $g$. Keep both glasses running and flip each one whenever it runs out; events happen at all multiples of $a$ and of $b$. For a target $T=cg$, choose $k\ge 0$ with $ka\equiv T(\mathrm{mod}b)$ (possible: $a/g$ is invertible mod $b/g$) and large enough that $ka\ge T$; then $\ell =(ka-T)/b\ge 0$ and the interval from the event $\ell b$ to the event $ka$ has length exactly $T$.

The search is exhaustive. Between events nothing can be decided, so a strategy is exactly a choice of flips at each event, and the recursion enumerates every such choice (states repeat, hence the memo). The table rows are its output; both functions were also checked against the invariants above and the classic answers (9 from 4 and 7, 15 from 7 and 11, 45 from two ropes).

Related notes

• Water Jug (the same gcd argument)
• Classic Puzzles
• BFS and DFS (state-space search)