Un chapelain anglais en poste en Haute-Birmanie s’ennuie sur le bateau qui l’y emmène, et se pose une question d’arboriculteur : sur ses quarante-neuf arbres plantés en carré, lesquels abattre pour que ceux qui restent s’alignent le plus souvent possible par quatre ? Dudeney lui répond vingt et une rangées, et ajoute qu’il croit que c’est le maximum. Il aura fallu cent neuf ans pour en être sûr.
L’énoncé, publié à Londres en 1917
Traduit intégralement, la lettre du chapelain comprise. La dernière phrase a l’air d’un détail : c’est la clé du problème.
J’ai reçu il y a peu une lettre intéressante du chapelain britannique de Meiktila, en Haute-Birmanie, dans laquelle mon correspondant m’apprenait qu’il s’était diverti, à bord du navire qui l’emmenait là-bas, à chercher la solution de ce petit problème.
S’il possède une plantation de quarante-neuf arbres, plantés en carré comme le montre l’illustration ci-jointe, il souhaite savoir comment en abattre vingt-sept de façon que les vingt-deux restés debout forment le plus grand nombre possible de rangées de quatre arbres.
Il va de soi qu’aucune rangée ne doit compter plus de quatre arbres.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
« Vingt et une rangées, je crois que c’est le plus grand nombre possible. » Dudeney savait parfaitement ce qu’il ne savait pas : il avait trouvé vingt et une rangées, plusieurs fois même, et il n’avait aucun moyen de prouver que vingt-deux fût hors d’atteinte. Il aurait fallu examiner les 49 699 896 548 176 façons de choisir vingt-deux arbres parmi quarante-neuf — près de cinquante mille milliards. Aujourd’hui, la question se pose à un solveur en nombres entiers — une inconnue par arbre, une par rangée — et la réponse tombe en huit secondes et demie : le maximum est bien vingt et un. Ce n’est plus une opinion. On peut même préciser son « il y a plusieurs façons de le faire » : il y en a exactement vingt, qui se ramènent à quatre dessins une fois les rotations et les miroirs mis de côté — et le sien est l’un des quatre.
Avant de croire la machine, on lui fait relire l’auteur. Le programme a d’abord été nourri de la planche de solution de 1917, relevée arbre par arbre sur la gravure : il y compte vingt et une rangées de quatre et pas une seule de cinq. C’est le contrôle indispensable — un compteur qui n’a jamais été confronté à un cas connu ne prouve rien du tout, et c’est aussi vrai pour un tableur que pour un solveur. Une fois d’accord avec Dudeney sur sa propre réponse, il pouvait être cru sur le reste.
Ce que le problème demande vraiment
Une rangée n’est pas une ligne du quadrillage. C’est le point sur lequel tout le monde se trompe d’abord : une rangée, ici, c’est quatre arbres alignés dans n’importe quelle direction. Les sept rangées horizontales et les sept colonnes, bien sûr, et les quatorze diagonales à quarante-cinq degrés qui portent au moins quatre arbres — mais aussi les seize obliques qui avancent de deux pas dans un sens pour un pas dans l’autre. Au total, le carré de sept sur sept contient quarante-quatre alignements utilisables. Qui n’en voit que vingt-huit plafonnera très vite, et c’est exactement ce qui rend ce casse-tête bon : il commence par apprendre à regarder.
Ce casse-tête a un nom et une descendance. Les mathématiciens l’appellent le problème du verger : avec un nombre d’arbres donné, combien peut-on former de rangées de trois, de quatre, de cinq ? Sylvester l’a posé pour les rangées de trois en 1868, la question générale n’est toujours pas close, et la version birmane de Dudeney en est un cas doublement contraint — les arbres sont obligés de tomber sur un quadrillage de sept sur sept, et il n’en reste que vingt-deux.
La dernière phrase de l’énoncé n’est pas une formalité. « Aucune rangée ne doit compter plus de quatre arbres » : sans cette interdiction, on garderait volontiers des colonnes entières, et l’on se disputerait pour savoir si sept arbres alignés font une rangée de quatre, ou plusieurs, ou aucune. Dudeney ferme la porte avant qu’on ne l’ouvre. Une ligne de cinq arbres n’est pas une ligne de quatre : elle est interdite, un point c’est tout.
Pourquoi vingt-deux serait si beau — et pourquoi on le sentait impossible. Comptons autrement : chaque rangée emploie quatre arbres, donc vingt-deux rangées représenteraient quatre-vingt-huit emplois d’arbres, à répartir sur vingt-deux arbres. Chacun devrait donc servir dans quatre alignements complets, sans exception. Or vingt et un des quarante-neuf emplacements du carré ne sont traversés que par quatre alignements possibles : pour eux, il faudrait que les quatre soient complets à la fois. Voilà l’intuition qu’avait Dudeney. Mais sentir qu’une chose coince n’est pas démontrer qu’elle est impossible, et c’est toute la différence entre son « je crois » et notre certitude.
Ce que fait le solveur, et qui n’est pas « essayer ». Il ne parcourt pas les cinquante mille milliards de possibilités : il raisonne sur des morceaux entiers de l’espace de recherche et les élimine en bloc, exactement comme on démontre qu’un nombre n’est pas premier sans essayer tous les diviseurs. Ce qu’il rend n’est donc pas une trouvaille, c’est un certificat : aucun choix de vingt-deux arbres ne dépasse vingt et une rangées. Neuf mille embranchements explorés, et la question est close.
Ce que ce problème fait travailler
D’abord l’alignement, et le fait qu’il se reconnaît à un déplacement régulier : deux à droite, un en haut, et on recommence. C’est du repérage dans un quadrillage mis au service d’autre chose que lui-même, et c’est le meilleur usage qu’on puisse en faire. Les obliques de pente deux sont invisibles tant qu’on ne les cherche pas ; une fois vues, on ne voit plus qu’elles.
Ensuite la différence entre trouver et prouver. Un élève qui affiche dix-huit rangées a trouvé quelque chose ; il n’a rien démontré sur les autres. Dudeney, qui en tenait vingt et une, n’a pas prétendu autre chose. C’est la même leçon que le damier mutilé, où l’on cherche en vain un pavage avant de comprendre qu’il fallait chercher une raison — sauf qu’ici, la raison est restée introuvable pendant un siècle, et que c’est une machine qui a tranché.
Et c’est une excellente activité de classe, qui ne demande qu’une feuille quadrillée et vingt-deux jetons : chacun cherche, on affiche le meilleur score du moment, il monte par paliers, et la discussion sur « peut-on faire mieux ? » arrive toute seule. On trouve facilement quinze ou seize rangées ; passer vingt demande de découvrir les obliques. Les autres problèmes de ce genre sont rassemblés sur la page Problèmes et activités.
À vous
- le défi de la plantation : vingt-deux arbres, vingt et une rangées de quatre, aucune de cinq. Quatre dessins essentiellement différents y parviennent ; il suffit d’en trouver un.
- l’échauffement, si l’on préfère commencer par le commencement : combien y a-t-il, dans le carré de sept sur sept, d’alignements portant au moins quatre arbres ? La réponse est dans l’article, la démonstration non.
- et la vraie question, celle qui reste entière : démontrer à la main que vingt-deux rangées sont impossibles. Une machine le certifie ; personne, à ma connaissance, n’en a jamais donné d’argument qu’un lecteur puisse suivre.
Une feuille quadrillée, quarante-neuf croix, une gomme. En commentaire, avec votre meilleur score — et la disposition de Dudeney viendra s’y poser, comme toujours dans cette série.
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, THE ROUND TABLE, THE CAB NUMBERS, THE POTATO PUZZLE, THE ECCENTRIC CHEESEMONGER, THE CLUB CLOCK, THE TWELVE MINCE-PIES, THE ARTILLERYMEN’S DILEMMA, PAPA’S PUZZLE, THE SPANISH DUNGEON, THE HAT-PEG PUZZLE, THE BARRELS OF HONEY, THE BICYCLE THIEF, A CALENDAR PUZZLE.
Problème n° 212 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.