Bonjour ,
En respectant l'énoncé pour n=8 on trouve  4 permutations.

Pour N=16   (2^4)--->5 permutations  .
On doit prouver rapidement n+1 si n est la puissance de 2 adéquate.

salut

ce suggère peut-être de travailler en base 2 et de trouver la fonction associée

ou alors il suffit aussi de considérer la permutation associée et de montrer qu'il existe tel que (identité) ...

dpi : les colonnes autres que la première sont dans l'ordre inverse :

la dernière carte reste toujours la dernière et la première devient l'avant dernière ...

Oui mais le raisonnement est le même
Voici les permutations pour N=32 (2^5) -->5+1 = 6   étapes:

Si on suit la carte 1, on voit:
étape  1    31  ème position
étape  2    30 ème          soit remontée   31-30 =1
étape  3    28 ème                                             30-28= 2
étape  4    24 ème                                              28-24= 4
étape  5    16 éme                                             24-16 = 8

On remarque aussi que la carte 11 ne bouge pas de position...

Bonjour à tous

Comme le propose Carpediem , pour moi la bonne approche est de considérer la permutation  , c'est à dire de ne pas s'occuper des valeurs des cartes mais seulement de leurs positions . Chaque point de départ génère un cycle et le PPCM des longueurs de ces cycles est la période cherchée .

Après il faut trouver la longueur de chaque cycle ( je ne l'ai pas encore fait ) mais on peut définir simplement la position suivante d'une carte à partir de sa position initiale .

Si on note pour alléger les notations alors si k<m+1 : k --> 2m - 2k + 1 et si k>m : k --> 2k - m . A partir de là on génère facilement la boucle issue de chaque k .

Ce n'est qu'une idée absolument pas finalisée

Imod

Bonjour à tous!
    Quelques commentaires...

- mes excuses à dpi pour mon exposé insuffisamment clair du problème, vous avez malgré tout réussi à votre 3ième tentative un exemple de la permutation telle qu'il le fallait. Remarque très juste d'aborder le problème soit par en avant ou à reculons  puisqu'il s'agit d'un cycle où chaque nombre généré après chaque étape devient membre d'un groupe particulier.



-dans le contexte du chapitre du livre où l'on trouve le problème, la suggestion de Carpediem est intéressante car il semble que la solution tourne autour de 2ⁿ.

-En ce qui concerne l'approche de Imod , je reformule et corrige son algorithme de la façon suivante:

a) si 12^n-1 alors  -2X(mod2ⁿ+1) Y (impair)

b) si 2^n-1+12ⁿ  alors 2X+1(mod2ⁿ+1) Y (pair)
                     ou 2(X-2^n-1)(mod2ⁿ+1) Y (pair)

En notant l'opération a  par I et l'opération b) par P nous pouvons prouver que pour

X=1 la séquence des permutations sera correspondante est
                  IP...I le avec n-2 opération(s) P requise(s).

X=2ⁿ la séquence est une suite de P.

enfin si n+1 est pair, il existe un X tel que la séquence sera une suite de I en nombre pair.

Ce ne sont que des résultats partiels et loin de la solution complète du problème. Notez que si X est pair la dernière opération est un P et réciproquement pour un X impair la séquence se terminera par un I.  Franchement, avec cette approche, je ne vois pas trop comment pousser plus loin.
Plus de possibilités avec le combinatoire ou les fonctions génératrices ou encore passer en mod 2ⁿ-1?

À vous de jouer!
























1

>Lochenmeteo
Pas de problème avec l'exposé
Comme l'a remarqué carpediem ,j'avais inversé les positions ,mais
cela finalement confirme le fait qu'en n+1 permutations on retrouve l'ordre initial.

Comme mon bidule fonctionne ,j 'ai testé N=2^6-->7 étapes
On peut considérer qu'un raisonnement par récurrence s'impose.

soit

Ici encore si on observe le parcours de 1 on retrouve les mêmes
puissance de 2  pour sa remontée vers la première place:

63  62  60  56  48  32  1  soit une progression de 1  ,2, 4 , 8 , 16 , (32-1)
On peut extrapoler que pour n=7 soit N=2^7  -->8 étapes , le parcours de 1 sera:

127   126  124   120   112   96    64     1
soit     +1      2         4          8       16    32   (64-1)

Je crois que je tiens quelque chose

Notons les positions des cartes en partant de celle du dessous en base 2 de 0 à 2^n-1.

Par exemple pour n=5, on a 2^5=32 cartes de 00000 à 11111.

Voici les permutations des 32 cartes:

00000 -> 00000
00001 -> 00010 -> 00100 -> 01000 -> 10000 -> 11111 -> 00001
00011 -> 00110 -> 01100 -> 11000 -> 01111 -> 11110 -> 00011
00101 -> 01010 -> 10100 -> 10111 -> 10001 -> 11101 -> 00101
00111 -> 01110 -> 11100 -> 00111
01001 -> 10010 -> 11011 -> 01001
01011 -> 10110 -> 10011 -> 11001 -> 01101 -> 11010 -> 01011
10101 -> 10101

On peut réécrire le mélange comme suit:


La position axxxx devient (xxxx+aaaa)a où '+' est le ou exclusif.

De là on peut prouver que n+1 opérations renvoie le même nombre.

Soit la position abc...yz les mélanges successifs donnent:

0+a, 0+b, 0+c, ..., 0+y, 0+z
a+b, a+c, ..., a+y, a+z, a+0
b+c, ..., b+y, b+z, b+0, b+a
..., c+y, c+z, c+0, c+a, c+b
...
y+z, y+0, y+a, y+b, y+c, ...
z+0, z+a, z+b, z+c, ..., z+y
0+a, 0+b, 0+c, ..., 0+y, 0+z

0+0, 0+1, 0+1, 0+0, 0+0 = 01100
0+1, 0+1, 0+0, 0+0, 0+0 = 11000
1+1, 1+0, 1+0, 1+0, 1+0 = 01111
1+0, 1+0, 1+0, 1+0, 1+1 = 11110
0+0, 0+0, 0+0, 0+1, 0+1 = 00011
0+0, 0+0, 0+1, 0+1, 0+0 = 00110
0+0, 0+1, 0+1, 0+0, 0+0 = 01100

Bravo LittleFox.
J'ai essayé aussi la numérotation de 0 à 2ⁿ-1 qui me semble plus logique mais, en le faisant, j'ai oublié d'écrire les nombres en binaires.

Bonjour à tous!
Ici je m'adresse particulièrement à
LittleFox pour signaler une incohérence lors de sa première intervention. En suivant l'évolution binaire du nombre (ou la position) 3, il y a un hic arrivé au passage de 30 à 3 donc soit de
11110  à 00011 alors que vous décrivez et je cite

1xxxx -> yyyy1
Quel est cet yyyy? C'est simplement xxxx avec chaque digit inversé.
             Selon ce raisonnement  après 11110 devrait suivre
00001 ce qui n'est clairement pas le cas. Je ne suis pas encore  à même d'en comprendre les conséquences sur la suite de vos déductions lors de votre seconde intervention. Un commentaire de votre part serait grandement apprécié.
À bientôt!

Il y a une erreur dans ton inversion de xxxx.

30 = 11110 = 1 1110 -> 0001 1 = 00011 = 3

Merci pour la relecture 😊

Bonjour à tous.
J'ai essayé de recadrer vos réponses en terme de congruence et nom d'un chien, la solution me pendait au bout du nez!

Je débute selon le raisonnement de LittleFox en désignant les positions (du paquet de carte) du bas vers le haut par 0, 1...jusqu'à 2ⁿ-1.
Si X < 2^n-1 alors 2X= Y ou Y (mod 2ⁿ⁺¹-1)
Sinon   -2X   Y (mod 2ⁿ⁺¹-1).
Après 2^s opération nous obtenons
2^sX   Y (mod2ⁿ⁺¹-1)
avec s= n+1  nous avons que 2ⁿ⁺¹ 1 (mod2ⁿ⁺¹-1)
donc X Y (mod2ⁿ⁺¹-1).
Considérons qu'avec avec X = 1 au départ nous obtenons le cycle n+1 suivant 1 , 2 ...2^n-1
suivi d'un saut vers 2ⁿ-1 et retour vers 1.
Étant membre du même cycle chaque puissance de 2 élevée à la n-1 ou moins vérifie donc
X Y (mod2ⁿ⁺¹-1)
Puisque tout nombre inférieur à 2ⁿ peut s'écrire comme la somme de puissances de 2
alors X Y (mod2ⁿ⁺¹-1).
CQFD