Det finns två timglas: det ena går helt på \(4\) minuter, det andra på \(7\) minuter. Hur mäter man exakt \(9\) minuter när mätningen ska starta första gången klockorna startas? En annan klocka, att räkna sekunder och gissa är inte tillåtet. Allt du behöver göra är att vända timglasen och se när den övre kammaren är tom. Att vända sig om borde inte ta någon tid. Det vi letar efter är en process där slutet av den önskade tidsperioden kan kännas igen enbart av timglasen.
Vi kallar klockan med \(4\) minuter \(A\) och den med \(7\) minuter \(B\) . Till en början finns all sand på botten. Vi startar båda klockorna samtidigt genom att vända på dem; Från detta ögonblick och framåt räknas de sökta \(9\) minuterna. Därefter kan du alltid handla när en klocka på toppen blir tom. Du får inte vända på en, en eller båda klockorna, inte ens en som fortfarande är igång. Du väntar tills nästa gång det tar slut. Det är inte tillåtet att stanna och markera; en tom klocka kan bli stående. Lösningen ser ut så här:
- I minuten startas \(0\) \(A\) och \(B\) .
- Vid minut är \(4\) \(A\) tom och vänds. \(B\) fortsätter att köras oförändrat.
- Vid minut är \(7\) \(B\) tom och vänds. Det är fortfarande \(1\) minut kvar i \(A\) .
- Vid minut är \(8\) \(A\) tom. I \(B\) rann sand ner i exakt \(1\) minut; därför vänds \(B\) omedelbart igen.
- Vid minut är \(9\) \(B\) tom. Tiden du letade efter har nåtts.
Vid minut \(8\) vrider vi på klockan \(B\) som fortfarande går. Sedan deras omstart vid minut \(7\) har exakt så mycket sand runnit ner som skulle passa genom flaskhalsen på \(1\) minut. Efter vändning är bara denna lilla mängd på toppen. Det tar nu \(1\) minut att sippra ner igen. Klockan blir därför tom vid minut \(9\) , inte efter ytterligare en fullständig körning. Så vi mäter sista minuten med sand som redan passerat igenom. Animationen visar detta drag:
Att vända ett löpande timglas är också användbart för den allmänna lösningen. Med återstående tid menar vi den tid som sanden fortfarande behöver rinna igenom i den övre kammaren. Om hela klockan har gångtiden \(c\) och dess återstående gångtid är \(r\) , så motsvarar mängden sand i botten varaktigheten \(cr\) . När du vänder på det kommer denna exakta summa till toppen. Om den övre kammaren är full i förväg kommer den att vara tom efteråt och vice versa. För en delvis körd klocka är den nya återstående gångtiden \(r'\):
$$r'=c-r.$$
Tidigare började mätningen med första svängen. Det betyder "utan ledtid": varje minut sedan starten räknas. "Med förskott" betyder å andra sidan att du kan förbereda klockorna först och den önskade tidsperioden börjar senare. Till exempel startar vi båda klockorna och vänder \(A\) vid minut \(4\) . Om \(B\) blir tom vid minut \(7\) börjar vår mätning. Om \(A\) blir tom vid minut \(8\) , slutar det. Vi mätte \(1\) minut; de föregående \(7\) minuterna räknas inte.
Nu betraktar vi godtyckliga timglas med positiva heltalskörtider \(a\) och \(b\) . Vi kallar den önskade varaktigheten \(T\) . Vilka tider kan mätas med detta om förberedelse tillåts? Även här måste början och slutet kunna kännas igen på ett tomt utrymme. Så du ska inte börja mäta någon gång utifrån din känsla. Handtagen förblir desamma som i själva pusslet. Först visar vi vilka tider som är exkluderade; sedan visar vi dig hur du faktiskt mäter resten.
Låt oss först ta klockor med \(6\) och \(10\) minuter. Båda körtiderna är delbara med \(2\) . Sanden kan därför mentalt delas upp i portioner, som var och en tar \(2\) minuter att gå igenom. När du vänder på den eller väntar tills nästa gång den är tom skapas bara hela portioner igen. Alla observerbara tomtider skiljer sig därför med ett jämnt antal minuter. Du kan inte använda den för att mäta en längd på \(3\) minuter, även om du förbereder klockorna så länge du vill i förväg.
I allmänhet, låt \(g=\gcd(a,b)\) vara den största gemensamma delaren av körtiderna. Inledningsvis är båda återstående termerna multiplar av \(g\) . När den roteras blir \(r\) antingen \(ar\) eller \(br\) ; båda förblir delbara med \(g\) . Vid väntan går den minsta positiva återstående tiden, vilket också är en multipel av \(g\) . Detta innebär att alla tomma tider och deras avstånd förblir multiplar av \(g\) . En mätbar varaktighet måste därför uppfylla \(g\mid T\) : \(T\) måste vara delbar med \(g\) . Om det räcker återstår att se.
För att göra detta låter vi båda klockorna gå helt om och om igen och vänder på var och en så fort den är tom. Den första blir sedan tom efter \(a,2a,3a,\ldots\) tidsenheter, den andra efter \(b,2b,3b,\ldots\) . Vi letar efter en tid \(mb\) för den andra klockan och en senare tid \(na\) för den första, mellan vilken exakt \(T\) ligger. Bézouts lemma garanterar matchande heltal \(n,m\) om \(T\) är en positiv multipel av \(g\) . Relationen du letar efter är::
$$na-mb=T.$$
Siffrorna \(n,m\) som tillhandahålls av Bézout kan initialt vara negativa. Negativa körningar kan inte utföras. Man kan dock öka båda talen utan att ändra tidsintervallet: vi ersätter dem med \(n+kb/g\) och \(m+ka/g\) , där \(k\) är ett tillräckligt stort positivt heltal. Båda tiderna förskjuts därför lika mycket \(kab/g\) ; deras skillnad kvarstår \(T\) . Så båda siffrorna blir positiva och de nödvändiga tiderna är faktiskt efter att klockorna startar.
Nu räknar du hela cyklerna för varje klocka. När den \(m\) klockan blir tom börjar mätningen; den slutar när den första klockan blir tom för \(n\) -te gången. Det finns exakt \(T\) tidsenheter emellan. Förberedelserna kan ta lång tid. Beviset lovar inte en särskilt kort process. För \(T=0\) sammanfaller början och slutet. Detta bevisar för alla icke-negativa heltalsmål: Med förberedelse kan en varaktighet mätas om och endast om den största gemensamma delaren delar den:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Denna regel gäller inte nödvändigtvis för startmätningar direkt vid första start. Till exempel, med \(4\) och \(7\) minuter \(g=1\) , men efter \(1\) minut är ingen klocka tom. Så du kan inte se slutet på denna minut. Mätningen från minut \(7\) till \(8\) som beskrivs ovan fungerar bara eftersom förberedelsen inte räknas. Beviset svarar alltså på frågan om vad som är möjligt efter förberedelse. Om du letar efter en tillåten process med eller utan förberedelser hjälper följande systematiska sökning.
PHP-skriptet kommer ihåg både återstående körtider och tiden som har förflutit sedan mätningens början. För varje sådant tillstånd, prova allt \(4\) Möjligheter: ingen klocka, bara den första, bara den andra eller vänd båda. Den väntar sedan tills nästa gång den töms. Värdet \(-1\) indikerar förberedelse; posten start ställer in mättiden \(0\). Kända förhållanden kommer inte att utredas på nytt. Sekvensen som hittas erhålls via dess föregångare. wait avser endast avståndet till nästa tömning, inte en extra tidsmätning:
<?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;
}
Sökningen hittar eller returnerar en tillåten process null, om ingen existerar. Den omfattar alla tillåtna fortsättningar och kräver maximal förberedelse \((a+1)(b+1)(T+2)\) Stater. Stora ingångar kräver därför mycket minne. Antalet sökövergångar minimeras, inte förberedelsetiden. Rationella löptider och måltider omvandlas till heltal med hjälp av en gemensam nämnare. För körtider utan en gemensam tidsenhet, till exempel \(1\) och \(\sqrt{2}\), denna finita heltalssökning är inte lämplig.