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, 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.
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.
Les trois réponses, comme promis.
1 et 2. Le minimum est 11, et l’on peut donc faire beaucoup mieux que 26. 26 étant précisément ce que donne la méthode gloutonne, celle qui prend à chaque fois le plus grand carré possible : un 12 × 12, puis vingt-cinq pièces de 1 × 1. Plus du double du minimum, pour la stratégie qui semblait la plus raisonnable. Et c’est la moralité cachée du problème.
Les onze morceaux ont pour côtés 7, 6, 6, 4, 3, 3, 2, 2, 2, 1 et 1. Voici où les poser, en numérotant les colonnes de gauche à droite et les rangées de haut en bas, de 1 à 13 : le 7 × 7 occupe les colonnes 1-7 et les rangées 1-7 ; un 6 × 6 les colonnes 8-13 et les rangées 1-6 ; l’autre 6 × 6 les colonnes 1-6 et les rangées 8-13. Reste un L de 48 cases, qu’on garnit ainsi : 4 × 4 en colonnes 10-13 et rangées 7-10 ; 3 × 3 en colonnes 7-9 et rangées 9-11 ; 3 × 3 en colonnes 11-13 et rangées 11-13 ; 2 × 2 en colonnes 8-9 et rangées 7-8, un autre en colonnes 7-8 et rangées 12-13, un troisième en colonnes 9-10 et rangées 12-13 ; enfin les deux carrés d’une seule case, en colonne 7 rangée 8 et en colonne 10 rangée 11. Somme des aires : 49 + 36 + 36 + 16 + 9 + 9 + 4 + 4 + 4 + 1 + 1 = 169.
Et comment être sûr qu’on ne peut pas descendre à 10 ? Je ne connais pas de preuve de salon, et c’est une réponse en soi : on épuise les cas, mais méthodiquement. On remplit toujours la case libre la plus basse et la plus à gauche — il faut bien que quelqu’un l’occupe, et le carré qui l’occupe a son coin exactement là. Il n’y a donc qu’un nombre fini de choix à chaque étape, et l’on élague dès que l’aire restante ne peut plus être couverte par le nombre de pièces encore disponibles.
Le piège, pour qui écrirait le programme : il est tentant de majorer le côté des carrés restants par la place disponible à l’endroit où l’on se trouve. C’est faux — un carré posé bien plus tard peut être bien plus grand. La majoration sûre est (13 − hauteur minimale)², et sans elle on trouve 12 au lieu de 11, avec l’assurance tranquille de ceux qui n’ont pas vérifié. Le contrôle qui démasque la panne : refaire tourner le programme sur les petits côtés, où les réponses sont connues : 2 donne 4, 3 donne 6, 5 donne 8, 7 donne 9, 11 donne 11.
3. Une seule façon. L’exploration complète produit huit découpes à onze morceaux, et ces huit-là sont la même : les huit images d’un même dessin par les rotations et les retournements du carré. À symétrie près, la solution est donc unique — et l’on peut enfin lever le conditionnel de Dudeney, qui écrivait « je crois qu’il n’y a pratiquement qu’une seule solution ». Il croyait juste. Entre croire et savoir, il y a exactement ce qui sépare une conviction d’une démonstration, et c’est le sujet de tout l’épisode.