Some Generalizations of the Bridge and Torch Problem

Imaginez un monde où les énigmes les plus passionnantes ne consistent pas à trouver un trésor caché ou à résoudre un meurtre, mais à faire traverser un pont sombre et branlant à un groupe d'amis avant le lever du soleil. C'est le domaine de l'optimisation combinatoire, une branche des mathématiques qui pose la question : « Quel est le meilleur moyen absolu de faire quelque chose lorsque l'on a des règles strictes ? » Voyez cela comme l'ultime partie de Tetris, mais au lieu de blocs, vous insérez des personnes dans des créneaux horaires, et le but est de terminer le niveau le plus rapidement possible. La version classique de ce jeu, connue sous le nom de « Problème du pont et de la torche », est célèbre pour ses règles d'une simplicité trompeuse : un groupe de personnes doit traverser un pont de nuit avec une seule lampe de poche. Le pont est étroit (seulement deux personnes peuvent s'y tenir à la fois), la lampe de poche doit être transportée à chaque traversée, et si deux personnes traversent ensemble, elles se déplacent à la vitesse de la plus lente. Cela semble facile, mais trouver le planning le plus rapide est une danse délicate de timing et de stratégie qui a dérouté plus d'un.

Maintenant, imaginez que vous preniez cette même énigme et que vous augmentiez le niveau. Et si le pont pouvait accueillir trois personnes ? Ou si, au lieu d'un seul pont, vous aviez un moyeu avec de nombreux rayons, comme une toile d'araignée, où les gens pourraient traverser vers différentes destinations en même temps ? C'est exactement ce que Thang Pang Ern et Gerard Sayson ont exploré dans leur article. Ils ont pris le classique puzzle du « pont à deux personnes », où chacun a un temps de traversée spécifique de 1 à $n$, et ils ne se sont pas contentés de le résoudre ; ils ont trouvé une formule magique qui prédit le temps minimum exact pour n'importe quel nombre de personnes. Ensuite, ils ont repoussé les limites, en déterminant les règles pour un pont pouvant accueillir trois personnes, et même pour un réseau en forme d'étoile. Ils ont découvert que, bien que les réponses deviennent complexes, elles suivent des motifs magnifiques et répétitifs qui peuvent être écrits en une seule équation.

La danse classique à deux personnes

Commençons par l'énigme originale. Vous avez un groupe de $n$ personnes, et leurs temps de traversée sont simplement les nombres $1, 2, 3, \dots, n$. La personne avec le temps 1 est un sprinteur, tandis que la personne avec le temps $n$ est une tortue. Le but est de faire passer tout le monde du côté gauche de la rivière au côté droit.

Les auteurs ont prouvé que pour cette configuration spécifique, il existe une formule parfaite, de forme fermée, pour calculer le temps minimum, $T(n)$. Ce n'est pas une simple supposition ; ils l'ont dérivée en décomposant le problème en morceaux plus petits. Ils ont réalisé que la meilleure stratégie consiste à envoyer les deux personnes les plus rapides (1 et 2) traverser en premier, en faire revenir une avec la torche, envoyer les deux personnes les plus lentes ensemble, puis faire revenir l'autre personne rapide. Ce « bloc » de mouvements évacue les deux personnes les plus lentes et laisse le système prêt à répéter le processus pour le groupe restant.

En additionnant les coûts de ces blocs, ils ont trouvé que le temps total pour $n$ personnes est :
$$T(n) = \frac{n^2}{4} + 3n - \frac{5 + (-1)^n - 1}{8}$$
Cette formule fonctionne pour tout nombre de personnes $n$ supérieur ou égal à 2. Ils ont également noté que la séquence de temps générée (1, 2, 6, 11, ...) est un motif connu dans le monde des mathématiques, mais ils ont fourni une preuve directe et nouvelle de pourquoi cette formule spécifique fonctionne. Curieusement, ils ont montré que la stratégie « standard » consistant à simplement renvoyer la personne la plus rapide faire des allers-retours avec tout le monde n'est pas toujours la meilleure. Par exemple, avec 4 personnes, la méthode standard prend plus de temps que la méthode astucieuse du « bloc ».

Le pont qui accueille trois personnes

Ensuite, les auteurs se sont demandé : « Et si le pont était plus large ? » Ils ont imaginé un pont pouvant accueillir jusqu'à 3 personnes à la fois, mais possédant toujours une seule lampe de poche. Cela change complètement la donne. Avec trois personnes, vous pouvez envoyer un trio, mais il faut toujours que quelqu'un ramène la lumière.

Ils ont découvert que pour cette version à « capacité 3 », le temps optimal, $T_3(n)$, suit un rythme différent et plus complexe. La formule implique un mélange d'une courbe quadratique (comme $n^2/6$) et de certains termes ondulatoires impliquant le cosinus et $(-1)^n$. Plus précisément, pour $n \ge 7$, le temps est :
$$T_3(n) = \frac{n^2}{6} + 2n - \frac{181}{36} + \frac{(-1)^n}{4} - \frac{2}{9} \cos\left(\frac{2n\pi}{3}\right)$$
Cette formule est si unique qu'elle a créé une toute nouvelle séquence de nombres dans l'Encyclopédie en ligne des séquences répertoriées (A392834). Les auteurs ont prouvé cela en montant que la meilleure stratégie consiste à déplacer des groupes de six personnes à la fois selon un cycle spécifique, réduisant le problème de $n$ personnes à $n-6$ personnes avec un coût prévisible ajouté à chaque fois. Ils ont également vérifié les petits nombres (comme 1 à 6) par force brute pour s'assurer que la formule correspond bien au début de la série.

Ils ont brièvement examiné un pont pouvant accueillir 4 personnes, mais ont admis que le motif devient désordonné et qu'ils n'ont pas encore trouvé de formule simple pour cela. Ils soupçonnent qu'une formule existe, mais qu'elle est beaucoup plus difficile à trouver.

Le réseau en forme d'étoile

Enfin, l'article fait un bond géant loin d'un simple pont. Imaginez un moyeu central (comme une gare) avec de nombreuses routes (rayons) menant à différentes destinations (feuilles). C'est ce qu'on appelle un « graphe en étoile ». Dans cette version, vous avez $n$ personnes au centre, $k$ routes menant vers l'extérieur et $t$ lampes de poche.

Les règles sont un peu différentes : en une seule « étape », vous pouvez envoyer des personnes sur différentes routes en même temps, tant que deux personnes n'utilisent pas la même route et qu'une personne n'est pas à deux endroits à la fois. Le temps pour cette étape est déterminé par la personne la plus lente de cette étape.

Les auteurs ont découvert que le temps minimum dépend fortement du nombre de lampes de poche et de routes dont vous disposez. Si vous avez assez de lampes de poche et de routes pour envoyer tout le monde en une seule grande vague, le temps est simplement le temps de la personne la plus lente ($n$). Mais si vous êtes limité, le temps croît approximativement comme $n^2$. Ils ont dérivé une formule de borne inférieure :
$$T(n, k, t) \ge sn - ms(s-1)$$
où $m$ est le plus petit entre le nombre de routes et de lampes de poche, et $s$ est le nombre de « tours » nécessaires pour faire sortir tout le monde.

L'un des aspects les plus fascinants de cette section est la façon dont elle se connecte aux mathématiques pures. En examinant les nombres générés par ce problème de graphe en étoile, ils ont réalisé qu'ils recréaient des identités mathématiques célèbres impliquant la « fonction partie entière » (qui consiste simplement à arrondir à l'entier inférieur le plus proche). Par exemple, en résolvant le puzzle pour des nombres spécifiques de personnes et de routes, ils ont « redécouvert » une identité connue sur la somme des fonctions partie entière, montrant comment un puzzle de planification amusant peut révéler des vérités profondes sur les motifs numériques.

En résumé, cet article prend une énigme classique, la résout avec une formule précise, l'étend à des ponts plus larges, puis la transforme en un réseau multi-voies, tout en découvrant une beauté mathématique cachée en chemin. Il montre que même dans un simple jeu de traversée de pont, il existe des couches de stratégie et de structure qui attendent d'être découvertes.