Er zijn twee zandlopers: de ene loopt volledig in \(4\) minuten, de andere in \(7\) minuten. Hoe meet je precies \(9\) minuten wanneer de meting moet beginnen bij de eerste keer dat de klokken worden gestart? Nog een klok, seconden tellen en raden is niet toegestaan. Het enige wat je hoeft te doen is de zandloper omdraaien en kijken wanneer de bovenkamer leeg is. Het omdraaien hoeft geen tijd te kosten. Wat wij zoeken is een proces waarbij het einde van de gewenste tijd uitsluitend aan de zandlopers te herkennen is.
We noemen de klok met \(4\) minuten \(A\) en die met \(7\) minuten \(B\) . Aanvankelijk bevindt al het zand zich op de bodem. We starten beide klokken tegelijkertijd door ze om te draaien; Vanaf dit moment tellen de gezochte \(9\) minuten. Daarna kun je altijd handelen als een klok bovenaan leeg raakt. Je mag niet één, één of beide klokken omdraaien, zelfs niet één die nog loopt. Je wacht tot de volgende keer dat het op is. Stoppen en markeren zijn niet toegestaan; een lege klok kan blijven staan. De oplossing ziet er als volgt uit:
- Op minuut \(0\) worden \(A\) en \(B\) gestart.
- Op minuut \(4\) is \(A\) leeg en wordt omgedraaid. \(B\) blijft onveranderd draaien.
- Op minuut \(7\) is \(B\) leeg en wordt omgedraaid. Er is nog \(1\) minuut over in \(A\) .
- Op minuut \(8\) is \(A\) leeg. In \(B\) liep het zand precies \(1\) minuut naar beneden; daarom wordt \(B\) onmiddellijk weer omgedraaid.
- Op minuut \(9\) is \(B\) leeg. Het door u gezochte tijdstip is bereikt.
Op minuut \(8\) draaien we de klok \(B\) die nog steeds loopt. Sinds hun herstart op minuut \(7\) is er precies zoveel zand naar beneden gestroomd als er in \(1\) minuut door het knelpunt zou passen. Na het keren ligt alleen deze kleine hoeveelheid er bovenop. Het duurt nu \(1\) minuut voordat het weer naar beneden druppelt. De klok wordt dus leeg op minuut \(9\) , en niet na nog een volledige run. We meten dus de laatste minuut met zand dat er al doorheen is gegaan. De animatie toont deze zet:
Het omdraaien van een lopende zandloper is ook handig voor de algemene oplossing. Met resterende tijd bedoelen we de tijd die het zand nog nodig heeft om door te stromen in de bovenkamer. Als de volledige klok de looptijd \(c\) heeft en de resterende looptijd \(r\) is, dan komt de hoeveelheid zand onderaan overeen met de duur \(cr\) . Als je hem omdraait, komt dit exacte bedrag bovenaan te staan. Als de bovenkamer vooraf vol is, is deze daarna leeg en omgekeerd. Voor een gedeeltelijk lopende klok is de nieuwe resterende looptijd \(r'\):
$$r'=c-r.$$
Voorheen begon de meting met de eerste beurt. Dit betekent ‘zonder doorlooptijd’: elke minuut sinds de start telt. “Met voorschot” betekent daarentegen dat u de klokken eerst kunt klaarzetten en dat de gewenste tijdsperiode later begint. We starten bijvoorbeeld beide klokken en draaien \(A\) om op minuut \(4\) . Als \(B\) leeg raakt op minuut \(7\) , begint onze meting. Als \(A\) leeg wordt op minuut \(8\) , eindigt het. We hebben \(1\) minuut gemeten; de voorgaande \(7\) minuten tellen niet mee.
Nu beschouwen we willekeurige zandlopers met een positieve gehele looptijd \(a\) en \(b\) . De gewenste duur noemen we \(T\) . Welke tijden kunnen hiermee gemeten worden als voorbereiding toegestaan is? Ook hier moeten het begin en het einde herkenbaar zijn aan een lege ruimte. Je moet dus niet op een gegeven moment gaan meten op basis van je gevoel. De handvatten blijven hetzelfde als bij de daadwerkelijke puzzel. Eerst laten we zien welke tijden uitgesloten zijn; dan laten we u zien hoe u de rest daadwerkelijk kunt meten.
Laten we eerst klokken nemen met \(6\) en \(10\) minuten. Beide looptijden zijn deelbaar door \(2\) . Het zand kan daarom mentaal in porties worden verdeeld, die elk \(2\) minuten nodig hebben om er doorheen te gaan. Wanneer je hem omdraait of wacht tot de volgende keer dat hij leeg is, ontstaan er weer alleen hele porties. Alle waarneembare leegstanden liggen dus een even aantal minuten uit elkaar. Je kunt er geen tijdsduur van \(3\) minuten mee meten, ook al zet je de klokken van tevoren zo lang klaar als je wilt.
In het algemeen geldt dat \(g=\gcd(a,b)\) de grootste gemene deler van de looptijden is. Aanvankelijk zijn beide resterende termen veelvouden van \(g\) . Bij rotatie wordt \(r\) \(ar\) of \(br\) ; beide blijven deelbaar door \(g\) . Bij het wachten verstrijkt de kleinste positieve resterende tijd, die ook een veelvoud is van \(g\) . Dit betekent dat alle lege tijden en hun afstanden veelvouden van \(g\) blijven. Een meetbare duur moet dus voldoen aan \(g\mid T\) : \(T\) moet deelbaar zijn door \(g\) . Of dat voldoende is, valt nog te bezien.
Om dit te doen, laten we beide klokken keer op keer volledig lopen en draaien we elke klok om zodra deze leeg is. De eerste wordt dan leeg na \(a,2a,3a,\ldots\) tijdseenheden, de tweede na \(b,2b,3b,\ldots\) . We zoeken een tijdstip \(mb\) van de tweede klok en een later tijdstip \(na\) van de eerste, waartussen precies \(T\) ligt. Het lemma van Bézout garandeert overeenkomende gehele getallen \(n,m\) als \(T\) een positief veelvoud is van \(g\) . De relatie die u zoekt is::
$$na-mb=T.$$
De door Bézout aangeleverde getallen \(n,m\) kunnen in eerste instantie negatief zijn. Negatieve runs kunnen niet worden uitgevoerd. Je kunt echter beide getallen verhogen zonder het tijdsinterval te veranderen: we vervangen ze door \(n+kb/g\) en \(m+ka/g\) , waarbij \(k\) een voldoende groot positief geheel getal is. Beide tijden worden dus met dezelfde hoeveelheid verschoven \(kab/g\) ; hun verschil blijft \(T\) . Beide getallen worden dus positief en de vereiste tijden zijn feitelijk nadat de klokken zijn gestart.
Nu tel je de volledige cycli van elke klok. Als de \(m\) klok leeg raakt, begint de meting; het eindigt wanneer de eerste klok voor de \(n\) -de keer leeg raakt. Er zitten precies \(T\) tijdseenheden tussen. De voorbereiding kan lang duren. Het bewijs belooft geen bijzonder kort proces. Voor \(T=0\) vallen begin en einde samen. Dit geldt voor alle niet-negatieve gehele doelstellingen: met voorbereiding kan een duur worden gemeten als en slechts als de grootste gemene deler deze deelt:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Deze regel is niet noodzakelijkerwijs van toepassing op het starten van metingen direct bij de eerste start. Bijvoorbeeld met \(4\) en \(7\) minuten \(g=1\) , maar na \(1\) minuut is geen klok leeg. Je kunt het einde van deze minuut dus niet zien. De hierboven beschreven meting van minuut \(7\) tot \(8\) werkt alleen omdat de voorbereiding niet meetelt. Het bewijs geeft daarmee antwoord op de vraag wat er na bereiding mogelijk is. Als u op zoek bent naar een toegestaan proces met of zonder voorbereiding, kan de volgende systematische zoekactie helpen.
Het PHP-script onthoudt zowel de resterende looptijden als de tijd die is verstreken sinds het begin van de meting. Probeer het allemaal voor al deze aandoeningen \(4\) Mogelijkheden: geen klok, alleen de eerste, alleen de tweede of beide omdraaien. Vervolgens wacht hij tot de volgende keer dat hij leegloopt. De waarde \(-1\) geeft voorbereiding aan; de binnenkomst start stelt de meettijd in \(0\). Bekende aandoeningen worden niet opnieuw onderzocht. De gevonden reeks wordt verkregen via zijn voorgangers. wait heeft alleen betrekking op de afstand tot de volgende lediging, geen extra tijdsmeting:
<?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;
}
De zoekopdracht vindt of retourneert een toegestaan proces null, als er geen bestaat. Het omvat alle toegestane voortzettingen en vergt een maximale voorbereiding \((a+1)(b+1)(T+2)\) Staten. Grote inputs vergen dus veel geheugen. Het aantal zoekovergangen wordt geminimaliseerd, niet de voorbereidingstijd. Rationele loop- en streeftijden worden omgezet in hele getallen met behulp van een gemeenschappelijke noemer. Bijvoorbeeld voor looptijden zonder gemeenschappelijke tijdseenheid \(1\) en \(\sqrt{2}\), deze eindige integer-zoekopdracht is niet geschikt.