Tri de crêpes

Un cuisinier fait des crêpes et les pose en pile à côté de la poêle lorsqu'elles sont cuites. Toutes les crêpes sont de taille différente. On dispose donc d'une pile de crêpes, chacune de taille différente et il s'agit d'ordonner les crêpes dans la pile, par ordre décroissant de taille (diamètre) avec donc celle de plus petit diamètre en haut de la pile. Un seul type d'opération est autorisé pour manipuler la pile : insérer une spatule à un endroit de la pile et retourner d'un coup toutes les crêpes qui se trouvent au-dessus de la spatule.

La question est : pour N crêpes, quel est le nombre minimum de manipulations (P) qui sont nécessaires pour mettre toute pile dans l'ordre décroissant ?

Un premier exemple peut être avec 2 crêpes (N=2), où l'on a alors seulement deux configurations de pile possibles. Soit il a cuit d'abord la petite puis la plus grande, soit c'est le contraire. Dans le premier cas, la plus petite est en bas et la plus grande en haut : il faut donc retourner toute la pile pour la mettre dans l'ordre voulu en glissant la spatule sous la crêpe du fond de la pile. Une seule manipulation est ainsi nécessaire. Dans le second cas, la pile est déjà dans l'ordre désiré, aucune manipulation n'est nécessaire. Donc pour N=2, P est au maximum de 1.

Le nombre minimum de manipulations est toujours 0 puisque le cuisinier peut avoir cuit les crêpes dans l'ordre décroissant de taille, auquel cas il n'y a aucune manipulation à faire.D'autre part, dès que N>4, il existe des piles où aucune crêpe ne touche une crêpe qui sera sa voisine dans le tri final (paire adjacente de crêpes). Comme chaque inversion crée au plus une adjacence de ce type, le tri prend nécessairement au moins N inversions - mais peut devoir en prendre plus^[1].De même, le nombre maximal est toujours inférieur à 2N-3 (on peut trier la pile séquentiellement, en commençant par la plus grande, avec deux inversions par crêpes, et le tri des deux dernières prend au plus un coup)^[1]. Mais cette manière de faire n'est pas nécessairement optimale.Si une pile de trois crêpes peut demander jusqu'à trois inversions, une pile de quatre peut toujours être triée en quatre inversions (économisant un coup) et une pile de cinq en cinq inversions (économisant deux coups).

P en fonction de N modifier

Le problème qui se pose est de trouver la loi mathématique qui donne P pour tout N, quand le tri est conduit de manière optimale. Ce problème est NP-difficile^[2],[3] et n'a toujours pas de solution complète. Les chercheurs qui se penchent depuis plus de 30 ans sur la question ont jusqu'ici réussi à estimer P qui serait toujours inférieur à ${\displaystyle {\frac {18n}{11}}}$ ^[2]. Cette valeur a été révélée en 2008 par une équipe de l'Université de Dallas (Texas). Cette valeur affine un majorant de ${\displaystyle {\frac {5n+5}{3}}}$ obtenu en 1979^[1].

Nombre de problèmes modifier

Le nombre C de configurations qu’une pile de crêpes possède au début du problème dépend du nombre N de crêpes dans cette pile. Il s’agit du nombre de façons différentes de permuter les N crêpes, soit une simple factorielle : C = N !. Pour chaque configuration de départ, il faut un nombre minimum P de manipulations au minimum afin de trier la pile. Bien qu’encore impossible de déterminer P pour tout N, on connaît toutefois le nombre de problèmes nécessitant P manipulations, pour un nombre de crêpes N fixé.

• Pour une pile d’une crêpe (N=1), il n’y a qu’une seule configuration possible (C=1). On peut considérer que la « pile » est déjà triée.
• Pour une pile de deux crêpes (N=2), il y a deux configurations possibles (C=2) :
  • la crêpe du dessus est plus petite que celle du dessous : la pile est déjà triée et ne nécessite donc aucune manipulation (P=0)
  • le diamètre de la crêpe du dessus est plus large que celle du dessous : il faut retourner toute la pile en une manipulation (P=1)
• Pour une pile de trois crêpes (N=3), il y a six configurations possibles (C=6) :
  • une configuration pour laquelle la pile est déjà triée, ne nécessitant aucune manipulation (P=0). On peut noter cette pile de la façon suivante : {1 ; 2 ; 3}.
  • deux configurations pour lesquelles il faut une seule manipulation (P=1). Il s’agit de la pile {2 ; 1 ; 3} où il faut retourner les deux premières crêpes et de la pile {3 ; 2 ; 1} où il faut retourner la pile complète.
  • deux configurations pour lesquelles il faut deux manipulations (P=2). Il s’agit des piles {2 ; 3 ; 1} et {3 ; 1 ; 2}.
  • une configuration nécessitant trois manipulations (P=3). Il s’agit de la pile {1 ; 3 ; 2}.

Le tableau suivant donne le nombre de problèmes nécessitant P manipulations, pour un nombre de crêpes N donné.

Ce tableau, lu ligne par ligne, constitue la suite A092113 de l'OEIS.

Dans un autre formalisme, le problème est équivalent au tri d'un tableau à l'aide d'une seule opération, l'inversion d'un préfixe.

Le tri de crêpes présenté en parallèle du problème classique du tri permet d'insister sur les opérateurs permis pour résoudre un problème d'algorithmique.

Ce tri a intéressé Bill Gates (l'un des fondateurs de Microsoft), David X. Cohen (l'un des créateurs de la série Futurama), et l'informaticien Christos Papadimitriou^[2].

Références modifier

Bibliographie modifier

Articles scientifiques modifier

• (en) William H. Gates et Christos Papadimitriou, « Bounds for Sorting by Prefix Reversal », Discrete Mathematics, n^o 27,‎ 1979, p. 47-57 (DOI 10.1016/0012-365X(79)90068-2) ;
• (en) David S. Cohen et Manuel Blum, « On the problem of sorting burnt pancakes », Discrete Applied Mathematics, vol. 61, n^o 2,‎ 1995, p. 105-120 (DOI 10.1016/0166-218X(94)00009-3) ;

Vulgarisation modifier

• Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », 2016, 216 p. (ISBN 978-2-7011-9766-1), chap. 19 (« À quoi servent les maths... À trier ses crêpes comme Bill Gates ? »).

Articles connexes modifier

• Tour de Hanoï
• Bézette
• Graphe des pancakes

Liens externes modifier

• (en) Flipping pancakes puzzle, une applet java et une discussion sur le tri de crêpes, sur cut-the-knot
• (en) The Pancake Problems par Douglas B. West
• (en) Eric W. Weisstein, « Pancake sorting », sur MathWorld

• Portail de l'informatique théorique