La combinatoire des découpages de rectangles

Dénombrer est une des activités centrales en mathématiques. Le domaine appliqué aux problèmes de dénombrement est la combinatoire, et nombreuses sont les questions de grande difficulté qu’on y rencontre. Pourtant, il arrive qu’au terme d’un raisonnement complexe, la réponse apportée à un problème combinatoire se formule simplement et de manière concise. Nous allons, dans cet article, présenter une telle situation. On observera que, pour accompagner un raisonnement combinatoire, il est souvent utile de faire des dessins, ce qui rend l’activité ludique et abordable.

Deux questions d’apparence élémentaire seront traitées. La première, relativement facile, est : combien y a-t-il de façons de découper un rectangle composé de 2 × n carrés, avec n un entier strictement positif, en deux pièces superposables, chacune d’un seul tenant et composée de carrés ? La seconde question, plus difficile, consiste à faire le même dénombrement mais pour un rectangle composé de 3 × 2n carrés, avec n un entier strictement positif. Ces deux questions seront l’occasion de comprendre quelques méthodes mises en œuvre en combinatoire.

Précisons que ces problèmes ont été soumis en 2023 et 2024 aux jeunes qui participent aux activités de l’association Math-en-Jeans, destinées à faire découvrir la recherche mathématique aux élèves des collèges et lycées. Le premier a été entièrement résolu par les élèves, mais pour le second seuls les premiers cas ont été traités.

De manière à disposer d’un langage commode, nous appellerons « découpage convenable » d’un rectangle une séparation de celui-ci en deux pièces superposables, chacune composée uniquement de carrés de taille 1 × 1 et « d’un seul tenant » – les carrés d’une pièce du découpage se touchent par leurs côtés, et sont tous joints les uns aux autres de la sorte.

Dans cet article, pour visualiser le découpage, on conviendra de colorer en vert celle des deux pièces qui contient la case en bas à gauche du rectangle. Il est clair que ce choix ne fait perdre aucune généralité.

Précisons aussi que deux découpages sont considérés comme équivalents, et ne doivent donc pas être comptés deux fois, si les deux pièces que donne l’un sont les mêmes que les deux pièces que donne l’autre. Pour dire que des pièces sont « les mêmes », on s’autorise à les retourner, comme on le ferait avec des pièces en carton ou en bois. Cela signifie par exemple que, pour nous, les deux découpages convenables présentés dans la figure 1 ne comptent que pour un.

Découper un rectangle 2 × n

La figure 2 présente les découpages convenables de rectangles de taille 2 × n pour les premières valeurs de n. On peut, dans un premier temps, obtenir ces découpages par tâtonnement.

En notant S (n) le nombre de façons de découper convenablement un rectangle de taille 2 × n, on lit sur la figure 2 que S (1) = S (2) = 1 ; S (3) = 2 et S (2k) = S (2k + 1) = k + 1 pour 2 ≤ k ≤ 4. On peut donc conjecturer que cette dernière formule reste valable pour tout k ≥ 2. On propose ci-dessous un argument pour établir ce résultat.

On numérote les colonnes de gauche à droite, à partir de 1. Si la pièce verte occupe entièrement la colonne numéro k, avec k ≥ 1, alors elle occupe entièrement toutes les colonnes de numéro k’avec k’≤ k, car dans le cas contraire la pièce blanche serait coupée en deux morceaux disjoints.

Une fois connues les colonnes entièrement occupées par la pièce verte, il n’y a que deux possibilités de découpages convenables. En effet, les carrés qui manquent pour arriver aux n carrés qui composent nécessairement la pièce verte sont soit tous en haut, soit tous en bas – car de nouveau, si ce n’était pas le cas, la pièce blanche serait coupée en deux. Une fois connues les colonnes verticales occupées par la pièce verte, on a donc deux possibilités, comme l’illustre la figure 3. Avec nos conventions, ces deux possibilités ne comptent que pour un seul découpage convenable, puisqu’en retournant les pièces de l’une on obtient les pièces de l’autre.

Enfin, comme chacune des deux pièces du découpage doit comporter exactement n carrés, le nombre de colonnes entièrement occupées par la pièce verte est inférieur ou égal à n/2. Cela permet de conclure :

- Si n est pair, n = 2m avec m un entier positif, les découpages convenables sont ceux dont la pièce verte est de la forme « 0 colonne occupée + n carrés en bas », ou « 1 colonne occupée + (n – 2) carrés en bas », ou « 2 colonnes occupées + (n – 4) carrés en bas », etc., jusqu’à la possibilité « m colonnes occupées + 0 carré en bas ». Cela fournit exactement m + 1 découpages convenables.

- Si n est impair, n = 2m + 1 avec m un entier positif, les découpages convenables sont ceux dont la pièce verte est de la forme « 0 colonne occupée + n carrés en bas », ou « 1 colonne occupée + (n – 2) carrés en bas », ou « 2 colonnes occupées + (n – 4) carrés en bas », etc., jusqu’à la possibilité « m colonnes occupées + 1 carré en bas ». Cela fournit également m + 1 découpages convenables.

Ceci démontre bien la conjecture. Remarquons que le cas n = 2 doit être traité à part, parce que dans ce cas la solution où la pièce verte est de la forme « 0 colonne verticale occupée » est la même que celle où cette pièce est de la forme « 1 colonne verticale occupée ». Cela se produit dans le cas n = 2, et seulement dans ce cas-là, car le rectangle de taille 2 × n est alors un carré.

Découper un rectangle 3 × 2n

L’étude du second problème, plus difficile, va conduire à démontrer que, pour tout n ≥ 1, le nombre de découpages convenables d’un rectangle de taille 3 × 2n est R (n) = 2^n+ 1 – (n + 1).

Comme pour le problème précédent, cette formule a d’abord été conjecturée en traitant de petites valeurs de n. Avec Martine Raison, professeuse agrégée de mathématiques à la retraite (et mon épouse), nous avons méticuleusement établi des listes de dessins, à partir desquelles nous avons émis les hypothèses que R (1) = 2, R (2) = 5, R (3) = 12 et R (4) = 27.

Pour tenter de trouver une formule générale pour R (n) compatible avec ces premières valeurs, je me suis référé à « L’encyclopédie en ligne des suites de nombres entiers », de Neil Sloane. Cela m’a permis de constater que la suite dont le n-ième terme vaut 2ⁿ – n contenait bien ces quatre termes consécutifs – avec cependant un décalage d’un rang. Ainsi il était possible de formuler la conjecture que pour tout n ≥ 1, R (n) = 2^n+ 1 – (n + 1). Une étude à la main pour les cas n = 5 et n = 6 a paru confirmer cette hypothèse.

Martine Raison et moi-même avons par la suite établi chacun une démonstration complète de la formule. Je présente ci-dessous celle que j’ai mise au point.

Pour le raisonnement, on distinguera les découpages « sans crochet » de ceux « avec crochets » : on dit qu’une pièce est « sans crochet » si et seulement si elle n’a pas de surplomb, c’est-à-dire qu’elle n’est composée que de piles de carrés mises côte à côte, comme le montre la figure 4.

Découpages sans crochet

Commençons par établir que le nombre SC (n) de découpages convenables sans crochet d’un rectangle de taille 3 × 2n est SC (n) = 3 × 2^{n – 1} – 1, pour tout n ≥ 1. Cela donne, pour de petites valeurs de n : SC (1) = 2, SC (2) = 5, SC (3) = 11, SC (4) = 23, SC (5) = 47, SC (6) = 95 et SC (7) = 191.

Dans la suite, on raisonne en donnant les détails pour le rectangle de taille 3 × 8 (n = 4), et en indiquant comment le raisonnement se généralise pour un rectangle de taille 3 × 2n avec n ≥ 1 quelconque.

Classons les divers découpages convenables sans crochet.

(a) Il y a les découpages dont la pièce verte occupe toute la ligne du bas et ne comporte aucun carré sur la ligne du haut.

Pour dénombrer les pièces de cette forme, on fixe « vert » ou « blanc » pour les quatre premiers carrés de la ligne horizontale centrale, marqués d’un point dans la figure 5. Par symétrie (nécessaire pour que les deux pièces soient superposables), cela définit entièrement le découpage convenable, et il ne peut pas y en avoir d’autres de ce type.

Il y a 2⁴ = 16 façons de fixer la couleur des carrés marqués d’un point, et dans le cas général il y en a 2ⁿ. Cependant, chacun des découpages convenables est obtenu en double à cause de la symétrie par rapport à la ligne verticale centrale. Par exemple, des deux découpages de la figure 6, qui correspondent respectivement aux choix vert-vert-blanc-vert et blanc-blanc-vert-blanc, ne doivent être comptés qu’une fois.

On obtient donc un total de 2^{n – 1} découpages convenables de type (a), dans le cas général. Pour le rectangle de taille 3 × 8 (n = 4), ces découpages convenables sont présentés dans la figure 7.

(b) Il y a les découpages dont la pièce verte occupe toute la ligne du bas, sauf le dernier carré. Par symétrie, cela les oblige à avoir la première colonne verticale entièrement occupée par des cases vertes, comme dans la figure 8.

Fixer « vert » ou « blanc » pour les trois carrés marqués d’un point dans cette figure 8 détermine entièrement les découpages convenables de ce type. Cela en fournit 2^{n – 1} et, cette fois, il n’y a pas de doublon. Pour le rectangle de taille 3 × 8 (n = 4), ce sont ceux représentés dans la figure 9.

(c) Il y a les découpages convenables dont la pièce verte occupe toute la ligne du bas sauf les deux derniers carrés. S’ils sont « sans crochet », cela implique que la pièce verte occupe entièrement les deux premières colonnes, comme dans la figure 10.

Fixer « vert » ou « blanc » pour les deux carrés marqués d’un point dans cette figure 10 détermine complètement les découpages convenables de ce type. Cela fournit 2^n-2 solutions, dans le cas général – et, de nouveau, il n’y a pas de doublon. Pour le rectangle de taille 3 × 8 (n = 4), ce sont celles représentées dans la figure 11.

(d) Il y a les découpages convenables dont la pièce verte occupe toute la ligne du bas sauf les trois derniers carrés. S’ils sont « sans crochet », cela implique que la pièce verte occupe entièrement les trois premières colonnes, comme dans la figure 12.

Fixer « vert » ou « blanc » pour le carré marqué d’un rond dans cette figure 12 détermine complètement les découpages convenables de ce type. Cela fournit 2^{n – 3} solutions, dans le cas général. Pour le rectangle de taille 3 × 8 (n = 4), ce sont ceux présentés dans la figure 13.

(e) Il y a celui dont la pièce verte occupe toute la moitié gauche du rectangle, comme dans la figure 14.

Dans le cas n = 4 on aboutit au dénombrement : SC (4) = 2³ + 2³ + 2² + 2¹ + 1 = 23. En utilisant la formule 2^n-1 + 2^n-2 + 2^n-3 + … + 1 = 2ⁿ – 1, cela se généralise pour tout n ≥ 1 sous la forme : SC (n) = 2^{n – 1} + (2^{n – 1} + 2^{n – 2} + 2^{n – 3} + … + 1) = 2^{n – 1} + 2ⁿ – 1 = 3 × 2^{n – 1} – 1.

Découpages avec crochets

Nous allons à présent établir que le nombre AC (n) de découpages convenables avec crochets d’un rectangle de taille 3 × 2n est AC (n) = 2^{n – 1} – n, pour tout n ≥ 1. Cela donne, pour de petites valeurs de n : AC (1) = AC (2) = 0, AC (3) = 1, AC (4) = 4 et AC (5) = 11.

On remarque que, dans le cas général, les crochets ne peuvent se situer qu’aux extrémités de la pièce verte (sinon la pièce blanche serait coupée en deux). Pour dénombrer les découpages avec crochets dans le cas général, nous allons raisonner sur le rectangle de taille 3 × 10 (n = 5), car le rectangle de taille 3 × 8 est trop simple pour en tirer facilement une généralisation avec n quelconque.

Pour n = 5, les seuls découpages convenables avec crochets sont ceux dessinés dans la figure 15. Ils sont classés en fonction du nombre de colonnes sur la gauche complètement occupées par la pièce verte. Le regroupement A contient donc les découpages où seule la première colonne du rectangle est entièrement occupée par la pièce verte. Dans la première colonne du regroupement A, il y a quatre découpages, chacun avec des crochets d’un carreau. Dans la deuxième colonne du regroupement A, il y a deux découpages avec des crochets de deux carreaux. Dans la troisième colonne se trouve l’unique découpage avec un crochet de trois carreaux. Le regroupement B contient quant à lui les découpages où les deux premières colonnes sont les seules entièrement occupées par la pièce verte. Seuls des crochets d’un ou deux carreaux sont alors possibles. Le regroupement C contient l’unique découpage avec crochets où les trois premières colonnes sont occupées par la pièce verte.

Cette classification va nous guider pour établir le cas général.

A) Si n ≥ 2, il y a les découpages convenables avec crochets dont la pièce verte occupe toute la colonne de gauche, et aucune autre. Comme le montre la figure 16, pour n = 5, ces découpages peuvent avoir des surplombs d’un, deux, ou trois carrés (correspondant respectivement aux colonnes 1, 2 et 3 du regroupement A de la figure 15). Pour n = 5, des surplombs plus importants sont impossibles.

Par des considérations de même nature que celles effectuées pour calculer SC (n), on constate que, pour n = 5, on obtient respectivement, pour ces trois sous-catégories, 2², 2¹ et 2⁰ découpages convenables avec crochets. Cela fournit un total de 2² + 2¹ + 1 = 2³ – 1 = 7 découpages convenables de ce type.

Dans le cas général, pour tout n ≥ 2, on aura donc 2^{n – 3} découpages convenables avec des surplombs d’un carré, 2^{n – 4} découpages convenables avec des surplombs de 2 carrés, etc. Cela fournit un total de 2^{n – 3} + 2^{n – 4} + … + 2⁰ = 2^{n – 2} – 1 découpages convenables de type A.

Si n < 2, les découpages de ce type sont impossibles.

B) Il y a les découpages convenables avec crochets dont la pièce verte occupe les deux colonnes à gauche, et aucune autre. Dans le cas n = 5, ils peuvent avoir des surplombs d’un ou deux carrés, mais pas plus. Dans ce cas, il y a deux découpages convenables avec surplombs d’un carré, et un découpage convenable avec surplomb de deux carrés. Cela fournit donc 2¹ + 2⁰ = 2² – 1 = 3 découpages convenables.

Dans le cas général, pour n < 3, il n’y a pas de tel découpage convenable, et pour n ≥ 3 on retrouve la même somme que dans le cas A, en supprimant le premier terme : 2^n-4 + 2^{n – 5} + … + 2⁰ = 2^{n – 3} – 1 découpages convenables de type B.

C) Il y a les découpages convenables avec crochets dont la pièce verte occupe trois colonnes à gauche, et aucune autre. Dans le cas général, pour n < 4, il n’y a pas de tel découpage convenable, et pour tout n ≥ 4, un raisonnement similaire à celui présenté dans les cas A et B indique qu’ils seront au nombre de 2^{n – 4} – 1.

Dans le cas n = 5, on retrouve donc bien un total de (2³ – 1) + (2² – 1) + (2¹ – 1) = (8 + 4 + 2 + 1) – 4 = 2⁴ – 5 = 11 découpages convenables, ce qui correspond aux cas dessinés dans la figure 15. Dans le cas général, on trouve un nombre total de découpages convenables avec crochets qui vaut AC (n) = (2^{n – 2} – 1) + (2^{n – 3} – 1) + … + (2⁰ – 1) = (2^{n – 2} + 2^{n – 3} + … + 2⁰) – (n – 1) = 2^{n – 1} – n.

En regroupant l’ensemble des résultats présentés ci-dessus, on obtient que, pour tout n ≥ 2, le nombre de découpages convenables d’un rectangle de taille 3 × 2n est R (n) = SC (n) + AC (n) = 3 × 2^{n – 1} – 1 + 2^{n – 1} – n = 4 × 2^{n – 1} – 1 – n = 2^n+ 1 – (n + 1).

Le cas n = 1, qui devait être traité à part, rejoint finalement les autres, et la formule R (n) = 2^n+ 1 – (n + 1) est donc valable pour tout n ≥ 1 : la conjecture est démontrée.

Retournements de pièces

Dans notre raisonnement, nous avons convenu que si une solution s’obtenait par retournement d’une autre, il ne fallait compter ces découpages qu’une seule fois. On peut adopter une autre convention et considérer qu’il faut, au contraire, compter deux fois un tel couple de solutions qui s’obtiennent par retournement l’une de l’autre. Dans ce cas, on obtient un dénombrement R’(n) des découpages convenables d’un rectangle de taille 3 × 2n à partir du calcul fait pour R (n).

En effet, pour obtenir la valeur de R’(n), il faut, semble-t-il, doubler la valeur de R (n), pusique chaque solution en fournit maintenant deux. Il y a cependant quelques exceptions, car parfois le découpage « retourné » s’obtient aussi par rotation, donc sans retournement. On constate qu’il y a deux découpages de ce type pour n = 1, deux autres découpages de ce type pour n = 2 et un découpage de ce type pour n = 3 et n = 4. La formule générale est R’(n) = 2 × (2^n+ 1 – (n + 1)) – 1 = 2^n+ 2 – 2n – 3.

Les difficultés rencontrées dans ces problèmes de dénombrement proviennent, d’une part, de la contrainte selon laquelle les pièces des découpages doivent être d’un seul tenant – ce qui ne se traduit pas facilement en termes algébriques – et, d’autre part, de la convention selon laquelle on ne doit pas compter plusieurs fois les solutions qui se déduisent par rotation ou retournement les unes des autres.

Aujourd’hui on ne connaît pas le dénombrement des découpages convenables pour des rectangles de taille 4 × n, ni pour des carrés de taille 2n × 2n. Pour ce faire, il semble difficile de mener le même type de raisonnement que ceux développés dans cet article… mais les lectrices et lecteurs intéressés sont invités à tenter l’exercice !