There are two hourglasses: one runs completely in \(4\) minutes, the other in \(7\) minutes. How do you measure exactly \(9\) minutes when the measurement has to start the first time the clocks are started? Another clock, counting seconds and guessing are not allowed. All you have to do is turn the hourglasses over and watch when the upper chamber is empty. Turning around shouldn’t take any time. What we are looking for is a process in which the end of the desired period of time can be recognized solely by the hourglasses.
We call the clock with \(4\) minutes \(A\) and the one with \(7\) minutes \(B\) . Initially all the sand is at the bottom. We start both clocks at the same time by turning them over; From this moment onwards the searched \(9\) minutes count. After that, you can always trade when a clock at the top becomes empty. You may not turn over one, one or both clocks, even one that is still running. You wait until the next time it runs out. Stopping and marking are not permitted; an empty clock can remain standing. The solution looks like this:
- At minute \(0\) \(A\) and \(B\) are started.
- At minute \(4\) \(A\) is empty and is flipped. \(B\) continues to run unchanged.
- At minute \(7\) \(B\) is empty and is flipped. There is still \(1\) minute left in \(A\) .
- At minute \(8\) \(A\) is empty. In \(B\) sand ran down for exactly \(1\) minute; therefore \(B\) is immediately turned over again.
- At minute \(9\) \(B\) is empty. The time you were looking for has been reached.
At minute \(8\) we turn over the clock \(B\) which is still running. Since their restart at minute \(7\) , exactly as much sand has flowed down as would fit through the bottleneck in \(1\) minute. After turning, only this small amount is on top. It now takes \(1\) minute to trickle down again. The clock therefore becomes empty at minute \(9\) , not after another complete run. So we measure the last minute with sand that has already passed through. The animation shows this move:
Flipping a running hourglass is also useful for the general solution. By remaining time we mean the time that the sand still needs to flow through in the upper chamber. If the full clock has the running time \(c\) and its remaining running time is \(r\) , then the amount of sand at the bottom corresponds to the duration \(cr\) . When you turn it over, this exact amount comes to the top. If the upper chamber is full beforehand, it will be empty afterwards and vice versa. For a partially run clock, the new remaining running time is \(r'\):
$$r'=c-r.$$
Previously, the measurement started with the first turn. This means “without lead time”: every minute since the start counts. “With advance” means, on the other hand, that you can prepare the clocks first and the desired time period begins later. For example, we start both clocks and turn \(A\) over at minute \(4\) . If \(B\) becomes empty at minute \(7\) , our measurement begins. If \(A\) becomes empty at minute \(8\) , it ends. We measured \(1\) minute; the previous \(7\) minutes do not count.
Now we consider arbitrary hourglasses with positive integer running times \(a\) and \(b\) . We call the desired duration \(T\) . What times can be measured with this if preparation is allowed? Here too, the beginning and end must be recognizable by an empty space. So you shouldn't start measuring at some point based on your feeling. The handles remain the same as in the actual puzzle. First we show which times are excluded; then we'll show you how to actually measure all the rest.
First let's take clocks with \(6\) and \(10\) minutes. Both running times are divisible by \(2\) . The sand can therefore be mentally divided into portions, each of which takes \(2\) minutes to go through. When you turn it over or wait until the next time it is empty, only whole portions are created again. All observable empty times are therefore an even number of minutes apart. You cannot use it to measure a duration of \(3\) minutes, even if you prepare the clocks for as long as you like beforehand.
In general, let \(g=\gcd(a,b)\) be the greatest common divisor of the running times. Initially both remaining terms are multiples of \(g\) . When rotated \(r\) becomes either \(ar\) or \(br\) ; both remain divisible by \(g\) . When waiting, the smallest positive remaining time elapses, which is also a multiple of \(g\) . This means that all empty times and their distances remain multiples of \(g\) . A measurable duration must therefore satisfy \(g\mid T\) : \(T\) must be divisible by \(g\) . Whether that is enough remains to be seen.
To do this, we let both clocks run completely again and again and turn each one over as soon as it is empty. The first then becomes empty after \(a,2a,3a,\ldots\) time units, the second after \(b,2b,3b,\ldots\) . We are looking for a time \(mb\) of the second clock and a later time \(na\) of the first, between which exactly \(T\) lies. Bézout's lemma guarantees matching integers \(n,m\) if \(T\) is a positive multiple of \(g\) . The relationship you are looking for is::
$$na-mb=T.$$
The numbers \(n,m\) supplied by Bézout can initially be negative. Negative runs cannot be carried out. However, one can increase both numbers without changing the time interval: we replace them with \(n+kb/g\) and \(m+ka/g\) , where \(k\) is a sufficiently large positive integer. Both times are therefore shifted by the same amount \(kab/g\) ; their difference remains \(T\) . So both numbers become positive and the required times are actually after the clocks start.
Now you count the complete cycles of each clock. When the \(m\) clock becomes empty the measurement begins; it ends when the first clock becomes empty for the \(n\) -th time. There are exactly \(T\) time units in between. The preparation can take a long time. The proof does not promise a particularly short process. For \(T=0\) the beginning and end coincide. This proves for all non-negative integer objectives: With preparation, a duration can be measured if and only if the greatest common divisor divides it:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
This rule does not necessarily apply to starting measurements right at the first start. For example, with \(4\) and \(7\) minutes \(g=1\) , but after \(1\) minute no clock is empty. So you can't see the end of this minute. The measurement from minute \(7\) to \(8\) described above only works because the preparation does not count. The proof thus answers the question of what is possible after preparation. If you are looking for a permitted process with or without preparation, the following systematic search will help.
The PHP script remembers both remaining running times and the time that has elapsed since the start of the measurement. For every such condition, try it all \(4\) Possibilities: no clock, only the first, only the second or turn both over. It then waits until the next time it empties. The value \(-1\) indicates preparation; the entry start sets the measurement time \(0\). Known conditions will not be re-investigated. The sequence found is obtained via its predecessors. wait only refers to the distance to the next emptying, not an additional time measurement:
<?php
declare(strict_types=1);
function hourglass(int $a, int $b, int $target, bool $prepare = false): ?array
{
if ($a <= 0 || $b <= 0 || $target < 0) {
throw new InvalidArgumentException('Positive capacities, nonnegative target required.');
}
$root = [0, 0, $prepare ? -1 : 0];
$key = static fn(array $s): string => implode(',', $s);
$queue = new SplQueue();
$queue->enqueue($root);
$previous = [$key($root) => null];
$enqueue = static function (array $next, array $from, array $action)
use ($queue, &$previous, $key): void {
$k = $key($next);
if (!array_key_exists($k, $previous)) {
$previous[$k] = [$key($from), $action];
$queue->enqueue($next);
}
};
while (!$queue->isEmpty()) {
$state = $queue->dequeue();
[$x, $y, $elapsed] = $state;
if ($elapsed === $target) {
$path = [];
for ($k = $key($state); $previous[$k] !== null;) {
[$k, $action] = $previous[$k];
$path[] = $action;
}
return array_reverse($path);
}
if ($elapsed === -1) {
$enqueue([$x, $y, 0], $state, ['start' => true]);
}
for ($mask = 0; $mask < 4; ++$mask) {
$u = ($mask & 1) ? $a - $x : $x;
$v = ($mask & 2) ? $b - $y : $y;
if ($u === 0 && $v === 0) {
continue;
}
$wait = $u === 0 ? $v : ($v === 0 ? $u : min($u, $v));
$nextTime = $elapsed < 0 ? -1 : $elapsed + $wait;
if ($nextTime > $target) {
continue;
}
$enqueue(
[max(0, $u - $wait), max(0, $v - $wait), $nextTime],
$state,
['flip' => $mask, 'wait' => $wait]
);
}
}
return null;
}
foreach ([[4, 7, 9, false], [4, 7, 1, false], [4, 7, 1, true],
[6, 10, 3, true], [5, 5, 10, false], [4, 7, 0, false]] as $case) {
echo json_encode($case), ': ', json_encode(hourglass(...$case)), PHP_EOL;
}
The search finds or returns a permitted process null, if none exists. It covers all permitted continuations and requires a maximum of preparation \((a+1)(b+1)(T+2)\) States. Large inputs therefore require a lot of memory. The number of search transitions is minimized, not the preparation time. Rational running and target times are converted into whole numbers using a common denominator. For runtimes without a common time unit, for example \(1\) and \(\sqrt{2}\), this finite integer search is not suitable.