Faire dîner les mêmes convives assez souvent pour que chacun se soit assis une fois, et une seule, entre chaque paire d’autres. Dudeney donne l’énoncé en trois lignes, annonce que personne n’a résolu le cas de treize personnes — et refuse de publier ce qu’il sait.
L’énoncé, publié à Londres en 1917
Traduit intégralement. C’est le plus court du livre, et de loin le plus vaste.
Asseyez les mêmes n personnes à une table ronde en (n − 1)(n − 2) / 2 occasions, de manière que personne n’ait jamais deux fois les deux mêmes voisins. Cela revient bien entendu à dire que chacun doit s’asseoir une fois, et une seule, entre chaque paire possible.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Et voici ce qu’il ajoute dans son corrigé, qui vaut l’énoncé : « Depuis la publication de ce livre en 1907, personne, à ma connaissance, n’a réussi à résoudre le cas de ce nombre de convives qui porte malheur, treize, attablés en soixante-six occasions. […] Mais comme je sais qu’un bon nombre de mathématiciens réfléchissent encore au cas de treize, je ne veux pas, à ce stade, leur voler le plaisir de le résoudre en montrant la réponse. »
Ce qu’on lit aujourd’hui
Ce problème porte son nom. On l’appelle en toutes lettres le problème de la table ronde de Dudeney, et les objets qu’il demande de construire sont des ensembles de Dudeney. Voici comment on l’énonce désormais : trouver, dans le graphe complet à n sommets, une famille de cycles hamiltoniens telle que chaque chemin de longueur deux appartienne à exactement un cycle. La table ronde, c’est le cycle ; les deux voisins d’un convive, c’est le chemin de longueur deux. Le dîner victorien est devenu un objet de la théorie des graphes.
Et il a fallu du temps. Le cas des effectifs pairs n’a été entièrement réglé qu’en 1993, par une construction générale publiée dans une revue de mathématiques discrètes. Les effectifs impairs, eux, ne sont toujours pas couverts en général : on sait construire la solution dans certaines familles de cas, pas dans toutes. Le vieux chroniqueur qui refusait de gâcher le plaisir des chercheurs n’imaginait sans doute pas que le plaisir durerait un siècle.
Ce que le problème demande vraiment
Ce nombre de repas n’est pas choisi, il est imposé. On peut le retrouver sans rien connaître au problème, et c’est le premier exercice à faire. Comptez de deux façons : combien y a-t-il, en tout, de « personne assise entre telle et telle » à réaliser ? Et combien un seul dîner en fournit-il ? Le rapport des deux donne la formule de l’énoncé, et il n’y a pas à discuter — s’il existe une solution, elle aura exactement ce nombre de repas.
Ce compte ne prouve rien, et c’est là que tout commence. Savoir que le budget tombe juste ne dit pas que le rangement est possible : il faut encore construire l’emploi du temps sans qu’aucune paire de voisins ne se répète. C’est la différence entre compter les places et asseoir les gens, et elle est immense — c’est exactement ce qui a occupé les mathématiciens pendant un siècle.
Commencez donc petit. À trois convives, un seul dîner suffit et il n’y a rien à dire. À quatre, il en faut trois ; à cinq, six ; à six, dix. J’ai fait tourner une recherche exhaustive jusqu’à huit convives et vingt et un dîners : à chaque fois, l’emploi du temps existe. Prenez cinq amis et une feuille — c’est faisable à la main, et c’est en le faisant qu’on comprend pourquoi le cas général est difficile.
Ce que ce problème fait travailler
Le double comptage, l’un des outils les plus économiques des mathématiques : compter la même chose de deux manières et faire parler l’égalité. Ici il donne d’un coup le nombre de repas, sans qu’on ait dessiné une seule table. C’est du dénombrement au sens strict, et c’est accessible bien avant le lycée.
Ensuite, l’idée qu’un problème d’organisation — un tournoi, un emploi du temps, une rotation d’équipes — est un problème de mathématiques et pas de bon sens. Celui-ci est le cousin direct des calendriers de championnat, où chaque équipe doit rencontrer chaque autre une fois et une seule.
Et enfin, les cycles hamiltoniens, dont le blog a déjà raconté pourquoi ils sont difficiles. Une table ronde est un cycle hamiltonien : on visite chaque convive une fois et on revient à son point de départ. Dudeney en demande toute une collection, ajustée au millimètre. Il ne le savait pas, mais il posait là une question de théorie des graphes quarante ans avant que le mot ne devienne courant.
À vous
- retrouvez la formule (n − 1)(n − 2) / 2 par le comptage. C’est la partie facile, et elle est jolie.
- construisez l’emploi du temps pour cinq convives : six dîners, et personne ne retrouve ses deux voisins.
- puis six convives, dix dîners. Vous sentirez à ce moment-là pourquoi treize a résisté si longtemps.
En commentaire. Je donnerai mes emplois du temps et le petit programme qui les trouve — mais faites les deux premiers à la main, c’est un excellent moment.
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, WATER, GAS, AND ELECTRICITY, 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, THE FOUR POSTAGE STAMPS, A CHAIN PUZZLE.
Problème n° 273 d’Amusements in Mathematics, de Henry Ernest Dudeney (Londres, 1917). Le texte est dans le domaine public : Dudeney est mort en 1930. Ce problème n’a pas d’illustration dans le livre ; le schéma ci-dessus a été composé pour cette série. Le livre est intégralement disponible sur Project Gutenberg, et l’énoncé original se lit ici.