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.
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.