Gegeben sind zwei Sanduhren: Die eine läuft in \(4\) Minuten vollständig durch, die andere in \(7\) Minuten. Wie misst man damit genau \(9\) Minuten, wenn die Messung schon beim ersten Start der Uhren beginnen muss? Eine weitere Uhr, Sekundenzählen und Schätzen sind nicht erlaubt. Man darf nur die Sanduhren umdrehen und beobachten, wann die obere Kammer leer ist. Das Umdrehen soll keine Zeit kosten. Gesucht ist also ein Ablauf, bei dem man das Ende der gesuchten Zeitspanne allein an den Sanduhren erkennt.
Wir nennen die Uhr mit \(4\) Minuten \(A\) und die mit \(7\) Minuten \(B\). Anfangs liegt der gesamte Sand jeweils unten. Wir starten beide Uhren gleichzeitig, indem wir sie umdrehen; ab diesem Moment zählen die gesuchten \(9\) Minuten. Danach darf man immer dann handeln, wenn eine Uhr oben leer wird. Dabei darf man keine, eine oder beide Uhren umdrehen, auch eine noch laufende. Bis zum nächsten Leerwerden wartet man. Anhalten und Markierungen sind nicht erlaubt; eine leere Uhr darf stehen bleiben. Die Lösung sieht so aus:
- Bei Minute \(0\) werden \(A\) und \(B\) gestartet.
- Bei Minute \(4\) ist \(A\) leer und wird umgedreht. \(B\) läuft unverändert weiter.
- Bei Minute \(7\) ist \(B\) leer und wird umgedreht. In \(A\) bleibt noch \(1\) Minute.
- Bei Minute \(8\) ist \(A\) leer. In \(B\) ist genau \(1\) Minute Sand nach unten gelaufen; deshalb wird \(B\) sofort nochmals umgedreht.
- Bei Minute \(9\) ist \(B\) leer. Die gesuchte Zeit ist erreicht.
Bei Minute \(8\) drehen wir die noch laufende Uhr \(B\) um. Seit ihrem Neustart bei Minute \(7\) ist genau so viel Sand nach unten gelaufen, wie in \(1\) Minute durch die Engstelle passt. Nach dem Drehen liegt nur diese kleine Menge oben. Sie braucht nun wieder \(1\) Minute, um nach unten zu rieseln. Die Uhr wird deshalb bei Minute \(9\) leer, nicht erst nach einem weiteren vollständigen Durchlauf. Wir messen also die letzte Minute mit Sand, der bereits durchgelaufen ist. Die Animation zeigt diesen Handgriff:
Das Umdrehen einer laufenden Sanduhr ist auch für die allgemeine Lösung nützlich. Mit Restlaufzeit meinen wir die Zeit, die der Sand in der oberen Kammer noch zum Durchlaufen braucht. Hat die volle Uhr die Laufzeit \(c\) und beträgt ihre Restlaufzeit \(r\), dann entspricht die Sandmenge unten der Dauer \(c-r\). Beim Umdrehen kommt genau diese Menge nach oben. Ist die obere Kammer vorher voll, ist sie danach leer und umgekehrt. Bei einer teilweise gelaufenen Uhr ergibt sich die neue Restlaufzeit \(r'\) aus:
$$r'=c-r.$$
Bisher begann die Messung beim ersten Umdrehen. Das bedeutet "ohne Vorlauf": Jede Minute seit dem Start zählt mit. "Mit Vorlauf" bedeutet dagegen, dass man die Uhren zunächst vorbereiten darf und die gewünschte Zeitspanne erst später beginnt. Beispielsweise starten wir beide Uhren und drehen \(A\) bei Minute \(4\) um. Wird \(B\) bei Minute \(7\) leer, beginnt unsere Messung. Wird \(A\) bei Minute \(8\) leer, endet sie. Gemessen haben wir \(1\) Minute; die vorherigen \(7\) Minuten zählen nicht dazu.
Nun betrachten wir beliebige Sanduhren mit positiven ganzzahligen Laufzeiten \(a\) und \(b\). Die gewünschte Dauer nennen wir \(T\). Welche Zeiten lassen sich damit messen, wenn Vorbereitung erlaubt ist? Beginn und Ende müssen auch hier an einem Leerwerden erkennbar sein. Man darf also nicht irgendwann nach Gefühl mit dem Messen anfangen. Die Handgriffe bleiben dieselben wie im konkreten Rätsel. Zunächst zeigen wir, welche Zeiten ausgeschlossen sind; anschließend zeigen wir, wie man alle übrigen tatsächlich misst.
Nehmen wir zunächst Uhren mit \(6\) und \(10\) Minuten. Beide Laufzeiten sind durch \(2\) teilbar. Der Sand lässt sich deshalb gedanklich in Portionen aufteilen, die jeweils \(2\) Minuten zum Durchlaufen brauchen. Beim Umdrehen oder Warten bis zum nächsten Leerwerden entstehen wieder nur ganze solche Portionen. Alle beobachtbaren Leerzeitpunkte liegen somit eine gerade Anzahl von Minuten auseinander. Eine Dauer von \(3\) Minuten kann man damit nicht messen, auch dann nicht, wenn man die Uhren vorher beliebig lange vorbereitet.
Allgemein sei \(g=\gcd(a,b)\) der größte gemeinsame Teiler der Laufzeiten. Anfangs sind beide Restlaufzeiten Vielfache von \(g\). Beim Drehen wird aus \(r\) entweder \(a-r\) oder \(b-r\); beides bleibt durch \(g\) teilbar. Beim Warten verstreicht die kleinste positive Restlaufzeit, also ebenfalls ein Vielfaches von \(g\). Damit bleiben auch alle Leerzeitpunkte und ihre Abstände Vielfache von \(g\). Eine messbare Dauer muss daher \(g\mid T\) erfüllen: \(T\) muss durch \(g\) teilbar sein. Ob das schon genügt, ist noch zu zeigen.
Dazu lassen wir beide Uhren immer wieder vollständig durchlaufen und drehen jede um, sobald sie leer ist. Die erste wird dann nach \(a,2a,3a,\ldots\) Zeiteinheiten leer, die zweite nach \(b,2b,3b,\ldots\). Wir suchen einen Zeitpunkt \(mb\) der zweiten Uhr und einen späteren Zeitpunkt \(na\) der ersten, zwischen denen genau \(T\) liegt. Das Lemma von Bézout garantiert passende ganze Zahlen \(n,m\), wenn \(T\) ein positives Vielfaches von \(g\) ist. Die gesuchte Beziehung lautet:
$$na-mb=T.$$
Dabei können die von Bézout gelieferten Zahlen \(n,m\) zunächst negativ sein. Negative Durchläufe lassen sich nicht ausführen. Man kann jedoch beide Zahlen vergrößern, ohne den Zeitabstand zu ändern: Wir ersetzen sie durch \(n+kb/g\) und \(m+ka/g\), wobei \(k\) eine genügend große positive ganze Zahl ist. Beide Zeitpunkte verschieben sich dadurch um denselben Betrag \(kab/g\); ihre Differenz bleibt \(T\). So werden beide Zahlen positiv, und die benötigten Zeitpunkte liegen tatsächlich nach dem Start der Uhren.
Nun zählt man die vollständigen Durchläufe jeder Uhr mit. Beim \(m\)-ten Leerwerden der zweiten Uhr beginnt die Messung; beim \(n\)-ten Leerwerden der ersten Uhr endet sie. Dazwischen liegen genau \(T\) Zeiteinheiten. Die Vorbereitung darf dabei lange dauern. Einen besonders kurzen Ablauf verspricht der Beweis nicht. Für \(T=0\) fallen Beginn und Ende zusammen. Damit ist für alle nichtnegativen ganzzahligen Ziele bewiesen: Mit Vorbereitung lässt sich genau dann eine Dauer messen, wenn der größte gemeinsame Teiler sie teilt:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Für einen Messbeginn direkt beim ersten Start gilt diese Regel nicht ohne Weiteres. Mit \(4\) und \(7\) Minuten ist beispielsweise \(g=1\), doch nach \(1\) Minute ist noch keine Uhr leer. Man kann das Ende dieser Minute also nicht erkennen. Die oben beschriebene Messung von Minute \(7\) bis \(8\) funktioniert nur, weil die Vorbereitung nicht mitzählt. Der Beweis beantwortet somit die Frage, was nach Vorbereitung möglich ist. Sucht man einen erlaubten Ablauf mit oder ohne Vorbereitung, hilft die folgende systematische Suche.
Das PHP-Script merkt sich beide Restlaufzeiten und die seit Messbeginn vergangene Zeit. Für jeden solchen Zustand probiert es alle \(4\) Möglichkeiten: keine Uhr, nur die erste, nur die zweite oder beide umdrehen. Danach wartet es bis zum nächsten Leerwerden. Der Wert \(-1\) kennzeichnet die Vorbereitung; der Eintrag start setzt die Messzeit auf \(0\). Bekannte Zustände werden nicht erneut untersucht. Über ihre Vorgänger erhält man den gefundenen Ablauf. wait bezeichnet nur den Abstand zum nächsten Leerwerden, keine zusätzliche Zeitmessung:
<?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;
}
Die Suche findet einen erlaubten Ablauf oder liefert null, wenn keiner existiert. Sie erfasst alle erlaubten Fortsetzungen und benötigt mit Vorbereitung höchstens \((a+1)(b+1)(T+2)\) Zustände. Große Eingaben brauchen daher viel Speicher. Minimiert wird die Zahl der Suchübergänge, nicht die Vorbereitungsdauer. Rationale Lauf- und Zielzeiten rechnet man mit einem gemeinsamen Nenner in ganze Zahlen um. Für Laufzeiten ohne gemeinsame Zeiteinheit, beispielsweise \(1\) und \(\sqrt{2}\), ist diese endliche Ganzzahlsuche nicht geeignet.