Battage de cartes

[Quidam]

Ca sert à quoi que je me décarcasse à battre les cartes ?

Une façon de mélanger un jeu de cartes consiste à séparer le paquet en deux paquets de tailles à peu près égales, à prendre un paquet dans chaque main et à laisser tomber sur le tapis une carte de chaque côté alternativement. Bien sûr parfois deux ou trois cartes du même paquet passent d'un seul coup, ça dépend de la dextérité du batteur. En supposant que l'on coupe parfaitement le paquet à chaque fois en deux paquets égaux, que l'opérateur soit parfaitement adroit, que chaque carte du paquet du haut se retrouve toujours au dessus de la carte de même rang du paquet du bas, il est évident qu'au bout d'un certain nombre d'opérations on retombera sur l'ordre initial. La question est : au bout de combien de fois ?
Par exemple, pour un jeu de 32 cartes !

[Galax]

Ca a l'air assez rapide, 5 pour 32 cartes et 8 pour 52 ?

[leon1789]

Ha oui :id: Preuve qu'un bon batteur de cartes est un batteur qui ne mélange pas suivant la perfection .

[leon1789]

Pour le tarot, la perfection est une technique satisfaisante non ? :zen:

[nuage]

Ha oui :id: Preuve qu'un bon batteur de cartes est un batteur qui ne mélange pas suivant la perfection .

C'est intuitivement évident : il n'y a pas d'aléa avec un bon batteur de cartes.
Donc il faut faire battre les cartes par un maladroit.

[leon1789]

En retirant 2 cartes du paquet de 32, on a une permutation d'ordre 28.

Question : pourquoi l'ordre de cette permutation est toujours inférieur au nombre de cartes ?

[nodgim]

Intéressante question!
Une carte donnée ne peut évidemment pas prendre plus de positions dans les 2 piles qu'il n'y a de cartes.
Mais, à y regarder de plus près, ce n'est pas une preuve.
En effet, on pourrait imaginer des cycles différents et premiers entre eux, qui feraient que le retour à l'ordre initial pourrait être supérieur au nombre de cartes!
Pour 30 cartes, par exemple, 28 changent de rangs à chaque manip., on pourrait imaginer un cycle de 19 rangs pour une carte donnée et 9 rangs pour une seconde carte. Il y aurait alors un retour à la situation initiale au bout de 19*9 manip.!
Or il n'en est rien. Quelque soit le nombre pair de cartes, les cycles ne sont jamais premiers entre eux.
Y a de l'Euler dans l'air, on dirait... :hum:

[leon1789]

Oui, il y a des permutations d'ordre supérieur à N dans .

Mais là, on a une permutation très "régulière" au niveau de ses orbites.

[ffpower]

J ai pas encore réfléchi,mais de loin j ai l impression que ce sujet ressemble a celui la:
http://www.maths-forum.com/showthread.php?t=74358

[Quidam]

J ai pas encore réfléchi,mais de loin j ai l impression que ce sujet ressemble a celui la:
http://www.maths-forum.com/showthread.php?t=74358

Bien vu ffpower ! Bravo !

C'est d'ailleurs celui-là qui m'a fait penser à celui-ci !

[nodgim]

On peut tout de même annoncer une règle sur les cycles.
Soit 2N, le nombre de cartes et p premier. Le cycle max. est 2N-2.
Si N-1 est congru à (p-1)/2 modulo p, alors le cycle ne peut être max.

Ce qui ne veut pas dire par ailleurs que le cycle sera max dans les autres cas, loin s'en faut.

[leon1789]

Or il n'en est rien. Quelque soit le nombre pair de cartes, les cycles ne sont jamais premiers entre eux.

C'est même "pire" que ça :
une orbite de cardinal maximal pour la relation d'ordre est de cardinal maximal pour la divisibilité.

Autrement dit, le ppcm des longueurs des cycles est lui-même la longueur d'un (ou plusieurs) cycle(s).

[leon1789]

(...)que chaque carte du paquet du haut se retrouve toujours au dessus de la carte de même rang du paquet du bas(...)

Les résultats ont l'air plus "homogènes" lorsque la carte initialement la plus basse du paquet, se retrouve en seconde position (toujours en partant du bas) après le mélange. Bien que cela augmente l'ordre de la permutation, cela donne des ordres qui ont l'air plus réguliers en fonction du nombre de cartes.

Par exemple, l'ordre de mélange varie jusqu'à 2N (et non 2N-2)...

[nodgim]

J'ajouterai que le cycle le plus grand est toujours celui qui part de 1.
J'explique ce "1".
Pour 2N cartes, il faut retenir 2N-2 nombres qui vont vraiment intervenir, les 1ère et dernière carte du paquet ne changeant jamais de position.

La modèlisation est donc celle ci, exemple pour 14-2=12 cartes:

12 11 10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10 11 12

Si on part de 1, on multiplie par 2, on passe à 2, puis 2*2=4 puis 2*4=8 mais on ne peut pas faire 2*8, donc on prend le nombre au dessus du 8, c.a.d. le 5, et on fait 2*5=10. On ne peut faire 2*10, donc on regarde le nombre situé sous le 10, c'est le 3, on fait alors 2*3=6 puis 2*6=12, etc...

Cet algorithme cache bien des mystères... :hum:

[leon1789]

Pour 2N cartes, il faut retenir 2N-2 nombres qui vont vraiment intervenir, les 1ère et dernière carte du paquet ne changeant jamais de position.

Exactement ! C'est comme si finalement, on battait uniquement 2N-2 cartes, c'est pas terrible "moralement" : un nombre pair s'écrit davantage 2N que 2N-2... C'est pour cela que je préfère placer la carte initialement la plus basse du paquet, en seconde position (toujours en partant du bas) après le mélange.

[leon1789]

En numérotant les cartes de 0 à 2N-1 (c'est pratique pour faire du modulo)

et en les battant ainsi
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> N, 0, N+1, 1, N+2, 2, ....

L'ordre du mélange est l'ordre de l'application x -> (2*x+1) mod (2*N+1)

[leon1789]

En numérotant les cartes de 0 à 2N-1 (c'est pratique pour faire du modulo)

et en les battant ainsi
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> N, 0, N+1, 1, N+2, 2, ....

L'ordre du mélange est l'ordre de l'application x -> (2*x+1) mod (2*N+1) dans Perm(Z/2N.Z)

[leon1789]

En numérotant les cartes de 0 à 2N-1 (c'est pratique pour faire du modulo)

et en les battant ainsi
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> N, 0, N+1, 1, N+2, 2, ....

L'ordre du mélange est l'ordre de l'application x -> (2*x+1) mod (2*N+1) dans Perm(Z/(2N+1).Z)

[leon1789]

En numérotant les cartes de 0 à 2N-1 (c'est pratique pour faire du modulo)

et en les battant ainsi
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> N, 0, N+1, 1, N+2, 2, ....

L'ordre du mélange est l'ordre de l'application x -> (2*x+1) mod (2*N+1) dans Perm(Z/(2N+1).Z), ou encore l'ordre multiplicatif de 2 modulo (C+1) où C est le nombre de cartes


Avec l'énoncé de Quidam, c'est donc l'ordre multiplicatif de 2 modulo (C-1) ...

[nodgim]

Bon, ça commence à s'éclaircir un peu.... :we:
Je peux déja annoncer ce petit théorème:
Tout nombre impair 2N+1 est soit de la forme 2^k+ou-1, soit divise un nombre de la forme 2^k+ou-1, avec k <=N.