Tri de crêpes

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].

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é.

Tri d’une pile de 6 crêpes. Il s’agit de la configuration {5 ; 3 ; 6 ; 1 ; 4 ; 2}, l’une des deux piles de 6 crêpes nécessitant 7 manipulations (l’autre étant {4 ; 6 ; 2 ; 5 ; 1 ; 3}).

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

• (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) ;

• 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 ? »).

• Tour de Hanoï
• Bézette

• (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