Il existe deux sabliers : l'un s'exécute complètement en \(4\) minutes, l'autre en \(7\) minutes. Comment mesurer exactement \(9\) minutes alors que la mesure doit démarrer au premier démarrage des horloges ? Une autre horloge, compter les secondes et deviner ne sont pas autorisés. Il suffit de retourner les sabliers et de surveiller quand la chambre haute est vide. Faire demi-tour ne devrait pas prendre de temps. Ce que nous recherchons, c'est un processus dans lequel la fin de la période souhaitée puisse être reconnue uniquement par les sabliers.
On appelle l'horloge avec \(4\) minutes \(A\) et celle avec \(7\) minutes \(B\) . Au départ, tout le sable est au fond. On fait démarrer les deux horloges en même temps en les retournant ; A partir de ce moment, les \(9\) minutes recherchées comptent. Après cela, vous pouvez toujours échanger lorsqu'une horloge en haut devient vide. Vous ne pouvez pas retourner une, une ou les deux horloges, même celle qui est encore en marche. Vous attendez la prochaine fois qu'il n'y en a plus. L'arrêt et le marquage ne sont pas autorisés ; une horloge vide peut rester debout. La solution ressemble à ceci:
- À la minute \(0\) \(A\) et \(B\) sont démarrés.
- À la minute \(4\) \(A\) est vide et est retourné. \(B\) continue de fonctionner sans changement.
- À la minute \(7\) \(B\) est vide et est retourné. Il reste encore \(1\) minute dans \(A\) .
- À la minute \(8\) \(A\) est vide. Dans \(B\) le sable a coulé pendant exactement \(1\) minute ; donc \(B\) est immédiatement retourné.
- À la minute \(9\) \(B\) est vide. L'heure que vous recherchiez est atteinte.
A la minute \(8\) nous retournons l'horloge \(B\) qui est toujours en marche. Depuis leur redémarrage à la minute \(7\) , exactement autant de sable s'est écoulé qu'il en passerait par le goulot d'étranglement en \(1\) minute. Après avoir tourné, seule cette petite quantité se trouve sur le dessus. Il faut maintenant \(1\) minute pour redescendre. L'horloge devient donc vide à la minute \(9\) , pas après une autre exécution complète. On mesure donc la dernière minute avec du sable déjà passé. L'animation montre ce mouvement:
Retourner un sablier en marche est également utile pour la solution générale. Par temps restant, nous entendons le temps pendant lequel le sable doit encore s'écouler dans la chambre haute. Si l'horloge complète a la durée de fonctionnement \(c\) et que sa durée de fonctionnement restante est \(r\) , alors la quantité de sable au fond correspond à la durée \(cr\) . Lorsque vous le retournez, ce montant exact apparaît en haut. Si la chambre haute est pleine au préalable, elle sera vide ensuite et vice versa. Pour une horloge partiellement exécutée, le nouveau temps d'exécution restant est \(r'\):
$$r'=c-r.$$
Auparavant, la mesure démarrait au premier tour. Cela signifie « sans délai » : chaque minute depuis le départ compte. « Avec avance » signifie en revanche que vous pouvez d'abord préparer les horloges et que la période horaire souhaitée commence plus tard. Par exemple, nous démarrons les deux horloges et retournons \(A\) à la minute \(4\) . Si \(B\) devient vide à la minute \(7\) , notre mesure commence. Si \(A\) devient vide à la minute \(8\) , il se termine. Nous avons mesuré \(1\) minute ; les \(7\) minutes précédentes ne comptent pas.
Considérons maintenant des sabliers arbitraires avec des temps d'exécution entiers positifs \(a\) et \(b\) . Nous appelons la durée souhaitée \(T\) . Quels temps peut-on mesurer avec cela si la préparation est autorisée ? Ici aussi, le début et la fin doivent être reconnaissables à un espace vide. Vous ne devriez donc pas commencer à mesurer à un moment donné en fonction de votre ressenti. Les poignées restent les mêmes que dans le puzzle lui-même. Nous montrons d’abord quelles heures sont exclues ; nous vous montrerons ensuite comment mesurer réellement tout le reste.
Prenons d'abord des horloges avec \(6\) et \(10\) minutes. Les deux temps d'exécution sont divisibles par \(2\) . Le sable peut donc être divisé mentalement en portions, dont chacune prend \(2\) minutes à parcourir. Lorsque vous le retournez ou attendez qu'il soit vide la prochaine fois, seules des portions entières sont à nouveau créées. Tous les temps vides observables sont donc espacés d’un nombre pair de minutes. Vous ne pouvez pas l'utiliser pour mesurer une durée de \(3\) minutes, même si vous préparez au préalable les horloges aussi longtemps que vous le souhaitez.
En général, soit \(g=\gcd(a,b)\) le plus grand diviseur commun des temps d'exécution. Initialement, les deux termes restants sont des multiples de \(g\) . Lors d'une rotation \(r\) devient soit \(ar\) soit \(br\) ; les deux restent divisibles par \(g\) . Lors de l'attente, le plus petit temps restant positif s'écoule, qui est également un multiple de \(g\) . Cela signifie que tous les temps vides et leurs distances restent des multiples de \(g\) . Une durée mesurable doit donc satisfaire \(g\mid T\) : \(T\) doit être divisible par \(g\) . Reste à savoir si cela sera suffisant.
Pour ce faire, nous laissons les deux horloges fonctionner complètement encore et encore et les retournons chacune dès qu'elles sont vides. Le premier devient alors vide après \(a,2a,3a,\ldots\) unités de temps, le second après \(b,2b,3b,\ldots\) . Nous recherchons une heure \(mb\) de la deuxième horloge et une heure ultérieure \(na\) de la première, entre lesquelles se situe exactement \(T\) . Le lemme de Bézout garantit la correspondance des entiers \(n,m\) si \(T\) est un multiple positif de \(g\) . La relation que vous recherchez est ::
$$na-mb=T.$$
Les nombres \(n,m\) fournis par Bézout peuvent être initialement négatifs. Les analyses négatives ne peuvent pas être effectuées. Cependant, on peut augmenter les deux nombres sans changer l'intervalle de temps : on les remplace par \(n+kb/g\) et \(m+ka/g\) , où \(k\) est un entier positif suffisamment grand. Les deux temps sont donc décalés du même montant \(kab/g\) ; leur différence reste \(T\) . Ainsi, les deux nombres deviennent positifs et les heures requises se situent en réalité après le démarrage des horloges.
Maintenant, vous comptez les cycles complets de chaque horloge. Lorsque la \(m\) horloge devient vide, la mesure commence ; il se termine lorsque la première horloge devient vide pour la \(n\) -ème fois. Il y a exactement \(T\) unités de temps entre les deux. La préparation peut prendre beaucoup de temps. La preuve ne promet pas un processus particulièrement court. Pour \(T=0\) le début et la fin coïncident. Cela se vérifie pour tous les objectifs entiers non négatifs : Avec préparation, une durée peut être mesurée si et seulement si le plus grand commun diviseur la divise:
$$T\text{ ist messbar}\quad\Longleftrightarrow\quad \gcd(a,b)\mid T.$$
Cette règle ne s'applique pas nécessairement au démarrage des mesures dès le premier démarrage. Par exemple, avec \(4\) et \(7\) minutes \(g=1\) , mais après \(1\) minute aucune horloge n'est vide. Vous ne pouvez donc pas voir la fin de cette minute. La mesure de la minute \(7\) à \(8\) décrite ci-dessus ne fonctionne que parce que la préparation ne compte pas. La preuve répond ainsi à la question de savoir ce qui est possible après préparation. Si vous recherchez un processus autorisé avec ou sans préparation, la recherche systématique suivante vous aidera.
Le script PHP mémorise à la fois les temps d'exécution restants et le temps écoulé depuis le début de la mesure. Pour chacune de ces conditions, essayez tout \(4\) Possibilités : pas d'horloge, seulement la première, seulement la seconde ou retourner les deux. Il attend ensuite la prochaine fois qu'il se vide. La valeur \(-1\) indique la préparation ; l'entrée start règle le temps de mesure \(0\). Les conditions connues ne feront pas l’objet d’une nouvelle enquête. La séquence trouvée est obtenue via ses prédécesseurs. wait se réfère uniquement à la distance jusqu'à la prochaine vidange, pas à une mesure de temps supplémentaire:
<?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 recherche trouve ou renvoie un processus autorisé null, s'il n'en existe pas. Il couvre toutes les suites autorisées et nécessite un maximum de préparation \((a+1)(b+1)(T+2)\) États. Les entrées volumineuses nécessitent donc beaucoup de mémoire. Le nombre de transitions de recherche est minimisé, pas le temps de préparation. Les temps d'exécution rationnels et les temps cibles sont convertis en nombres entiers en utilisant un dénominateur commun. Pour les runtimes sans unité de temps commune, par exemple \(1\) et \(\sqrt{2}\), cette recherche d'entiers finis ne convient pas.