L'énigme du pont et de la lampe torche

Apparue discrètement au début des années 1980 sur les tout premiers balbutiements d'Internet et les lointains forums de discussion, cette énigme de gestion du temps est souvent appelée le fameux problème du pont de U2. En effet, une tenace légende urbaine prétendait que ce célèbre groupe de rock l'utilisait systématiquement lors de ses exigeants entretiens d'embauche. Bien que l'auteur original soit totalement anonyme, elle est devenue un grand standard mondial.

L'erreur la plus habituelle et fatale est de vouloir utiliser le marcheur le plus rapide pour faire systématiquement tous les retours en arrière avec la lampe. Cela donnerait un total de dix-neuf longues minutes. La ruse indispensable consiste plutôt à faire traverser les deux marcheurs les plus lents ensemble pour que leur grande lenteur ne soit comptabilisée qu'une seule et unique fois. Il faut impérativement pour cela que le deuxième marcheur le plus rapide soit déjà de l'autre côté pour ramener la lampe.

Très populaire et fréquemment utilisé dans l'enseignement académique des mathématiques discrètes, ce passionnant casse-tête est un brillant exemple d'optimisation et d'ordonnancement de tâches complexes. Il démontre brillamment que l'intuition naïve de la vitesse pure est parfois extrêmement trompeuse.