Tri de crêpes

Tri de crêpes
Rotation d'une partie de la pile de crêpes à l'aide de la spatule.
Problème lié

Le tri de crêpes (de l'anglais pancake sorting) est un problème mathématique. Il s'agit de trier une pile de crêpes afin que les crêpes soient empilées de la plus grande à la plus petite (au sens de leur diamètre). La seule opération autorisée pour arriver à ce résultat est de retourner la partie supérieure de la pile. On peut considérer d'une part le problème algorithmique, où le but est d'arriver à la configuration finale, comme pour un algorithme de tri, et d'autre part des questions mathématiques. Une question classique est d'évaluer le nombre minimum de mouvements nécessaires, pour toute pile d'une certaine taille.

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.

Problèmes mathématiques

[modifier | modifier le code]

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 | modifier le code]

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 à [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 obtenu en 1979[1].

Nombre de problèmes

[modifier | modifier le code]

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

Nombre de piles de taille donnée nécessitant P manipulations pour être triée
Nombre P de manipulations nécessaires
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Nombre N
de crêpes
1 1
2 1 1
3 1 2 2 1
4 1 3 6 11 3
5 1 4 12 35 48 20
6 1 5 20 79 199 281 133 2
7 1 6 30 149 543 1 357 1 903 1 016 35
8 1 7 42 251 1 191 4 281 10 561 15 011 8 520 455
9 1 8 56 391 2 278 10 666 38 015 93 585 132 697 79 379 5 804
10 1 9 72 575 3 963 22 825 106 461 377 863 919 365 1 309 756 814 678 73 232
11 1 10 90 809 6 429 43 891 252 737 1 174 766 4 126 515 9 981 073 14 250 471 9 123 648 956 354 6
12 1 11 110 1 099 9 883 77 937 533 397 3 064 788 14 141 929 49 337 252 118 420 043 169 332 213 111 050 066 13 032 704 167
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.

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 | modifier le code]
  1. a b et c Gates et Papadimitriou 1979
  2. a b et c 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 », , 216 p. (ISBN 978-2-7011-9766-1), chap. 19 (« À quoi servent les maths... À trier ses crêpes comme Bill Gates ? »).
  3. (en) Laurent Bulteau, Guillaume Fertin et Irena Rusu, « Pancake Flipping is hard », Journal of Computer and System Sciences, vol. 81, no 8,‎ (lire en ligne).

Bibliographie

[modifier | modifier le code]

Articles scientifiques

[modifier | modifier le code]

Vulgarisation

[modifier | modifier le code]
  • 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 », , 216 p. (ISBN 978-2-7011-9766-1), chap. 19 (« À quoi servent les maths... À trier ses crêpes comme Bill Gates ? »).

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]