Der er to timeglas: det ene kører helt på \(4\) minutter, det andet på \(7\) minutter. Hvordan måler man præcis \(9\) minutter, når målingen skal starte første gang urene startes? Et andet ur, at tælle sekunder og gætte er ikke tilladt. Alt du skal gøre er at vende timeglassene og se, når det øverste kammer er tomt. At vende om burde ikke tage nogen tid. Det, vi leder efter, er en proces, hvor slutningen af den ønskede tidsperiode udelukkende kan genkendes af timeglassene.
Vi kalder uret med \(4\) minutter \(A\) og det med \(7\) minutter \(B\) . Til at begynde med er alt sandet i bunden. Vi starter begge ure på samme tid ved at vende dem; Fra dette øjeblik og fremefter tæller de søgte \(9\) minutter. Herefter kan du altid handle, når et ur i toppen bliver tomt. Du må ikke vende det ene, det ene eller begge ure, heller ikke et der stadig kører. Du venter til næste gang den løber tør. Standsning og markering er ikke tilladt; et tomt ur kan blive stående. Løsningen ser sådan ud:
- Efter minut startes \(0\) \(A\) og \(B\) .
- I minut er \(4\) \(A\) tom og vendt. \(B\) fortsætter med at køre uændret.
- I minut er \(7\) \(B\) tom og vendt. Der er stadig \(1\) minut tilbage i \(A\) .
- I minut er \(8\) \(A\) tom. I \(B\) løb sand ned i nøjagtig \(1\) minut; derfor vendes \(B\) straks igen.
- I minut er \(9\) \(B\) tom. Det tidspunkt, du ledte efter, er nået.
I minut \(8\) vender vi uret \(B\) som stadig kører. Siden deres genstart i minut \(7\) , er nøjagtigt så meget sand strømmet ned, som ville passe gennem flaskehalsen på \(1\) minut. Efter vending er kun denne lille mængde på toppen. Det tager nu \(1\) minut at sive ned igen. Uret bliver derfor tomt ved minut \(9\) , ikke efter endnu en komplet kørsel. Så vi måler det sidste minut med sand, der allerede er passeret igennem. Animationen viser dette træk:
At vende et løbende timeglas er også nyttigt til den generelle løsning. Med resterende tid mener vi den tid, sandet stadig skal gennemstrømme i det øverste kammer. Hvis det fulde ur har køretiden \(c\) og dets resterende køretid er \(r\) , så svarer mængden af sand i bunden til varigheden \(cr\) . Når du vender det om, kommer dette nøjagtige beløb til tops. Hvis det øverste kammer er fyldt på forhånd, vil det være tomt bagefter og omvendt. For et delvist kørt ur er den nye resterende køretid \(r'\):
$$r'=c-r.$$
Tidligere startede målingen med første omgang. Det betyder "uden leveringstid": hvert minut siden starten tæller. "Med forhånd" betyder på den anden side, at du kan forberede urene først, og den ønskede tidsperiode begynder senere. For eksempel starter vi begge ure og vender \(A\) ved minut \(4\) . Hvis \(B\) bliver tom i minut \(7\) , begynder vores måling. Hvis \(A\) bliver tom i minut \(8\) , slutter den. Vi målte \(1\) minut; de foregående \(7\) minutter tæller ikke.
Nu betragter vi vilkårlige timeglas med positive heltals køretider \(a\) og \(b\) . Vi kalder den ønskede varighed \(T\) . Hvilke tider kan måles med dette, hvis forberedelse er tilladt? Også her skal begyndelsen og slutningen kunne kendes på et tomt rum. Så du bør ikke begynde at måle på et tidspunkt baseret på din følelse. Håndtagene forbliver de samme som i selve puslespillet. Først viser vi hvilke tider der er udelukket; så viser vi dig, hvordan du rent faktisk måler resten.
Lad os først tage ure med \(6\) og \(10\) minutter. Begge køretider er delelige med \(2\) . Sandet kan derfor mentalt opdeles i portioner, som hver tager \(2\) minutter at gå igennem. Når du vender den om eller venter til næste gang den er tom, bliver der kun skabt hele portioner igen. Alle observerbare tomme tider er derfor et lige antal minutter fra hinanden. Du kan ikke bruge den til at måle en varighed på \(3\) minutter, selvom du forbereder urene, så længe du vil på forhånd.
Lad generelt \(g=\gcd(a,b)\) være den største fælles divisor af køretiderne. Til at begynde med er begge resterende led multipla af \(g\) . Når den roteres \(r\) enten \(ar\) eller \(br\) ; begge forbliver delelige med \(g\) . Når man venter, går den mindste positive resterende tid, som også er et multiplum af \(g\) . Det betyder, at alle tomme tider og deres afstande forbliver multipla af \(g\) . En målbar varighed skal derfor opfylde \(g\mid T\) : \(T\) skal være delelig med \(g\) . Om det er nok skal vise sig.
For at gøre dette lader vi begge ure køre helt igen og igen og vender hver enkelt om, så snart det er tomt. Den første bliver så tom efter \(a,2a,3a,\ldots\) tidsenheder, den anden efter \(b,2b,3b,\ldots\) . Vi leder efter en tid \(mb\) for det andet ur og et senere tidspunkt \(na\) af det første, mellem hvilket nøjagtigt \(T\) ligger. Bézouts lemma garanterer matchende heltal \(n,m\) hvis \(T\) er et positivt multiplum af \(g\) . Det forhold du leder efter er::
$$na-mb=T.$$
Tallene \(n,m\) leveret af Bézout kan initialt være negative. Negative kørsler kan ikke udføres. Man kan dog øge begge tal uden at ændre tidsintervallet: vi erstatter dem med \(n+kb/g\) og \(m+ka/g\) , hvor \(k\) er et tilstrækkeligt stort positivt heltal. Begge tider forskydes derfor med samme mængde \(kab/g\) ; deres forskel forbliver \(T\) . Så begge tal bliver positive, og de nødvendige tider er faktisk efter urene starter.
Nu tæller du de komplette cyklusser for hvert ur. Når det \(m\) ur bliver tomt, begynder målingen; den slutter, når det første ur bliver tomt for \(n\) -te gang. Der er præcis \(T\) tidsenheder imellem. Forberedelsen kan tage lang tid. Beviset lover ikke en særlig kort proces. For \(T=0\) falder begyndelsen og slutningen sammen. Dette beviser for alle ikke-negative heltalsmål: Med forberedelse kan en varighed måles, hvis og kun hvis den største fælles divisor deler den:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Denne regel gælder ikke nødvendigvis for startmålinger lige ved første start. For eksempel med \(4\) og \(7\) minutter \(g=1\) , men efter \(1\) minut er intet ur tomt. Så du kan ikke se slutningen af dette minut. Målingen fra minut \(7\) til \(8\) beskrevet ovenfor virker kun, fordi forberedelsen ikke tæller. Beviset besvarer således spørgsmålet om, hvad der er muligt efter forberedelse. Hvis du leder efter en tilladt proces med eller uden forberedelse, vil følgende systematiske søgning hjælpe.
PHP-scriptet husker både resterende køretider og den tid, der er forløbet siden starten af målingen. For hver sådan tilstand, prøv det hele \(4\) Muligheder: intet ur, kun det første, kun det andet eller vend begge dele. Så venter den til næste gang den tømmes. Værdien \(-1\) angiver forberedelse; indgangen start indstiller måletiden \(0\). Kendte forhold vil ikke blive genundersøgt. Den fundne sekvens er opnået via sine forgængere. wait henviser kun til afstanden til næste tømning, ikke en ekstra tidsmåling:
<?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øgningen finder eller returnerer en tilladt proces null, hvis ingen eksisterer. Den dækker alle tilladte fortsættelser og kræver maksimalt forberedelse \((a+1)(b+1)(T+2)\) Stater. Store input kræver derfor meget hukommelse. Antallet af søgeovergange er minimeret, ikke forberedelsestiden. Rationelle løbe- og måltider konverteres til hele tal ved hjælp af en fællesnævner. For køretider uden fælles tidsenhed, f.eks \(1\) og \(\sqrt{2}\), denne endelige heltalssøgning er ikke egnet.