J'imagine un raisonnement par récurrence sur le nombre de cartes n pour prouver que le processus est nécessairement fini, quelque soit la permutation de départ.
Premiers pas de raisonnement :

- quand la carte n+1 est à la fin du paquet, on se ramène au cas de n cartes car la dernière carte ne peut jamais bouger du fond de son paquet.
- idem quand la carte n+1 est en tête de paquet, elle passe au fond en une manip
- quand la carte 1 est au fond du paquet, il faut pouvoir faire venir la carte n+1 en tête de paquet : est-ce possible ?

L'idéal étant même de montrer qu'une suite de manipulation n'a pas de cycle (sauf une fois le 1 en haut du paquet), et qu'on finit forcément par retomber sur le cas où le 1 est en premier.
En testant sur 4 cartes, je m'aperçois que tout se termine en 4 manip maximum, et qu'on termine très souvent sur 1234. Peut-on toujours terminer en au plus n manip ?
Y a plus qu'à généraliser !

(je vois bien venir l'entourloupe du genre : mais non L00ping, il va falloir trouver un contre-exemple parce que ça marche pas pour tous les n ! )

Ah oui, bien plus facile en effet.

1. Un arrangement de cartes donné ne peut transformer notre paquet qu'en un seul autre arrangement. Ça paraît logique, mais c'est très utile pour la suite.

2. Il n'y a qu'un nombre fini d'arrangements

3. Supposons un arrangement initial qu'on peut transformer sans s'arrêter. Dans ce cas, on doit forcément revenir sur un arrangement qu'on a déjà vu (d'après 2.), et du coup à partir de celui-là, nos transformations vont forcément "tourner en boucle" (d'après 1.) Donc si une série de transformation ne s'arrête jamais, c'est qu'elle boucle (c'est pas aussi évident que ça en a l'air).

4. La première carte ayant une valeur V, elle se retrouvera toujours en position V après inversion.

5. Supposons un arrangement initial qu'on peut transformer sans s'arrêter. Dans ce cas, il boucle à partir d'une certaine carte. Soit V la plus grande valeur de carte qu'on peut avoir en première position parmi celles qui sont dans la boucle. Après transformation, cette carte se retrouve en position V. Toutes les premières cartes suivantes dans la boucle sont inférieures à V, donc aucune d'entre elles n'inversera les cartes au delà de la v-ième, et du coup la carte V restera toujours en position V. Elle ne peut donc pas revenir en 1ère position, ce qui est absurde vu qu'il doit s'agir d'une boucle.

Il n'existe donc pas d'arrangement initial tel que la série de transformation ne s'arrête jamais.

vrai pour 1,2,3 cartes

les cartes n'ont de valeur qu'en position 1
le nombre de combinaisons est fini


supposons que c'est vrai pour n-1 cartes

pour n cartes 3 choix possibles :
.......... la carte n est en position n.......  on retombe au cas n-1
........ la carte n ne passe pas en position 1 et le jeu se termine comme un jeu n-1

........ la carte n passe en position 1 et immédiatement  en position n


donc le jeu s'arrêtera pour n cartes

Bravo aussi à Débutant et Gasole

Vasimolo

Je tente donc un raisonnement par récurrence pour montrer que quelque soit n, le processus se termine toujours.

pour n=2 : que l'on parte de 12 ou 21 on aboutit à 12.

si on suppose la proposition vraie pour n
Premier cas : la carte n+1 est au fond du paquet
On se ramène alors au cas à n cartes, car la carte n+1 de bougera pas du fond du paquet.
Second cas : la carte n+1 est en tête du paquet
On se ramène au premier cas car à la manip suivante, la carte n+1 se retrouvera au fond du paquet
Troisième cas : la carte n+1 n'est ni au fond ni en tête du paquet
Appelons k la carte du fond du paquet. En fait le rôle joué par les cartes n+1 et k peuvent s'inverser. En effet, si k=1, l'idée est d'amener forcément la carte n+1 en tête du paquet. Or si on remplace n+1 par 1, cela ne change rien : le 1 ne joue aucun rôle dans les suites de manipulations, uniquement quand il arrive en tête du paquet où tout s'arrête. Donc d'après la proposition au rang n, on sait qu'on va pouvoir amener n+1 en tête du paquet, et on se ramène au second cas.
Si k n'est pas égal à 1, cela ne change rien, on peut échanger le rôle de n+1 et k. On se ramène alors au rang n, avec les cartes {1,...,k-1,k+1,...,n+1}. Si on avait besoin du k en tête du paquet pour résoudre le problème, alors on va arriver à amener n+1 en tête de paquet, et on se ramène au cas 2. Sinon, le 1 arrivera en tête du paquet
Donc proposition vraie au rang n+1

Et le processus s'arrête quelque soit n !

Je crois qu'on peut même montrer que le processus s'arrête en au plus n étapes ?

Ah, il existe donc des contre-exemples ...
Pour quel n ?
J'arrive pas à voir l'erreur de ma démo, du coup

Je parie que c'est le dernier cas qui pose problème.
Sur un exemple je vais essayer d'expliquer mon raisonnement.

Prenons la permutation 8 4 5 2 1 7 9 3 6
Ici k=6 et n+1=9
Tant que 9 n'est pas arrivé en tête du paquet, le 6 va rester au fond. Et quand il arrive en tête du paquet, on se ramène aux autres cas.

Si on imagine qu'on avait la série 8 4 5 2 1 7 6 3, on sait d'après le rang n qu'on peut amener le 1 en tête de paquet.
Si cela peut se faire sans l'aide du 6 en tête du paquet, alors le 6 peut valoir n'importe quelle valeur (en l'occurrence ici 9), cela ne changera rien. Et le 1 arrivera en tête.
Si par contre on a besoin du 6 en tête, alors on fait les manip sur la config de départ comme si le 9 était un 6, et au moment où le 6 arrive en tête de paquet, on se souvient qu'en fait il est un 9, et on se ramène aux cas précédents.

Y a une escroquerie quelque part ? Je n'ai quasi aucun doute sur ma démo, donc ça veut certainement dire que je fais une boulette quelque part

Bonne démo de 007 ( j'avais mal compris ) et de Dylasse

On peut faire très très court avec un peu d'astuce !!!

Vasimolo

Il y a plusieurs façons ; l'une d'elle est de considérer la valeur de la plus grande carte passant en position 1 .

Vasimolo

Beaucoup de bonnes réponses

J'avais vu la solution comme ça , mais on peut bien sûr faire autrement :

On note V la valeur de la carte la plus haute passant sur le dessus du tas . Elle ne peut pas revenir en position 1 car après 1 elle passe en position V . On note V la nouvelle valeur de la carte la plus haute passant en position 1 , ...

Merci pour la participation

Vasimolo

PS pour Gasole : Je tiens à jour depuis très longtemps des petits carnets dans lesquels je note des problèmes glanés à droite et à gauche ainsi que quelques idées personnelles . J'ai le défaut de ne pas noter les références à supposé que je les aie connues à un moment ou un autre . Pour celui-ci je ne peux pas te répondre , il fait parti de ceux que je préfère car il ne demande pratiquement aucune connaissance : c'est trop facile ( mais sans intérêt ) de coincer tout le monde avec un résultat super pointu

Les tests que j'ai faits sur n=4 montrent que ça se termine en au plus 4 étapes.
Vous pensez que c'est vrai quel que soit n ?

Evidemment, il aurait fallu que je teste sur n=5 ...
Je pense donc que ma conjecture, même avec n+1, est à jeter à la poubelle