I. Le problème

Présentation du problème.

II. La méthode naturelle

A] Explications

B] Un exemple.

III. Les arbres

A] Quelques remarques préliminaires.

B] Construction de l'arbre.

C] Validité de l'arbre.

D] Arbre élaboré.

E] Les bases du retournement.

F] Les égalités.

G] Quelques règles de calcul.

IV. Majoration et minoration

A] Recherche d'un minorant

B] Recherche d'un majorant

C] Encadrement de f(n)

V. Conclusion

Annexes

annexe 1

annexe 2

annexe 3

annexe 4

On veut savoir comment ordonner un tas de n crêpes numérotées de 1 à n de façon à avoir la plus grande en bas et la plus petite en haut, les crêpes étant de plus en plus petites n allant du bas vers le haut du tas.

Pour cela on s'oblige à utiliser un seul type de transformation et un seul outil

On coupe le tas à l'endroit choisi. La partie qui se trouve au dessus sera retournée, c'est à dire mise en sens inverse.

On se propose par exemple de remettre en ordre la pile ci-dessous

8 5 7 1 3 6 4 2

II. La méthode naturelle

A] Explications

Dans cet exemple nous avons ordonné de manière intuitive la pile de crêpes. Nous avons trouvé une méthode qui permet à coup sûr d'ordonner une pile.

Elle consiste à rechercher la plus grande crêpe : si elle n'est pas à sa place (c'est-à-dire en bas) on coupe la pile en dessous de celle-ci et on retourne la partie de la pile située au dessus de l'endroit où on a coupé. Cette crêpe se retrouve alors en haut de la pile. Il suffit alors de retourner la pile pour remettre la plus grande crêpe à sa place. On continue de même avec les crêpes restantes.

Cette méthode nécessite deux opérations pour remettre une crêpe à sa place sauf pour les deux plus petites qui seront soit dans l'ordre soit dans le désordre mais dans ce cas un seul retournement est nécessaire.

Cette méthode nous permet d'ordonner une pile à n éléments en 2(n-2)+1 coups pour n 2, c'est-à-dire qu'en 2n-3 coups, on est sûr de ranger la pile. (voir exemple ci-dessous)

Mais cette technique n'est pas forcément la plus rapide, il suffit pour s'en convaincre de regarder l'exemple suivant.

B] Un exemple.

Les nombres soulignés (4) matérialisent les coups de pelle.

II. Les arbres

A] Quelques remarques préliminaires.

Nous avons une pile ; on effectue un retournement ou une suite de retournements. On obtient une nouvelle pile. On peut repartir de cette pile et retrouver la pile initiale en faisant les mêmes retournements. Exemple:

Les tirets (_) représentent les coups de pelle.

C'est le principe de base de notre arbre ; il consistera à partir de la pile ordonnée, à effectuer des retournements qui aboutiront à d'autres ordres.

B] Construction de l'arbre ( voir annexe 1 et annexe 2 ).

Nous inscrivons la pile ordonnée dans une colonne, le niveau 0 car cette pile ne nécessite aucun retournement pour être remise dans l'ordre.

Cette pile de n crêpes peut être coupée à n endroits différents : on effectue ces retournements et on place les piles obtenues dans le niveau 1 (un seul retournement judicieux permet de remettre ces piles en ordre).

On remarque que l'ordre initial se retrouve dans ce niveau. En effet on a retourné une seule crêpe, ce qui est inutile puisque cette crêpe ne changera pas de place. Nous allons donc supprimer ce retournement.

On effectue maintenant les (n-1) retournements à partir des piles du niveau 1 pour obtenir les combinaisons du niveau 2. On s'aperçoit que des ordres réapparaissent (pour la pile de 4 éléments, c'est l'ordre 1234). Cela s'explique par le fait qu'on a effectué deux fois de suite le même retournement et donc qu'on retrouve l'ordre initial (comme dans l'exemple ci-dessus).

On simplifie encore l'arbre avec ceci. On continue ainsi.

C] Validité de l'arbre.

Nous avons n crêpes au départ et nous devons trouver n! permutations. Nous achèverons l'arbre une fois que nous les aurons toutes trouvées.

Nous savons que toute pile peut être remise dans l'ordre avec la méthode naturelle. La méthode naturelle permet d'aboutir à la pile initiale après un certain nombre de retournements. Or, c'est le principe de base de notre arbre.

Notre arbre fournit donc toutes les combinaisons possibles.

D] Arbre élaboré ( voir annexe 3 ).

Nous pouvons voir que certaines piles apparaissent plusieurs fois et parfois même à des niveaux différents. Nous ne conserverons que les piles différentes et qui apparaissent dans le niveau le plus proche de 0. En effet, il est inutile de faire les mêmes retournements à partir de plusieurs piles identiques.

Nous allons maintenant étudier les retournements qui permettent de simplifier l'arbre.

E] Les bases du retournement.

Nous allons noter un retournement "R". En indice, il y aura le nombre "i" de crêpes retournées : R_i.

Une suite de retournements sera notée "S" et " " la même suite de retournements mais dans l'ordre inverse. Le signe "=" indiquera l'équivalence entre deux suites équivalentes : S₁ = S₂. Plusieurs retournements successifs seront notés : R₂*R₃*R_i ...

F] Les égalités.

On remarque que R₁ est l'élément neutre et que

Règle I : R_i* R_i = R₁ et S*= R

G] Quelques règles de calcul.

Nous avons observé qu'il était que deux suites de retournements différentes appliquées à une même pile donnaient le même résultat comme par exemple :

R₂*R₃*R₂ = R₃*R₂*R₃

On obtient une pile nouvelle et seule à partir de laquelle on peut effectuer d'autres retournements.

Si on sait que S₁*S₂ = S₃ alors S₁*S₂*₂ = S₃*₂ or S₂*₂ = R₁ donc S₁ = S₃* ₂

On a aussi ₁*S₁*S₂ = ₁*S₃ or S₁*₁ = R₁ donc S₂ = ₁*S₃

et finalement on a S₁*S₂ = S₃*₂*₁*S₃

En utilisant les règles I et II, à partir de R₂*R₃*R₂ = R₃*R₂*R₃, on obtient les égalités R₂*R₃ = R₃*R₂*R₃*R₂ et R₃*R₂ = R₂*R₃*R₂*R₃.

G] Les mots neutres

Soit la suite :

R_a*R_b*...*R_x*R_y*R_z*R = R₁

et on la transforme :

R_a*R_b*...*R_x*R_y*R_z*R*R = R₁*R

R_a*R_b*...*R_x*R_y*R_z*R*R = *R or R*R = R₁

R_a*R_b*...*R_x*R_y*R_z = *R

R*R_a*R_b*...*R_x*R_y*R_z = R₁

on peut aussi écrire :

R_z*R*R_a*R_b*...*R_x*R_y = R₁

R_y*R_z*R*R_a*R_b*...*R_x = R₁

et on arrivera bientôt à la suite initiale :

R_a*R_b*...*R_x*R_y*R_z*R = R₁

Il y a donc un cycle.

Chaque égalité est équivalente à la suite initiale et on peut donc "commencer" d'où on veut dans ce cycle:

En recherchant les suites correspondantes au même cycle, on obtient un ensemble de classe qui constitue un noyau élémentaire à partir duquel on peut retrouver toutes les autres suites

Voici les mots ( représentants de classe ) trouvés (jusqu'à 4 éléments) :

R₂*R₃*R₂*R₄*R₂*R₃*R₂*R₄ = R₁

R₂*R₃*R₄*R₂*R₃*R₂*R₄*R₃ = R₁

R₂*R₃*R₄*R₃*R₂*R₃*R₄*R₃ = R₁

R₂*R₄*R₂*R₄*R₂*R₄*R₂*R₄ = R₁

R₃*R₄*R₃*R₄*R₃*R₄*R₃*R₄ = R₁

R₂*R₄*R₂*R₃*R₄*R₃*R₄ = R₁

R₂*R₄*R₂*R₄*R₃*R₄*R₃ = R₁

R₂*R₃*R₂*R₃*R₂*R₃ = R₁

R_i*R_i = R₁

Curiosité :

La pileest la pile de référence

La pileest la pile choisie

La pileest la pile que l'on désire fabriquer

La pileest l'ordre

On va ranger les nombres dedans les cases de

On associe chaque nombre deau nombre desitué sur la même ligne :

On range dans chaque case deles nombres deen face des nombres deégaux aux nombres de:

1	2	.	1
2	3	.	2
3	4	.	3
4	1	.	4
...	...	.	...

On associe chaque nombre deau nombre desitué sur la même ligne :

(1, c)

(2, b)

(3, d)

(4, a)

On associe chaque case deau nombre desitué sur la même ligne :

(, a')

(, b')

(, c')

(, d')

IV. Majoration et minoration

Pour cela, nous nous intéressons aux éléments de la dernière colonne du tableau. Ces éléments sont ceux qui nécessitent le plus grand nombre de manipulations pour retourner à l'ordre initial. Ce sont les plus grands désordres.

Si nous pouvons arriver à évaluer le niveau de ces plus grands désordres dans l'arbre, nous pourrons alors connaître le nombre de manipulations ou coups nécessaires au maximum pour remettre n'importe quel désordre dans l'ordre initial. Ce nombre de coups maximum est appelé f(n) pour un tas de n crêpes.

A l'aide des arbres, nous avons remarqué que:

f(1) = 0, une seule crêpe est forcément dans l'ordre!

f(2) = 1

f(3) = 3

f(4) = 4

On se propose d'encadrer f(n).

A] Recherche d'un minorant ( voir annexe 4 ) (( on cherche quelque chose dont on soit sûr que c'est plus petit que f(n) ))

Nous allons utiliser notre premier arbre.

On se propose de chercher le nombre de combinaisons pas forcément différentes que l'on a trouvées au niveau << p >> quelconque.

On additionne le nombre de combinaisons trouvées à chaque niveau :

on a donc :

Le nombre de désordres différents pour n crêpes étant n!, pour obtenir ce nombre, il faut que. Voici les calculs :pour tout entier supérieur à 3

Ainsi, pour être certain d'avoir tous les désordre possibles d'un tas de n crêpes, il faudra, dans l'arbre, aller au moins jusqu'au niveau p tel que p soit supérieur à la partie entière de

B] Recherche d'un majorant (( on cherche quelque chose dont on soit sûr que c'est plus grand que f(n) ))

Nous avons déjà vu que f(n)2n-3 pour n2

On se propose de trouver un meilleur majorant.

A l'aide de la méthode naturelle, on range toutes les crêpes d'une pile de n crêpes sauf les cinq du dessus. Cela nécessite 2(n-5) retournements, il reste 5 crêpes à remettre en ordre. Or f(5) = 5.

On a donc besoin de 2(n-5)+5 ou 2n-5 retournements pour remettre en ordre une pile de plus de 5 crêpes.

C] Encadrement de f(n)

D'après ce qui précède, on a :

ou pour .

V. Conclusion

Finalement, si on avait un moyen d'éliminer des arbres les désordres en doubles, triples ... alors on pourrait peut-être trouver un meilleur minorant.

Nous espérons que ces quelques réflexions ont apporté un peu d'eau au moulin de la recherche mathématiques et le lecteur aura compris que la question reste posée.