Ci sono due clessidre: una funziona completamente in \(4\) minuti, l'altra in \(7\) minuti. Come si misurano esattamente \(9\) minuti quando la misurazione deve iniziare la prima volta che si avviano gli orologi? Non sono ammessi un altro orologio, il conteggio dei secondi e l'ipotesi. Tutto quello che devi fare è capovolgere le clessidre e osservare quando la camera superiore è vuota. Girarsi non dovrebbe richiedere molto tempo. Ciò che cerchiamo è un processo in cui la fine del periodo di tempo desiderato possa essere riconosciuta esclusivamente dalle clessidre.
Chiamiamo l'orologio con \(4\) minuti \(A\) e quello con \(7\) minuti \(B\) . Inizialmente tutta la sabbia è sul fondo. Avviamo entrambi gli orologi contemporaneamente capovolgendoli; Da questo momento contano i \(9\) minuti ricercati. Successivamente, puoi sempre fare trading quando l'orologio in alto diventa vuoto. Non puoi girare uno, uno o entrambi gli orologi, nemmeno uno ancora in funzione. Aspetti fino alla prossima esaurimento. Non sono consentiti arresti e marcature; un orologio vuoto può restare in piedi. La soluzione è simile a questa:
- Al minuto \(0\) \(A\) e \(B\) vengono avviati.
- Al minuto \(4\) \(A\) è vuoto e viene capovolto. \(B\) continua a funzionare invariato.
- Al minuto \(7\) \(B\) è vuoto e viene capovolto. Manca ancora \(1\) minuto in \(A\) .
- Al minuto \(8\) \(A\) è vuoto. In \(B\) la sabbia è scesa esattamente per \(1\) minuto; quindi \(B\) viene immediatamente capovolto.
- Al minuto \(9\) \(B\) è vuoto. Il tempo che stavi cercando è stato raggiunto.
Al minuto \(8\) giriamo l'orologio \(B\) che è ancora in funzione. Dalla ripartenza al minuto \(7\) è defluita esattamente tanta sabbia quanta ne sarebbe passata attraverso il collo di bottiglia in \(1\) minuto. Dopo la svolta, solo questa piccola quantità rimane in cima. Adesso ci vuole \(1\) minuto per colare nuovamente verso il basso. L'orologio quindi si svuota al minuto \(9\) , non dopo un'altra corsa completa. Quindi misuriamo l'ultimo minuto con la sabbia che è già passata. L'animazione mostra questa mossa:
Per la soluzione generale è utile anche girare una clessidra in funzione. Per tempo rimanente intendiamo il tempo necessario alla sabbia per scorrere nella camera superiore. Se l'orologio completo ha il tempo di esecuzione \(c\) e il tempo di esecuzione rimanente è \(r\) , la quantità di sabbia sul fondo corrisponde alla durata \(cr\) . Quando lo giri, questo importo esatto arriva in cima. Se la camera superiore è piena prima, sarà vuota e viceversa. Per un orologio parzialmente funzionante, il nuovo tempo di esecuzione rimanente è \(r'\):
$$r'=c-r.$$
In precedenza, la misurazione iniziava con la prima svolta. Ciò significa “senza tempi di anticipo”: ogni minuto dalla partenza conta. “Con anticipo” significa invece che è possibile predisporre prima gli orologi e che il periodo desiderato inizierà più tardi. Ad esempio, avviamo entrambi gli orologi e giriamo \(A\) al minuto \(4\) . Se \(B\) si svuota al minuto \(7\) , inizia la nostra misurazione. Se \(A\) diventa vuoto al minuto \(8\) , termina. Abbiamo misurato \(1\) minuto; \(7\) minuti precedenti non contano.
Consideriamo ora clessidre arbitrarie con tempi di esecuzione interi positivi \(a\) e \(b\) . Chiamiamo la durata desiderata \(T\) . Quali tempi possono essere misurati con questo se la preparazione è consentita? Anche qui inizio e fine devono essere riconoscibili da uno spazio vuoto. Quindi non dovresti iniziare a misurare ad un certo punto in base alle tue sensazioni. Le maniglie rimangono le stesse del puzzle vero e proprio. Per prima cosa mostriamo quali orari sono esclusi; poi ti mostreremo come misurare effettivamente tutto il resto.
Per prima cosa prendiamo gli orologi con \(6\) e \(10\) minuti. Entrambi i tempi di esecuzione sono divisibili per \(2\) . La sabbia può quindi essere divisa mentalmente in porzioni, ciascuna delle quali impiega \(2\) minuti per essere attraversata. Quando lo giri o aspetti che sia vuoto la volta successiva, vengono create nuovamente solo porzioni intere. Tutti i tempi vuoti osservabili sono quindi distanti un numero pari di minuti. Non puoi usarlo per misurare una durata di \(3\) minuti, anche se prepari in anticipo gli orologi per tutto il tempo che desideri.
In generale, sia \(g=\gcd(a,b)\) il massimo comun divisore dei tempi di esecuzione. Inizialmente entrambi i termini rimanenti sono multipli di \(g\) . Quando ruotato \(r\) diventa \(ar\) o \(br\) ; entrambi rimangono divisibili per \(g\) . Durante l'attesa trascorre il tempo rimanente positivo più piccolo, che è anche un multiplo di \(g\) . Ciò significa che tutti i tempi vuoti e le loro distanze rimangono multipli di \(g\) . Una durata misurabile deve quindi soddisfare \(g\mid T\) : \(T\) deve essere divisibile per \(g\) . Resta da vedere se ciò sarà sufficiente.
Per fare ciò, lasciamo girare ancora e ancora entrambi gli orologi completamente e li giriamo non appena è vuoto. Il primo diventa quindi vuoto dopo \(a,2a,3a,\ldots\) unità di tempo, il secondo dopo \(b,2b,3b,\ldots\) . Cerchiamo un tempo \(mb\) del secondo orologio e un tempo successivo \(na\) del primo, tra i quali si trova esattamente \(T\) . Il lemma di Bézout garantisce la corrispondenza degli interi \(n,m\) se \(T\) è un multiplo positivo di \(g\) . La relazione che stai cercando è::
$$na-mb=T.$$
I numeri \(n,m\) forniti da Bézout possono inizialmente essere negativi. Non è possibile eseguire corse negative. Tuttavia, è possibile aumentare entrambi i numeri senza modificare l'intervallo di tempo: li sostituiamo con \(n+kb/g\) e \(m+ka/g\) , dove \(k\) è un numero intero positivo sufficientemente grande. Entrambi i tempi vengono quindi spostati della stessa quantità \(kab/g\) ; la loro differenza rimane \(T\) . Quindi entrambi i numeri diventano positivi e i tempi richiesti sono effettivamente successivi all'avvio degli orologi.
Ora conti i cicli completi di ciascun orologio. Quando il \(m\) orologio si svuota, inizia la misurazione; termina quando il primo orologio si svuota per la \(n\) -esima volta. Ci sono esattamente \(T\) unità di tempo intermedie. La preparazione può richiedere molto tempo. La prova non promette un processo particolarmente breve. Per \(T=0\) l'inizio e la fine coincidono. Ciò vale per tutti gli obiettivi interi non negativi: con la preparazione, una durata può essere misurata se e solo se il massimo comun divisore la divide:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Questa regola non si applica necessariamente all'avvio delle misurazioni subito al primo avvio. Ad esempio, con \(4\) e \(7\) minuti \(g=1\) , ma dopo \(1\) minuto nessun orologio è vuoto. Quindi non puoi vedere la fine di questo minuto. La misurazione dai minuti \(7\) a \(8\) sopra descritta funziona solo perché la preparazione non conta. La dimostrazione risponde quindi alla domanda su cosa è possibile dopo la preparazione. Se stai cercando un processo consentito con o senza preparazione, la seguente ricerca sistematica ti aiuterà.
Lo script PHP ricorda sia i tempi di esecuzione rimanenti che il tempo trascorso dall'inizio della misurazione. Per ciascuna di queste condizioni, prova tutto \(4\) Possibilità: nessun orologio, solo il primo, solo il secondo oppure girarli entrambi. Quindi attende fino al prossimo svuotamento. Il valore \(-1\) indica preparazione; l'entrata start imposta il tempo di misurazione \(0\). Le condizioni note non verranno riesaminate. La sequenza trovata è ottenuta tramite i suoi predecessori. wait si riferisce solo alla distanza fino allo svuotamento successivo, non a una misurazione del tempo aggiuntiva:
<?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;
}
La ricerca trova o restituisce un processo consentito null, se non ne esiste nessuno. Copre tutte le continuazioni consentite e richiede la massima preparazione \((a+1)(b+1)(T+2)\) Stati. Gli input di grandi dimensioni richiedono quindi molta memoria. Il numero di transizioni di ricerca è ridotto al minimo, non il tempo di preparazione. I tempi di corsa razionali e di destinazione vengono convertiti in numeri interi utilizzando un denominatore comune. Ad esempio per tempi di esecuzione senza unità di tempo comune \(1\) e \(\sqrt{2}\), questa ricerca di numeri interi finiti non è adatta.