Trois usines en haut, trois maisons en bas, neuf conduites à tirer sans qu’aucune n’en croise une autre. Prenez un crayon. Vous allez y arriver huit fois — et buter sur la neuvième.
L’énoncé, publié à Londres en 1917
Traduit intégralement, y compris le soupir de chroniqueur qui l’ouvre.
Il existe une demi-douzaine de casse-tête, vieux comme le monde, qui ressurgissent perpétuellement, et il n’y a guère de mois dans l’année qui n’apporte des demandes quant à leur solution. Il arrive que l’un d’eux, qu’on croyait un volcan éteint, entre en éruption de la façon la plus surprenante. J’ai reçu un nombre extraordinaire de lettres au sujet de cet antique casse-tête que j’ai appelé « L’eau, le gaz et l’électricité ». Il est bien plus ancien que l’éclairage électrique, et même que le gaz, mais l’habit neuf le remet au goût du jour. Le casse-tête consiste à amener l’eau, le gaz et l’électricité, depuis W, G et E, jusqu’à chacune des trois maisons A, B et C, sans qu’aucune conduite n’en croise une autre. Prenez votre crayon et tracez les lignes montrant comment il faut s’y prendre. Vous vous trouverez bien vite en difficulté.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
Dudeney commence par se plaindre, et c’est le seul énoncé du livre où il le fasse. « Un nombre extraordinaire de lettres », « pas un mois dans l’année » : en 1917, le chroniqueur de casse-tête tenait aussi le service après-vente. Et il précise que le problème est « bien plus ancien que l’éclairage électrique, et même que le gaz » — l’eau, le gaz et l’électricité sont un habit neuf posé sur une question qui traînait depuis longtemps. C’est très exactement le sujet de cette série : les problèmes ne vieillissent pas, seuls leurs décors changent.
Le théorème qui règle définitivement ce genre de question — savoir si un réseau donné peut se dessiner à plat sans aucun croisement — a été publié par le mathématicien polonais Kazimierz Kuratowski en 1930, dans les Fundamenta Mathematicae. Dudeney est mort cette année-là. Il aura passé sa vie à recevoir des lettres sur ce casse-tête sans jamais disposer de l’outil qui y répond.
Ce que le problème demande vraiment
Fixez les règles avant de tracer. Une conduite peut serpenter autant qu’elle veut, faire le tour du dessin, s’allonger jusqu’à l’absurde : peu importe. Mais tout se passe sur la feuille — pas de pont, pas de tunnel, pas de troisième dimension. Et si, vers le quinzième essai, vous vous surprenez à vouloir faire passer un tuyau quelque part où il n’a rien à faire, arrêtez-vous et notez-le : savoir ce que l’énoncé interdit exactement est la moitié de ce problème. Dudeney, dans sa solution, s’y est lui-même arrêté.
Puis la question change. Après quelques essais, on cesse de se demander comment pour se demander pourquoi ça ne marche pas. C’est le vrai basculement, et il est plus difficile qu’il n’y paraît : « je n’y arrive pas » et « personne n’y arrivera » sont deux affirmations sans rapport. La première se constate, la seconde se démontre.
Et une preuve, ici, ne peut pas passer par les dessins. Il y en a une infinité : on ne les essaiera jamais tous. Il faut donc trouver une quantité qui ne change pas d’un tracé à l’autre, et montrer qu’elle interdit ce qu’on cherche. Compter, plutôt que dessiner — c’est tout l’art, et c’est ce que fait la théorie des graphes.
Ce que ce problème fait travailler
Le geste central est celui qu’on n’enseigne jamais assez : traduire un dessin en nombres. Six lieux, neuf conduites, et les régions que le tracé découpe dans la feuille. Ces trois nombres ne sont pas indépendants — ils obéissent à une relation qu’Euler a découverte en regardant des polyèdres, et qui vaut pour tout réseau tracé sans croisement. C’est le même monde que la tournée du facteur, où l’on décide à l’avance si un parcours est possible sans jamais l’essayer.
Ensuite, l’idée d’invariant : une quantité que les choix du dessinateur ne peuvent pas modifier. Tant qu’on n’en tient pas une, on n’a rien ; dès qu’on en tient une, la démonstration tient en quatre lignes. C’est la même mécanique que dans les problèmes de coloriage et de pavage, et c’est ce qui sépare une énigme d’un exercice.
Enfin, ce petit dessin de six cases est l’un des objets les plus étudiés des mathématiques du XXe siècle. Il a un nom, une théorie autour de lui, et il apparaît partout où l’on veut savoir si un réseau peut se poser à plat — le tracé d’un circuit imprimé, par exemple. Si le sujet vous attire, le blog a déjà creusé du côté des graphes hamiltoniens.
À vous
Trois questions, et la troisième est ma préférée :
- combien de conduites arrivez-vous à tracer, et où exactement ça bloque ?
- si vous pensez que c’est impossible : comment le démontrer ? Un dessin raté ne prouve rien.
- et si la feuille n’était pas plate ? Sur un ballon, cela ne change rien. Sur une bouée, essayez donc.
En commentaire. J’y mettrai mes réponses dans quelques jours — y compris la sortie de secours que Dudeney s’est autorisée, et qui a fait grincer des dents pendant un siècle.
Dans la même série. Rétro Math’s reprend les 430 problèmes d’Amusements in Mathematics (1917) : l’énoncé traduit tel quel, ce qu’on en sait aujourd’hui, et la solution en commentaire. Les autres épisodes en ligne : CHINESE MONEY, CHANGING PLACES, THE STOP-WATCH, MRS. PERKINS’S QUILT, THE INDUSTRIOUS BOOKWORM, SIR EDWYN DE TUDOR, THE NINE COUNTERS, THE SIX FROGS, A CENSUS PUZZLE, THE BARREL PUZZLE, A TRICK WITH DICE, CROSSING THE RIVER AXE, THE MILKMAID PUZZLE, THE TROUBLESOME EIGHT.
Problème n° 251 d’Amusements in Mathematics, de Henry Ernest Dudeney (Londres, 1917). Texte et gravure sont dans le domaine public : Dudeney est mort en 1930. Le livre est intégralement disponible sur Project Gutenberg, et l’énoncé original se lit ici.
Les trois réponses, comme promis — et la sortie de secours de Dudeney pour finir.
1. Huit conduites, et le blocage a un lieu précis. Commencez par tracer le grand circuit qui fait le tour de tout le monde :
W–A–G–B–E–C–W. Six conduites posées, et un hexagone qui partage la feuille en deux — un dedans et un dehors. Il reste exactement trois conduites à tirer :W–B,G–CetE–A, c’est-à-dire les trois grandes diagonales de l’hexagone. Chacune doit être tracée entièrement à l’intérieur ou entièrement à l’extérieur, puisqu’elle ne peut pas franchir le circuit déjà posé. Or ces trois diagonales sont deux à deux entrelacées : les extrémités de l’une séparent toujours celles de l’autre sur le pourtour. Deux diagonales du même côté se croisent donc forcément. Trois objets, deux côtés : il y en a nécessairement deux ensemble. Voilà le blocage, et voilà pourquoi il arrive toujours à la neuvième. Vous pouvez placer la première diagonale dedans, la deuxième dehors — huit conduites, tout va bien — et la troisième n’a plus nulle part où aller.2. La démonstration, en comptant au lieu de dessiner. L’argument ci-dessus en est déjà une, et elle tient dans un dessin. En voici une autre, plus courte, celle qui utilise la relation d’Euler annoncée dans l’article. Supposons le tracé réussi. On a
S = 6lieux etA = 9conduites ; la relationS − A + F = 2impose alorsF = 5régions, en comptant celle qui entoure le dessin. Maintenant la remarque qui fait tout : une conduite va toujours d’une usine à une maison, jamais d’une usine à une usine. Il n’existe donc aucun circuit de longueur 3, et chaque région est bordée par au moins 4 conduites. Comptons les couples (région, conduite qui la borde). Chaque conduite en fournit exactement deux, ce qui donne2 × 9 = 18. Mais chaque région en réclame au moins quatre, ce qui donne au moins4 × 5 = 20. Il faudrait que 18 soit supérieur ou égal à 20. Le tracé supposé n’existe pas.Notez ce qui vient d’arriver : on n’a examiné aucun dessin, et on les a pourtant tous éliminés. C’est la différence entre « je n’y arrive pas » et « personne n’y arrivera », et elle tient dans ces deux lignes de comptage.
3. La bouée, oui. Le ballon, non. Sur un ballon, rien ne change, et c’est un bon exercice d’imagination : percez la sphère en un point vide de tout tracé, puis étalez-la à plat. Vous récupérez exactement un dessin sur la feuille, avec les mêmes croisements. Ce qui est impossible sur le plan l’est sur la sphère, et réciproquement. La bouée, elle, offre ce que le plan n’a pas : un trou. Reprenez l’hexagone
W–A–G–B–E–C, posez une diagonale à l’intérieur, une deuxième à l’extérieur — et faites passer la troisième par l’anse. Elle rejoint son extrémité sans rien croiser, puisqu’elle a quitté la surface visible le temps du voyage. Le même comptage le confirme d’ailleurs sans dessin : sur une bouée, la relation d’Euler s’écritS − A + F = 0, ce qui donneF = 3régions. La condition devient « 18 au moins 12 » — elle passe. Une seule anse suffit, et c’est la mesure exacte de la difficulté de ce petit réseau : il ne lui manquait qu’un trou.Et la sortie de secours. Dudeney, dans sa solution de 1917, commence par reconnaître que « selon les conditions, au sens strict où on les comprend d’abord, il n’existe aucune solution possible ». Puis il ajoute cette phrase qui a fait grincer des dents pendant un siècle : « dans un tel dilemme, il faut toujours chercher quelque équivoque de mots, quelque astuce » — et il fait passer la conduite d’eau destinée à la maison C à travers la maison A, en supposant que le propriétaire n’y verrait pas d’objection. Aucun tuyau n’en croise un autre : la lettre de l’énoncé est sauve. Ce n’est évidemment pas une solution, c’est un aveu bien habillé — mais il est plus honnête qu’il n’en a l’air, puisqu’il désigne l’endroit exact où l’énoncé était muet. C’est d’ailleurs ce que je vous suggérais de noter au quinzième essai : savoir ce que le problème interdit vraiment est la moitié du travail.