Battage de cartes

[leon1789]

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.

Oui, c'est-à-dire avec

Tu te rapproches de l'ordre multiplicatif de 2 modulo 2N+1 ...

[nodgim]

Au passage, et pour prendre un peu de recul vis à vis de ce problème spécifique, je note que l'ensemble des nombres voisins (à l'unité) des puissances de 2 englobe tous les nombres premiers, sauf 2, sous la forme directe ou en factorisation. Etonnant, non ? :doh:

[ffpower]

c est une consequence directe du petit theoreme de fermat ca^^

[leon1789]

oui, pour tout p premier impair, il existe un entier k>0 tel que .
Le plus petit des ces entiers k est nommé l'ordre multiplicatif de 2 modulo p. :zen:

[nodgim]

oui, pour tout p premier impair, il existe un entier k>0 tel que .
Le plus petit des ces entiers k est nommé l'ordre multiplicatif de 2 modulo p. :zen:

Bon, d'accord avec l'ordre multiplicatif de 2 modulo p et le petit thérème de Fermat. Mais connait on la preuve que le cycle maximal est le nombre de cartes moins 2 ? Existe t il déja des études sur ce sujet et en connait-on les résultats ?
Merci d'avance pour vos réponses.

[leon1789]

Bon, d'accord avec l'ordre multiplicatif de 2 modulo p et le petit thérème de Fermat. Mais connait on la preuve que le cycle maximal est le nombre de cartes moins 2 ? Existe t il déja des études sur ce sujet et en connait-on les résultats ?
Merci d'avance pour vos réponses.

je relance

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

et l'ordre multiplicatif maximal de 2 modulo C-1 est C-2

[leon1789]

Bonjour,

On considère une involution f de dans . On doit montrer que f a au moins un point fixe.

Je connais une démonstration qui fait appel au théorème de Jordan et au théorème de Brower. Il doit bien exister une démonstration plus élémentaire ne faisant pas usage à cette artillerie lourde de topologie...

Des idées ?

:doh: une erreur de discussion ? :ptdr:

[nodgim]

je relance


et l'ordre multiplicatif maximal de 2 modulo C-1 est C-2

Ben, oui, mais la preuve? :doh:

[nodgim]

Soit 2C le nombre de cartes.
il a été dit plus haut qu'on pouvait écrire que (2C-1)*n=2^k+-1 avec k mini
Si 2^k-1, le cycle sera k
Si 2^k+1, le cycle sera 2k

Si 2C-1 est premier, tous les cycles ont le même cardinal, mais le cycle peut être unique, et dans ce cas, son cardinal est 2C-2.

Si 2C-1=a^i*b^j....*d*... (décomposition en facteurs premiers)
Il y a alors un cycle principal et des cycles secondaires.
Le cardinal du cycle principal est:
a^(i-1)*(a-1)*b^(j-1)*(b-1)...*(d-1)*...ou sa moitié, selon que 2C-1=2^k+1 ou 2^k-1.

Le nombre de cycles secondaires est le nombre de diviseurs de 2C-1,soit:
[(i+1)(j+1)...2...]-2

Le cardinal des cycles secondaires est une fraction entière du cardinal du cycle principal.
Par exemple:a(a-1) ou (b-1) ou encore (a-1)(b-1)(d-1).
Là encore, et comme pour le cycle principal, le cardinal du cycle secondaire peut être la moitié de la valeur attendue.

Exemple pour 2C-1=a²bc
le cardinal du cycle principal est a(a-1)(b-1)(c-1) (ou la moitié)
Les premiers nombres, et leur cardinal, des cycles secondaires, sont:
a......:(a-1)(b-1)(c-1)
a².....:(b-1)(c-1)
b......:a(a-1)(c-1)
c......:a(a-1)(b-1)
ab.....:(a-1)(c-1)
a²b....:(c-1)
bc.....:a(a-1)
ac.....:(a-1)(b-1)
a²c....:(b-1)
abc....:(a-1)

Ouf!

[leon1789]

Ben, oui, mais la preuve? :doh:

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, ....
le mélange est donné par l'application x -> (2*x+1) mod (2*N+1)

tu es d'accord ?

Il suffit ensuite de calculer l'ordre de l'application -> ordre de 2 modulo 2N+1

Ensuite, on revient à la distribution de Quidam est
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> 0, N,1, N+1, 2, N+2, ....

[nodgim]

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, ....
le mélange est donné par l'application x -> (2*x+1) mod (2*N+1)

tu es d'accord ?

Il suffit ensuite de calculer l'ordre de l'application -> ordre de 2 modulo 2N+1

Ensuite, on revient à la distribution de Quidam est
0 , 1 , 2 , 3 , ... , N , N+1, N+2, ... ==> 0, N,1, N+1, 2, N+2, ....

Bon, je fais un refus psychologique là dessus, je n'arrive pas à faire la synthèse que tu décris. :hum:
Pas grave, ce que j'ai fait apporte un peu de précision sur les cycles....Et puis ce sont les mêmes que les puissances kièmes de a modulo N si a et N sont premiers entre eux. :id:

[leon1789]

Bon, je fais un refus psychologique là dessus, je n'arrive pas à faire la synthèse que tu décris. :hum:
Pas grave, ce que j'ai fait apporte un peu de précision sur les cycles....Et puis ce sont les mêmes que les puissances kièmes de a modulo N si a et N sont premiers entre eux. :id:

Je comprends. Il faut dire que je ne m'explique pas très bien non plus.

En clair, j'ai retrouvé une formule simple (une fonction affine !) permettant de connaître la position de la carte n°X après le mélange.
Ensuite, il suffit d'étudier la formule pour comprendre le mélange. On voit alors que c'est complètement (et uniquement) lié aux puissances de 2. :we: