Hay dos relojes de arena: uno funciona completamente en \(4\) minutos y el otro en \(7\) minutos. ¿Cómo se miden exactamente \(9\) minutos cuando la medición debe comenzar la primera vez que se ponen en marcha los relojes? No se permite otro reloj, contar segundos ni adivinar. Todo lo que tienes que hacer es girar los relojes de arena y observar cuando la cámara superior está vacía. Dar la vuelta no debería llevar mucho tiempo. Lo que buscamos es un proceso en el que el final del período de tiempo deseado pueda ser reconocido únicamente por los relojes de arena.
Al reloj de \(4\) minutos lo llamamos \(A\) y al de \(7\) minutos lo llamamos \(B\) . Inicialmente toda la arena está en el fondo. Ponemos en marcha ambos relojes a la vez dándoles la vuelta; A partir de este momento cuentan los \(9\) minutos buscados. Después de eso, siempre podrás operar cuando el reloj en la parte superior se quede vacío. No se podrá dar vuelta a uno, ni a uno ni a ambos relojes, ni siquiera uno que esté todavía en marcha. Esperas hasta la próxima vez que se acabe. No se permiten detenerse ni marcar; un reloj vacío puede permanecer en pie. La solución se ve así:
- En el minuto se inician \(0\) \(A\) y \(B\) .
- En el minuto \(4\) \(A\) está vacío y se voltea. \(B\) continúa ejecutándose sin cambios.
- En el minuto \(7\) \(B\) está vacío y se voltea. Todavía queda \(1\) minuto en \(A\) .
- En el minuto \(8\) \(A\) está vacío. En \(B\) la arena corrió durante exactamente \(1\) minuto; por lo tanto \(B\) se voltea inmediatamente nuevamente.
- En el minuto \(9\) \(B\) está vacío. Se ha llegado a la hora que buscabas.
En el minuto \(8\) damos la vuelta al reloj \(B\) que todavía está en marcha. Desde su reinicio en el minuto \(7\) , ha fluido exactamente tanta arena como cabría a través del cuello de botella en \(1\) minuto. Después de darle la vuelta, solo queda esta pequeña cantidad encima. Ahora tarda \(1\) minuto en volver a bajar. Por lo tanto, el reloj se vacía en el minuto \(9\) , no después de otra ejecución completa. Así que medimos el último minuto con arena que ya pasó. La animación muestra este movimiento.:
Voltear un reloj de arena en funcionamiento también es útil para la solución general. Por tiempo restante nos referimos al tiempo que la arena aún necesita para fluir en la cámara superior. Si el reloj completo tiene el tiempo de funcionamiento \(c\) y el tiempo de funcionamiento restante es \(r\) , entonces la cantidad de arena en el fondo corresponde a la duración \(cr\) . Cuando le das la vuelta, esta cantidad exacta llega a la cima. Si la cámara superior está llena antes, después estará vacía y viceversa. Para un reloj parcialmente ejecutado, el nuevo tiempo de ejecución restante es \(r'\):
$$r'=c-r.$$
Anteriormente, la medición comenzaba con la primera vuelta. Esto significa “sin plazo de entrega”: cada minuto desde el inicio cuenta. “Con antelación” significa, por otro lado, que puedes preparar los relojes primero y empezar después el periodo de tiempo deseado. Por ejemplo, ponemos en marcha ambos relojes y giramos \(A\) en el minuto \(4\) . Si \(B\) se vacía en el minuto \(7\) , comienza nuestra medición. Si \(A\) queda vacío en el minuto \(8\) , termina. Medimos \(1\) minuto; los \(7\) minutos anteriores no cuentan.
Ahora consideramos relojes de arena arbitrarios con tiempos de ejecución enteros positivos \(a\) y \(b\) . A la duración deseada la llamamos \(T\) . ¿Qué tiempos se pueden medir con esto si se permite la preparación? También en este caso el principio y el final deben ser reconocibles mediante un espacio vacío. Por lo tanto, no deberías empezar a medir en algún momento según tus sensaciones. Los mangos siguen siendo los mismos que en el rompecabezas real. Primero mostramos qué tiempos están excluidos; luego le mostraremos cómo medir el resto.
Primero tomemos relojes con \(6\) y \(10\) minutos. Ambos tiempos de ejecución son divisibles por \(2\) . Por lo tanto, la arena se puede dividir mentalmente en porciones, cada una de las cuales tarda \(2\) minutos en pasar. Cuando le das la vuelta o esperas hasta la próxima vez que esté vacío, solo se vuelven a crear porciones enteras. Por lo tanto, todos los tiempos de vacío observables están separados por un número par de minutos. No puedes usarlo para medir una duración de \(3\) minutos, incluso si preparas los relojes todo el tiempo que quieras de antemano.
En general, sea \(g=\gcd(a,b)\) el máximo común divisor de los tiempos de ejecución. Inicialmente, los dos términos restantes son múltiplos de \(g\) . Cuando se gira \(r\) se convierte en \(ar\) o \(br\) ; ambos permanecen divisibles por \(g\) . Al esperar, transcurre el tiempo restante positivo más pequeño, que también es un múltiplo de \(g\) . Esto significa que todos los tiempos vacíos y sus distancias siguen siendo múltiplos de \(g\) . Por lo tanto, una duración mensurable debe satisfacer \(g\mid T\) : \(T\) debe ser divisible por \(g\) . Queda por ver si eso es suficiente.
Para ello dejamos correr ambos relojes completamente una y otra vez y le damos la vuelta a cada uno en cuanto se vacía. El primero luego queda vacío después de \(a,2a,3a,\ldots\) unidades de tiempo, el segundo después de \(b,2b,3b,\ldots\) . Buscamos un tiempo \(mb\) del segundo reloj y un tiempo posterior \(na\) del primero, entre los cuales se encuentra exactamente \(T\) . El lema de Bézout garantiza la coincidencia de números enteros \(n,m\) si \(T\) es un múltiplo positivo de \(g\) . La relación que buscas es::
$$na-mb=T.$$
Los números \(n,m\) proporcionados por Bézout pueden ser inicialmente negativos. No se pueden realizar tiradas negativas. Sin embargo, se pueden aumentar ambos números sin cambiar el intervalo de tiempo: los reemplazamos con \(n+kb/g\) y \(m+ka/g\) , donde \(k\) es un entero positivo suficientemente grande. Por lo tanto, ambos tiempos se desplazan en la misma cantidad \(kab/g\) ; su diferencia sigue siendo \(T\) . Entonces ambos números se vuelven positivos y los tiempos requeridos son en realidad después de que se inician los relojes.
Ahora cuentas los ciclos completos de cada reloj. Cuando el \(m\) reloj se vacía, comienza la medición; termina cuando el primer reloj queda vacío por \(n\) -ésima vez. Hay exactamente \(T\) unidades de tiempo intermedias. La preparación puede llevar mucho tiempo. La prueba no promete un proceso particularmente corto. Para \(T=0\) el principio y el final coinciden. Esto se demuestra para todos los objetivos de números enteros no negativos: con preparación, una duración se puede medir si y sólo si el máximo común divisor la divide.:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Esta regla no se aplica necesariamente a las mediciones iniciales desde el primer inicio. Por ejemplo, con \(4\) y \(7\) minutos \(g=1\) , pero después de \(1\) minuto ningún reloj está vacío. Entonces no puedes ver el final de este minuto. La medición del minuto \(7\) al \(8\) descrita anteriormente solo funciona porque la preparación no cuenta. La prueba responde así a la pregunta de qué es posible después de la preparación. Si está buscando un proceso permitido con o sin preparación, la siguiente búsqueda sistemática le resultará útil.
El script PHP recuerda tanto los tiempos de ejecución restantes como el tiempo transcurrido desde el inicio de la medición. Para cada una de estas condiciones, pruébelo todo \(4\) Posibilidades: sin reloj, solo el primero, solo el segundo o darle la vuelta a ambos. Luego espera hasta la próxima vez que se vacía. el valor \(-1\) indica preparación; la entrada start establece el tiempo de medición \(0\). Las condiciones conocidas no se volverán a investigar. La secuencia encontrada se obtiene a través de sus predecesoras. wait solo se refiere a la distancia hasta el siguiente vaciado, no a una medición de tiempo adicional:
<?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 búsqueda encuentra o devuelve un proceso permitido. null, si no existe ninguno. Cubre todas las continuaciones permitidas y requiere un máximo de preparación. \((a+1)(b+1)(T+2)\) Estados. Por lo tanto, las entradas grandes requieren mucha memoria. Se minimiza el número de transiciones de búsqueda, no el tiempo de preparación. Los tiempos de ejecución racional y objetivo se convierten a números enteros utilizando un denominador común. Para tiempos de ejecución sin una unidad de tiempo común, por ejemplo \(1\) y \(\sqrt{2}\), Esta búsqueda de enteros finitos no es adecuada.