Un édredon en patchwork, cent soixante-neuf carrés cousus les uns aux autres. On vous demande de le défaire en aussi peu de morceaux carrés que possible. Cela ressemble à un jeu de salon victorien — et c’est devenu, un demi-siècle plus tard, un problème de recherche qui porte son nom.
L’énoncé, publié à Londres en 1917
Il tient en trois phrases. C’est le plus court de la série, et de loin le plus profond.
On verra que, dans le cas présent, l’édredon de patchwork carré est composé de 169 pièces. Le casse-tête consiste à trouver le plus petit nombre possible de portions carrées dont l’édredon pourrait être fait, et à montrer comment elles pourraient être assemblées. Ou, pour prendre le problème à l’envers : divisez l’édredon en aussi peu de portions carrées que possible, en coupant simplement les coutures.
Henry Ernest Dudeney, Amusements in Mathematics, 1917
Ce qu’on lit aujourd’hui
Ce casse-tête a un nom en mathématiques, et c’est le sien. On appelle « édredon de Mrs Perkins » le problème général : découper un carré de côté n en le moins de carrés possible, tous à côtés entiers. John Conway lui a consacré un article en 1964 dans les Proceedings of the Cambridge Philosophical Society — il y traite les petits cas et donne une majoration du nombre de pièces, que Trustrum a ensuite ramenée à un ordre de grandeur en logarithme de n. La suite des minima est répertoriée dans l’encyclopédie des suites d’entiers, et des dénombrements exhaustifs par ordinateur ont depuis été publiés bien au-delà de la taille qui nous occupe.
Et Dudeney prend une précaution qu’on remarque à peine. Dans sa solution, il écrit : « je crois qu’il n’y a pratiquement qu’une seule solution ». Je crois. Il a construit sa découpe, il ne l’a pas démontrée minimale — et il a l’honnêteté de le dire. C’est exactement la frontière entre trouver et prouver, et c’est là que ce petit édredon a cessé d’être un jeu.
Ce que le problème demande vraiment
« En coupant simplement les coutures » n’est pas une image. C’est la règle du jeu : les ciseaux suivent le quadrillage des 169 pièces, jamais autre chose. Chaque portion a donc un côté entier — 1, 2, 3 pièces de large, pas 4,5. Sans cette contrainte, ce serait un tout autre problème, et beaucoup moins intéressant.
Le réflexe naturel est le pire de tous. On se dit qu’il faut prendre le plus grand carré possible, puis le plus grand dans ce qui reste, et ainsi de suite. J’ai fait tourner cette méthode gloutonne sur l’édredon : elle découpe un grand carré de 12 sur 12, et se retrouve avec une bande en L d’une seule pièce de large qu’il faut débiter en vingt-cinq carrés d’une pièce. Total : 26 morceaux. On peut faire beaucoup, beaucoup mieux. La plus grosse pièce est ici votre ennemie, parce qu’elle laisse derrière elle un couloir que rien ne rattrape.
Enfin, « le plus petit nombre possible » se démontre en deux temps, et presque personne ne fait le second. Exhiber une découpe en k morceaux prouve qu’on peut faire au plus k. Il reste à établir qu’on ne peut pas faire moins — et cette moitié-là ne se trouve pas en dessinant.
Ce que ce problème fait travailler
D’abord une leçon sur les aires : la somme des aires des morceaux vaut 169, c’est une condition nécessaire. Elle n’est pas suffisante, et l’écart entre les deux est vertigineux — pour un nombre de pièces donné, il existe des dizaines de listes de côtés dont les aires totalisent bien 169, et presque aucune ne se pose réellement dans le carré. L’arithmétique autorise, la géométrie refuse. Savoir qu’une condition nécessaire ne suffit pas, c’est un des passages obligés du raisonnement mathématique.
Ensuite, l’habitude de chercher par la contrainte plutôt que par l’exemple. Un coin de l’édredon doit bien être occupé par un morceau ; le long d’un bord, les morceaux doivent se succéder sans laisser de trou. Ces remarques-là valent mieux que cent essais au crayon, et elles se prêtent au découpage réel — c’est un problème qu’on peut poser à une classe avec du papier quadrillé et des ciseaux, comme les carrelages de couleur.
Et une dernière chose, plus rare : accepter qu’un problème d’apparence enfantine puisse être ouvert. Le cas de l’édredon de Dudeney est réglé depuis longtemps ; le problème général, lui, a occupé des mathématiciens professionnels pendant des décennies, et l’on n’en connaît toujours pas de formule.
À vous
Trois questions, de difficulté croissante :
- en combien de portions carrées savez-vous découper l’édredon ? (Faites mieux que 26.)
- quel est le minimum — et comment être sûr qu’on ne peut pas descendre plus bas ?
- ce minimum, l’atteint-on d’une seule façon, ou de plusieurs ?
En commentaire. Du papier quadrillé et une paire de ciseaux valent mieux qu’un long discours — et la troisième question a une réponse que Dudeney lui-même n’osait donner qu’au conditionnel. J’y mettrai les miennes dans quelques jours.
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.
Problème n° 173 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.