Measuring and timing puzzles

GAME · Chapter 514 min readAsked at Jane Street, Optiver, SIG, IMC

Assumes Logic puzzles: information bounds and common knowledge.

After this lesson you should be able to

  • Measure a quantity you have no instrument for by combining the constraints you do have.
  • Recognise when a puzzle is really an arithmetic identity in disguise.
  • Schedule a set of moves to minimise the worst case rather than the first case.

This family gives you crude instruments and asks for a precise answer: ropes that burn unevenly, jugs with no markings, a clock with no numbers. Every one is solved the same way — stop trying to measure the thing directly and find an operation that combines what you have into what you want.

Proposition 5.1

Combine the constraints, do not refine the instrument

You cannot make an uneven rope burn evenly and you cannot mark a jug. What you can do is run two constraints at once — two ends of the same rope, two jugs against each other, two hands of the same clock — so that their difference or their sum is the quantity you were asked for.

Holds when

  • Ask what operations the objects allow, not what the objects measure.
  • Halving is almost always available: two ends of one rope, or one jug poured into another.
  • If the target is not reachable by those operations, say so and say why — that is also an answer.

Why lighting both ends is the whole trick. A rope that takes an hour to burn from one end takes half an hour lit from both, however unevenly it burns: the two flames between them consume the whole rope, and they meet when the total consumed is all of it. Nothing about the rate mattered. That is the pattern to look for — an operation whose answer does not depend on the thing you were not told.

Example 5.2

Forty-five minutes from two ropes

You have two ropes and a lighter. Each rope burns through in exactly 6060 minutes, but neither burns at a constant rate. Measure 4545 minutes.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    tboth ends=12tone endt_{\text{both ends}} = \tfrac{1}{2} t_{\text{one end}}
  2. Substitute
    Light rope A at both ends and rope B at one end\text{Light rope A at both ends and rope B at one end}
  3. Solve
    t=30t = 30
    Rope A is gone. Rope B has 30 minutes of burn left.
  4. Light B’s second end⇒302=15\text{Light B's second end} \Rightarrow \tfrac{30}{2} = 15
    The remaining rope now burns from both ends.
  5. Answer
    30+15=45 minutes30 + 15 = 45 \text{ minutes}

Sanity check. Both ropes are fully consumed and no rate was ever assumed, which is the test of a correct answer here.

Example 5.3

The follow-up you will get

Same two ropes. Measure 1515 minutes without waiting the first 3030. And what is the full set of times two such ropes can measure?

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    Available: 60, 30, and sums of segments burning in parallel\text{Available: } 60,\ 30,\ \text{and sums of segments burning in parallel}
  2. Substitute
    Light A both ends, B both ends and one extra point? No — only ends are lightable\text{Light A both ends, B both ends and one extra point? No — only ends are lightable}
  3. Solve
    Light A both ends and B one end at t=0\text{Light A both ends and B one end at } t=0
    A ends at 30; light B’s other end then.
  4. {15, 30, 45, 60}\{15,\ 30,\ 45,\ 60\}
    Fifteen arrives at t=45t = 45, not at t=15t = 15: you cannot have it sooner with two ropes.
  5. Answer
    {15, 30, 45, 60} minutes\{15,\ 30,\ 45,\ 60\}\ \text{minutes}

Sanity check. Saying which times are *not* reachable is the part that separates a candidate who solved the puzzle from one who remembered it.

Example 5.4

Four litres from a three and a five

You have an unmarked 33-litre jug, an unmarked 55-litre jug and a tap. Measure exactly 44 litres.

Show the worked solutionHide the worked solution

Worked solution

  1. Formula
    4=2×5−2×34 = 2 \times 5 - 2 \times 3
  2. Substitute
    Every reachable amount is 5a+3b for integers a,b\text{Every reachable amount is } 5a + 3b \text{ for integers } a, b
  3. Solve
    Fill 5→pour into 3\text{Fill 5} \to \text{pour into 3}
    Two litres left in the five.
  4. Empty 3→move the 2 across\text{Empty 3} \to \text{move the 2 across}
    The three-jug holds 2 and has room for 1.
  5. Fill 5→top up the 3\text{Fill 5} \to \text{top up the 3}
    One litre leaves the five.
  6. Answer
    5−1=4 litres5 - 1 = 4 \text{ litres}

Sanity check. Any amount that is a multiple of gcd⁡(3,5)=1\gcd(3,5) = 1 and at most 55 is reachable, so 44 had to be possible before any pouring was attempted.

The rest of this lesson is in Premium

You have read the opening. 11 more sections follow, including 6 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read Arithmetic that survives a clock in full, free.