Énigme de combustion de mèches

En mathématiques récréatives, les énigmes de combustion de mèches sont un type de casse-tête mathématique dans lesquels sont donnés des longueurs de cordes ou de mèches brûlant (de manière non uniforme) pendant un temps donné pris pour unité, et qu'on doit allumer de manière à mesurer une certaine durée. Les nombres fusibles sont les durées que l'on peut mesurer ainsi ; en 2021, une équipe de chercheurs américains a démontré de surprenants résultats d'indécidabilité concernant l'ensemble des nombres fusibles.

Le problème de base

La variante la plus simple et la plus connue de ces problèmes demande de mesurer un temps de 45 secondes en utilisant deux mèches dont chacune met une minute à brûler entièrement lorsque on en allume une extrémité ; l'énoncé précise qu'elles brûlent à une vitesse non constante, ce qui interdit des solutions mesurant la longueur de mèche souhaitée^[1].

La solution (unique avec ces contraintes) consiste à :

allumer une extrémité de la première mèche, et les deux extrémités de l'autre mèche ;
lorsque la seconde mèche a entièrement brûlé, 30 secondes se sont écoulées ; on allume la deuxième extrémité de la première mèche.
lorsque la première mèche s'est consumée, 45 secondes se sont écoulées^[1].

Nombres fusibles

Formalisant l'énoncé précédent, on dispose d'un nombre arbitraire de mèches brûlant dans le temps 1, et les seules opérations autorisées sont d'allumer une extrémité au temps $x$ (et la mèche a entièrement brûlé au temps $x+1$ ) ou d'allumer ensuite la seconde extrémité au temps $y<x+1$ (et alors la mèche sera entièrement consumée au temps $(x+y+1)/2$ ). Les nombres fusibles sont ceux qu'on peut construire à partir de 0 en utilisant uniquement ces deux opérations ; la solution donnée au problème de base montre que ${\tfrac {3}{4}}$ est un nombre fusible. On montre sans perte de généralité qu'on peut toujours se ramener au second cas, et donc que l'ensemble des nombres fusibles, $F$ , est le plus petit ensemble contenant 0 et stable pour l'opération $x,y\mapsto (x+y+1)/2$ , où $x$ et $y$ sont deux éléments de $F$ tels que $|x-y|<1$ ^[1].

$F$ est un sous-ensemble bien ordonné de l'ensemble des rationnels dyadiques positifs, c'est-à-dire des fractions dont les dénominateurs sont des puissances de deux ; cela veut dire que toute suite décroissante de nombres fusibles est finie. Le type d'ordre de $F$ est $\varepsilon _{0}$ , un nombre ordinal qui est le plus petit des nombres epsilon^[1]. $F$ étant bien ordonné et contenant tous les entiers, pour chaque entier $n$ il y a un plus petit nombre fusible supérieur à $n$ ; il est de la forme $n+1/2^{k(n)}$ . L'entier $k(n)$ croît extrêmement vite avec $n$ (c'est la suite A188545 de l'OEIS) : alors que $k(1)=3$ et que $k(2)=10$ , $k(3)=1\,541\,023\,937$ et $k(4)$ est déjà supérieur à $2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 16$ (en notation des flèches de Knuth). En 2021, une équipe autour de Jeff Erickson a construit un algorithme explicite de calcul de $k(n)$ très simple^[2], mais dont le fait qu'il s'arrête quel que soit $n$ est impossible à démontrer avec les axiomes de Peano^[3] ; ce résultat, analogue à ceux de Paris et Kirby pour les suites de Goodstein, est sans doute le résultat d'indécidabilité le plus naturel obtenu jusqu'à présent^[1].

Variantes et généralisations

Beaucoup de variantes de l'énoncé sont possibles, par exemple en utilisant des mèches non toutes identiques. On peut également envisager d'allumer les mèches ailleurs qu'en leurs extrémités. Si par exemple on a à tout instant trois extrémités allumées (en commençant par allumer une extrémité et un point au milieu de la mèche, puis en rallumant une extrémité (ou un point au milieu) chaque fois qu'une extrémité s'éteint, ce qui peut demander une suite infinie de mises à feu), il est clair que la mèche se consumera au total en 1/3 du temps ; généralisant cette méthode, on voit qu'on peut obtenir ainsi toute fraction unitaire, puis tout rationnel.

Les résultats connus sur les développements égyptiens montrent que pour mesurer ainsi un temps $x/y$ , avec $x<y$ , il suffit de $O({\sqrt {\log y}})$ mèches (où $O$ est la notation de Landau) ; une conjecture de Paul Erdős affirme que $O(\log \log y)$ mèches pourraient toujours suffire^[4].

Historique

Dans un livret sur ces problèmes intitulé Shoelace Clock Puzzles (« puzzles d'horloges en lacets de chaussures »), créé pour une conférence Gathering 4 Gardner (en) de 1998, Dick Hess attribue ces puzzles au statisticien de Harvard Carl Morris (en)^[5].

Outre leur intérêt récréatif, ces puzzles sont parfois utilisé dans des entretiens d'embauche comme test des capacités de résolution de problèmes^[6], et ont été également proposés comme activités mathématiques au collège^[7].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Rope-burning puzzle » (voir la liste des auteurs).

↑ ^{a b c d et e} Delahaye 2021.
↑ Plus précisément, ils définissent $M(x)$ , la distance entre x et le plus petit nombre fusible plus grand que x, récursivement par $M(x)=-x$ si $x<0$ , et $M(x)=M(x-M(x-1))/2$ sinon.
↑ Erickson 2021 ; cet article contient d'autres résultats d'indécidabilité, par exemple le fait que ces axiomes ne permettent pas non plus de démontrer que $F$ est bien ordonné.
↑ Erdős 1950.
↑ Hess 2009.
↑ Mongan 2012.
↑ Brumbaugh 2013.

Bibliographie

Jean-Paul Delahaye, « Mesurer le temps en allumant des mèches », Pour la science, vol. 527,‎ 2021, p. 80–85
(en) Douglas K. Brumbaugh, Teaching Middle School Mathematics, Routledge, 2013, 191, 309 (ISBN 978-1-136-75622-1)

(en) Jeff Erickson, Gabriel Nivasch et Junyan Xu, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021), IEEE, 2021, 1–13 p. (DOI 10.1109/lics52264.2021.9470703, arXiv 2003.14342)
(hu) Pál Erdős, « Az $\textstyle {\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\cdots +{\frac {1}{x_{n}}}={\frac {a}{b}}$ egyenlet egész számú megoldásairól » [« Sur les solutions entières de $\textstyle {\frac {1}{x_{1}}}+{\frac {1}{x_{2}}}+\cdots +{\frac {1}{x_{n}}}={\frac {a}{b}}$ . »], Matematikai Lapok, vol. 1,‎ 1950, p. 192–210 (MR 0043117, lire en ligne)
(en) Nathan Haselbauer, 60-Second Brain Teasers Pencil-Free Puzzles: Short Head-Scratchers from the Easy to Near Impossible, Fair Winds Press, 2020, 77, 121 (ISBN 978-1-63159-927-9)

(en) Dick Hess, All-Star Mathlete Puzzles, coll. « Official Mensa Puzzle Books », 2009 (ISBN 978-1-4027-5528-6), p. 9

(en) John Mongan, Noah Suojanen Kindler et Eric Giguère, Programming Interviews Exposed: Secrets to Landing Your Next Job, John Wiley & Sons, 2012 (ISBN 978-1-118-28720-0), p. 234

(en) M. Vose, « Egyptian fractions », Bulletin of the London Mathematical Society, vol. 17,‎ 1985, p. 21 (DOI 10.1112/blms/17.1.21, MR 0766441)

(en) Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, 2, 6 (ISBN 1-56881-201-9)

Portail des mathématiques

[del-1] {a b c d et e} Delahaye 2021.

[2] Plus précisément, ils définissent $M(x)$ , la distance entre x et le plus petit nombre fusible plus grand que x, récursivement par $M(x)=-x$ si $x<0$ , et $M(x)=M(x-M(x-1))/2$ sinon.

[3] Erickson 2021 ; cet article contient d'autres résultats d'indécidabilité, par exemple le fait que ces axiomes ne permettent pas non plus de démontrer que $F$ est bien ordonné.

[4] Erdős 1950.

[5] Hess 2009.

[6] Mongan 2012.

[7] Brumbaugh 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]