Két homokóra van: az egyik \(4\) perc alatt fut le teljesen, a másik \(7\) perc alatt. Hogyan mérhet pontosan \(9\) percet, amikor a mérést az órák első indításakor el kell kezdeni? Más óra, másodpercek számolása és találgatás nem megengedett. Csak annyit kell tennie, hogy megfordítja a homokórát, és figyeli, mikor üres a felső kamra. A megfordulás nem tarthat sokáig. Olyan folyamatot keresünk, amelyben a kívánt időtartam végét kizárólag a homokórák ismerhetik fel.
\(4\) perces órát \(A\) , a \(7\) percet \(B\) hívjuk. Kezdetben az összes homok az alján van. Mindkét órát egyszerre indítjuk elfordítással; Ettől a pillanattól kezdve a keresett \(9\) perc számít. Ezt követően mindig kereskedhet, ha a tetején lévő óra üres lesz. Nem fordíthatja meg az egyik, az egyik vagy mindkét órát, még azt sem, amelyik még mindig működik. Megvárod, amíg a következő alkalommal elfogy. Megállás és jelölés nem megengedett; egy üres óra állva maradhat. A megoldás így néz ki:
- \(0\) percben \(A\) és \(B\) elindul.
- \(4\) percben \(A\) üres, és át van fordítva. \(B\) változatlan formában fut tovább.
- A \(7\) percben \(B\) üres és meg van fordítva. Még \(1\) perc van hátra \(A\) .
- A \(8\) percben \(A\) üres. \(B\) -ben pontosan \(1\) percig folyt le a homok; ezért \(B\) azonnal újra megfordul.
- A \(9\) percben \(B\) üres. Elérkezett a keresett idő.
A \(8\) percben megfordítjuk a \(B\) amely még mindig fut. Mivel a \(7\) pontosan annyi homok folyt le, amennyi \(1\) perc alatt átfért a szűk keresztmetszeten. Tekergetés után már csak ez a kis mennyiség van a tetején. Most \(1\) percbe telik, amíg újra lecsöpög. Az óra tehát a \(9\) percben válik üressé, nem pedig egy újabb teljes futás után. Tehát az utolsó percet a már átjárt homokkal mérjük. Az animáció ezt a lépést mutatja:
A futó homokóra megfordítása is hasznos az általános megoldáshoz. A hátralévő idő alatt azt az időt értjük, ameddig a homoknak még át kell folynia a felső kamrában. Ha a teljes óra futási ideje \(c\) és hátralévő futásideje \(r\) , akkor az alsó homok mennyisége megfelel a \(cr\) időtartamnak. Amikor megfordítja, pontosan ez az összeg jön a tetejére. Ha a felső kamra előtte megtelt, utána üres lesz, és fordítva. Részben futott óra esetén az új hátralévő futási idő \(r'\):
$$r'=c-r.$$
Korábban az első kanyarral kezdődött a mérés. Ez azt jelenti, hogy „átfutási idő nélkül”: a kezdés óta minden perc számít. Az „előleggel” viszont azt jelenti, hogy először az órákat készítheti elő, és a kívánt időtartam később kezdődik. Például elindítjuk mindkét órát, és \(A\) -t \(4\) percben fordítjuk. Ha \(B\) a \(7\) percben üres lesz, a mérés elkezdődik. Ha \(A\) \(8\) percben üres lesz, akkor véget ér. \(1\) percet mértünk; az előző \(7\) perc nem számít bele.
Most tetszőleges homokórákat tekintünk pozitív egész számokkal \(a\) és \(b\) futási időkkel. A kívánt időtartamot \(T\) -nek hívjuk. Milyen időket lehet ezzel mérni, ha megengedett a felkészülés? A kezdetnek és a végnek itt is felismerhetőnek kell lennie egy üres helyről. Tehát nem szabad valamikor elkezdeni a mérést az érzései alapján. A fogantyúk ugyanazok maradnak, mint a valódi puzzle-ben. Először megmutatjuk, mely időpontok vannak kizárva; majd megmutatjuk, hogyan kell ténylegesen mérni az összes többit.
Először vegyünk \(6\) és \(10\) perces órákat. Mindkét futási idő osztható \(2\) -vel. A homokot ezért gondolatban részekre lehet osztani, amelyek mindegyike \(2\) percet vesz igénybe. Amikor megfordítja, vagy megvárja, amíg a következő alkalommal kiürül, csak a teljes részek jönnek létre újra. Ezért az összes megfigyelhető üres idő páros számú perc eltéréssel van egymástól. Nem mérhetsz vele \(3\) perces időtartamot, még akkor sem, ha előtte tetszés szerint készíted elő az órákat.
Általában legyen \(g=\gcd(a,b)\) a futási idők legnagyobb közös osztója. Kezdetben mindkét fennmaradó tag a \(g\) többszöröse. Ha elforgatjuk \(r\) \(ar\) vagy \(br\) lesz; mindkettő osztható marad \(g\) -vel. Várakozáskor a legkisebb pozitív hátralévő idő telik el, ami szintén \(g\) többszöröse. Ez azt jelenti, hogy minden üres idő és távolságuk \(g\) többszöröse marad. A mérhető időtartamnak tehát ki kell elégítenie \(g\mid T\) : \(T\) oszthatónak kell lennie \(g\) -vel. Hogy ez elég-e, az majd kiderül.
Ehhez mindkét órát hagyjuk újra és újra teljesen járni, és mindegyiket megfordítjuk, amint kiürült. Ezután az első üres lesz \(a,2a,3a,\ldots\) időegység után, a második pedig \(b,2b,3b,\ldots\) után. A második óra \(mb\) időpontját és az első \(na\) későbbi időpontját keressük, amelyek között pontosan \(T\) található. A Bézout-féle lemma garantálja a \(n,m\) megfelelő egész számokat, ha \(T\) \(g\) pozitív többszöröse. A keresett kapcsolat a következő::
$$na-mb=T.$$
A Bézout által megadott \(n,m\) számok kezdetben negatívak is lehetnek. Negatív futtatások nem hajthatók végre. Mindazonáltal mindkét szám növelhető az időintervallum megváltoztatása nélkül: helyettesítjük őket \(n+kb/g\) és \(m+ka/g\) -vel, ahol \(k\) egy kellően nagy pozitív egész szám. Mindkét idő tehát azonos mértékben tolódik el \(kab/g\) ; különbségük marad \(T\) . Így mindkét szám pozitív lesz, és a szükséges idők valójában az órák indulása után vannak.
Most megszámolja az egyes órák teljes ciklusait. Amikor a \(m\) óra kiürül, a mérés megkezdődik; akkor ér véget, amikor az első óra \(n\) -edik alkalommal kiürül. Pontosan \(T\) időegység van a kettő között. Az előkészítés sokáig tarthat. A bizonyítás nem ígér különösebben rövid folyamatot. \(T=0\) esetén a kezdet és a vége egybeesik. Ez minden nem-negatív egész célnál bizonyítja: előkészítéssel akkor és csak akkor mérhető az időtartam, ha a legnagyobb közös osztó osztja.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Ez a szabály nem feltétlenül vonatkozik az első indításnál kezdődő mérésekre. Például \(4\) és \(7\) percekkel \(g=1\) , de \(1\) perc után egyetlen óra sem üres. Tehát nem látja ennek a percnek a végét. A fent leírt \(7\) perctől \(8\) ig történő mérés csak azért működik, mert a felkészülés nem számít. A bizonyítás tehát választ ad arra a kérdésre, hogy mi lehetséges az előkészítés után. Ha egy engedélyezett folyamatot keres előkészítéssel vagy anélkül, a következő szisztematikus keresés segít.
A PHP szkript megjegyzi a hátralévő futási időket és a mérés kezdete óta eltelt időt is. Minden ilyen állapot esetén próbálja ki az összeset \(4\) Lehetőségek: nincs óra, csak az első, csak a második vagy fordítsd meg mindkettőt. Ezután megvárja a következő kiürülést. Az érték \(-1\) előkészítést jelez; a bejegyzést start beállítja a mérési időt \(0\). Az ismert körülményeket nem vizsgálják újra. A talált szekvenciát az elődjein keresztül kaptuk meg. wait csak a következő ürítés távolságára vonatkozik, további időmérésre nem:
<?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;
}
A keresés engedélyezett folyamatot talál vagy ad vissza null, ha egyik sem létezik. Lefedi az összes engedélyezett folytatást, és maximális felkészülést igényel \((a+1)(b+1)(T+2)\) Államok. A nagy bemenetek ezért sok memóriát igényelnek. A keresési átmenetek száma minimalizálva van, nem az előkészítési idő. A racionális futási és célidőket egy közös nevező segítségével egész számokká alakítják át. Például közös időegység nélküli futási időkre \(1\) és \(\sqrt{2}\), ez a véges egész keresés nem alkalmas.