Pliage d'une bande ou d'une feuille de timbres

En mathématiques des origamis, le pliage d'une bande de timbres est la base d'un problème de dénombrement des façons de plier une bande de timbres postes, de même nature que le problème du pliage d'une feuille de timbres.

Historique

Le mathématicien Édouard Lucas énonce ces deux questions dans sa Théorie des nombres publiée en 1891, en citant Émile Lemoine comme étant à l’origine du problème. André Sainte-Laguë étudie ce problème dans un chapitre de son livre Avec des nombres et des lignes de 1937.

Contributions à ce problème par Jacques Touchard en 1950 , John Koehler en 1968, et Stéphane Legendre en 2012.

Pliages d'une bande de timbres numérotés

Le problème consiste à déterminer le nombre de manières de plier une bande de timbres numérotés, de façon à tous les replier sur un seul d’entre eux, les pliages devant se faire uniquement selon les lignes perforées. Le pliage doit être réalisé de telle sorte que le timbre numéro 1 ait sa face imprimée tournée vers le haut et que les perforations entre les timbres 1 et 2 soient situées à droite, ce qui élimine un certain nombre de cas obtenus par des symétries.

Par exemple, il existe deux façon de plier une bande de deux timbres, et six façons de plier une bande de trois timbres différents :

Dans ce cas, on obtient les six permutations possibles des trois timbres, mais pour plus de trois timbres, les permutations ne sont pas toutes possibles. Si, pour une permutation p, il y a deux nombres i et j de même parité telle que les quatre nombres i, j, i + 1 et j + 1 apparaissent dans p dans cet ordre, alors p ne peut être obtenu par pliage. La condition de parité implique que les plis entre les timbres i et i + 1, et entre les timbres j et j + 1, apparaissent du même côté de la pile de timbres pliés, mais la condition d'ordre implique que ces deux plis se croisent, une impossibilité physique. Par exemple, la permutation à quatre éléments 1324 ne peut pas être obtenue, car elle a cette séquence interdite avec i = 1 et j = 3. Toutes les permutations restantes, sans ce modèle, peuvent être obtenues par pliage. La suite des nombres de pliages d'une bande de n timbres est donnée par la suite A000136 de l'OEIS :

1, 2, 6, 16, 50, 144, 462, 1392, 4536, 14060, 46310, 146376, 485914, 1557892, 5202690,....

Le n-ième terme est divisible par n (car une permutation circulaire de la bande de timbre peut toujours être obtenue), et la suite des résultats de cette division est

1, 1, 2, 4, 10, 24, 66, 174, 504, 1406, 4210, 12198, 37378, 111278, 346846, 1053874,... suite A000682 de l'OEIS,

Ce sont les nombres de manières topologiquement distinctes dont une courbe semi-infinie peut faire n croisements avec une droite, appelés « demi-méandres ». Ils sont étroitement liés aux méandres, façons pour une courbe fermée de faire le même nombre de croisements avec une droite. Les méandres correspondent à des solutions au problème de pliage des timbres dans lesquelles le premier et le dernier timbre peuvent être reliés l'un à l'autre pour former une boucle continue de timbres.

Dans les années 1960, John E. Koehler et WF Lunnon ont mis en œuvre des algorithmes qui, à cette époque, pouvaient calculer cette suite pour un maximum de 28 timbres. Malgré des recherches supplémentaires, les méthodes connues pour calculer ces nombres demandent un temps exponentiel en fonction de n. Ainsi, il n’existe aucune formule ou algorithme efficace connu qui pourrait calculer cette suite pour de très grandes valeurs de n. Néanmoins, des méthodes heuristiques issues de la physique peuvent être utilisées pour prédire le taux de croissance exponentielle de cette suite.

Le problème du pliage de la bande de timbres ne considère généralement que le nombre d'états pliés possibles de la bande de timbres, sans considérer s'il est possible de construire physiquement le pliage par une suite de mouvements à partir d'une bande de timbres dépliée. Cependant, d'après la solution du problème de la règle de charpentier, chaque état plié peut être obtenu (ou de manière équivalente, peut être déplié).

Pliages d'une bande de timbres non numérotés

Dans une autre variante du problème du pliage de la bande de timbres, celle-ci est considérée comme vierge, de sorte qu'il n'est pas possible de distinguer l'une de ses extrémités de l'autre, et deux pliages ne sont considérés comme distincts que lorsqu'ils ont des formes différentes. Retourner une bande pliée n'est pas considéré comme modifiant sa forme, donc par exemple trois timbres ne donnent que deux pliages, une courbe en S et une spirale. Les nombres de pliages avec cette définition sont donnés par la suite A001011 de l'OEIS :

1, 1, 2, 5, 14, 38, 120, 353, 1148, 3527, 11622, 36627, 121622, 389560, 1301140, 4215748,...

Pliages d'une feuille carrée de timbres

Il s'agit ici de dénombrer les façons de plier une feuille n × n de timbres le long de ses perforations, permettant à chaque pli de former soit un pli montagne, soit un pli vallée. Ce problème diffère du pliage d'une bande de timbres dans la mesure où il fait intervenir des plis dans deux directions.

Il existe huit façons de plier une feuille 2 × 2 le long de ses perforations, en comptant chaque séquence verticale différente de feuilles pliées comme une manière distincte de plier la feuille :

Le problème général du dénombrement des façons de plier une feuille n × n n'est connu que pour n ≤ 7.

Ces nombres forment la suite A001418 de l'OEIS :

1, 8, 1368, 300608, 186086600, 123912532224, 129950723279272.

Complexité

 Les problèmes de pliage de bandes et de feuilles de timbres sont liés à un problème de mathématiques des origami consistant à savoir si un carré avec un motif de pli peut être plié en une figure plate. Si une direction de pliage (soit un pli montagne, soit un pli vallée) est attribuée à chaque pli d'une bande de timbres, il est possible de tester si le résultat peut être plié à plat en temps polynomial.

Pour le même problème sur une feuille (divisée en rectangles par des plis avec des directions assignées), on ne sait pas si un algorithme de pliage temporel polynomial existe en général, bien qu'un algorithme polynomial soit connu pour les cartes 2 × n. Dans un cas restreint où la carte doit être pliée par une suite de plis « simples », qui plient le papier le long d'une seule ligne, le problème est polynomial. Certaines extensions du problème, par exemple aux feuilles de papier non rectangulaires, sont NP-complètes.

Même pour une bande de timbres unidimensionnelle, avec ses plis déjà étiquetés comme plis de montagne ou de vallée, il est difficile de trouver un moyen de la plier qui minimise le nombre maximum de timbres se trouvant entre les deux timbres d'un pli

Voir aussi

• Suite de pliage de papier, une séquence infinie de 0 et de 1 qui décrit une façon de plier des bandes de timbres.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « map folding » (voir la liste des auteurs).

Liens externes

• (en) Eric W. Weisstein, « Stamp Folding », sur MathWorld
• Animation de ces pliages