Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Probleme de recherche mathématiques complexe

Posté par
JojoLeBarjo
13-12-17 à 23:56

Bonjour à tous

Mon professeur m'a récemment donné un problème de recherche mathématiques
Voici l'énoncé :

Imaginons un paquet de n cartes à jouer  toutes tournées face vers le haut
Au début, on retourne la première carte, ensuite on retourne les deux premières carte (en même temps, pas indépendamment les unes des autres) etc... jusqu'à retourner le paquet entier. On recommence alors ce processus à l'infini.
Par exemple, si l'on représente une carte vers le haut par la lettre A et vers le bas par Z et si plus une carte est vers le haut du paquet, plus elle est à droite dans la représentation, pour un paquet de 4 cartes, on a :
AAAA->AAAB(on a retourné 1 carte)->AAAB(on a retourné 2 cartes)->AABB(on a retourné 3 cartes)->AABB(on a retourné 4 cartes)->AABA(on a retourné 1 carte)->AABA(on a retourné 2 cartes)->ABAB...
Vous pouvez faire l'expérience en vrai pour vérifier.

La question est la suivante : Soit M le nombre de coup minimal avant de retrouver le paquet initial (toutes les cartes face vers le haut). Et soit n le nombre de carte dans un paquet. Montrer que M ne peut s'écrire que sous la forme nk ou (nk)-1, avec k un entier naturel.

Je stagne complètement sur cette question.

Evidemment, je ne vous demande pas une réponse complète (surtout pas d'ailleurs, c'est pas du tout ce que je cherche) mais quelques pistes éventuelles qui pourraient me permettre d'avancé dans la résolution du problème.

Merci beaucoup d'avoir lu.

Bonne soirée.

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 13:15

salut

Citation :
Par exemple, si l'on représente une carte vers le haut par la lettre A et vers le bas par Z et si plus une carte est vers le haut du paquet, plus elle est à droite dans la représentation, pour un paquet de 4 cartes, on a :
AAAA->AAAB(on a retourné 1 carte)->AAAB(on a retourné 2 cartes)->AABB(on a retourné 3 cartes)->AABB(on a retourné 4 cartes)->AABA(on a retourné 1 carte)->AABA(on a retourné 2 cartes)->ABAB...

incompréhensible ...

c'est plutôt en utilisnat F et P pour les deux faces d'une cartes :

on part de la situation :

FFFFFFFF....

on retourne la première carte : PFFFFFFFFF...

on retourne les deux premières cartes : FPFFFFFFF ....

on retourne les trois premières cartes : PFPFFFFFFF....


... si je comprends bien ....

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 13:39

Bonjour,
moi je comprends ça tout autrement

numérotons les cartes ....4321
l'autre face étant rouge

je retourne une carte
4321 AAAB

je retourne deux cartes (ensemble, formant un paquet de deux cartes) :
4312 AAAB

je retourne 3 cartes (ensemble, formant un paquet de 3 cartes) :
4213 AABB

je retourne 4 cartes (tout le paquet)
3124 AABB

comme j'ai épuisé le nombre de cartes, je recommence :
3124 AABA

puis 2 cartes
3142 AABA

etc

quant au devenir de ce paquet de cartes ... aucun idée.
peut être une histoire de code Gray ?
faire un algorithme pour simuler tout ça et émettre des conjectures (à démontrer ensuite) ne semble pas trop abominable.

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 13:47

et je ne comprends toujours pas ...

on retourne et permute ??

Citation :
numérotons les cartes ....4321
l'autre face étant rouge

je retourne une carte
4321    AAAB

je retourne deux cartes (ensemble, formant un paquet de deux cartes) :
4312    AAAB


à la première étape tu as retourné une carte ... ok

je ne vois pas en quoi tu as retourné deux cartes à la deuxième étape ... par contre tu en as permuté deux ...

ha ok tu en retournes deux ... mais pourquoi les permuter ?

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 13:53

prends un paquet de cartes et tu comprendras ...

quand on retourne 3 cartes par exemple, on retourne le paquet de 3 cartes "en bloc"

celle qui était en dessous vient au dessus et change de face (de couleur dans mon illustration)
celle qui était au dessus vient au dessous et change de face
celle qui était au milieu reste au milieu et change de face

(et le reste du paquet est bien sur inchangé)

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 15:15

le résultat de l'algorithme précité.
avec des cartes nommées ABCD..., en minuscule si elles sont de dos, toutes visibles au départ, et le dessus du paquet à gauche
le critère est que les cartes reviennent exactement à leur position initiale orientation comprise
si on ne regarde que l'orientation (en binaire 1 = vue de dos), il y a deux fois moins d'étapes si N est pair.

Entrer N : 3
aBC 100, 1 cartes retournées
bAC 100, 2 cartes retournées
caB 110, 3 cartes retournées
CaB 010, 1 cartes retournées
AcB 010, 2 cartes retournées
bCa 101, 3 cartes retournées
BCa 001, 1 cartes retournées
cba 111, 2 cartes retournées
ABC 000, 3 cartes retournées
9 retournements de cartes


Entrer N : 4
aBCD 1000, 1 cartes retournées
bACD 1000, 2 cartes retournées
caBD 1100, 3 cartes retournées
dbAC 1100, 4 cartes retournées
DbAC 0100, 1 cartes retournées
BdAC 0100, 2 cartes retournées
aDbC 1010, 3 cartes retournées
cBdA 1010, 4 cartes retournées
CBdA 0010, 1 cartes retournées
bcdA 1110, 2 cartes retournées
DCBA 0000, 3 cartes retournées
abcd 1111, 4 cartes retournées
Abcd 0111, 1 cartes retournées
Bacd 0111, 2 cartes retournées
CAbd 0011, 3 cartes retournées
DBac 0011, 4 cartes retournées
dBac 1011, 1 cartes retournées
bDac 1011, 2 cartes retournées
AdBc 0101, 3 cartes retournées
CbDa 0101, 4 cartes retournées
cbDa 1101, 1 cartes retournées
BCDa 0001, 2 cartes retournées
dcba 1111, 3 cartes retournées
ABCD 0000, 4 cartes retournées
24 retournements de cartes

l'algorithme lui-même est laissé à JojoLeBarjo ...

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 16:39

Bonjour

Tout d'abord, merci de vos réponses.

Je rectifie quelque peu votre interprétation.
L'ordre des cartes n'importe pas, ce qui compte, c'est juste qu'elle soit toute face vers le haut.

D'autre part, j'ai déjà codé un programme qui calcule le nombre de coup nécessaire avant de revenir à l'état initial en fonction du nombre de carte dans le paquet. Par exemple, pour un paquet de 4 cartes il faudra 11 coups.

Cependant, cela ne suffit pas à répondre à la question. Il faut montrer que le nombre minimal M de coup avant que le paquet revienne à son état initial s'écrit soit sous la forme M=nk ou M=nk-1 avec n le nombre de carte du paquet et k un entier naturel non nul. (Il n'est pas demandé de déterminer quand il s'écrit sous la forme nk ou nk-1

Merci d'avoir lu
Bonne journée

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 16:48

ce qui ne m'aide toujours pas à comprendre ...

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 16:54

Il faut voir comme mathafou
Essaye chez toi, prend 3 cartes les unes sur les autres, prend la premiere caree, retourne la puis prend les deux premieres cartes et retourne les (elles doivent rester coller entre elles) puis repose les sur le paquet.
Tu verras que la formation n'a pas changé entre la première et la deuxième transformation

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 17:11

ha ok on retourne complètement le paquet de cartes sélectionnées ...

merci

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 18:00

Personne n'a une petite idée?

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 18:33

l'ordre des cartes importe pour le fonctionnement interne (en fait juste pour les retourner par paquets)

si on ne tient pas compte du nom des cartes, c'est juste la sortie en binaire de mes résultats qu'il faut examiner (et tester pour quand s'arrêter)
il confirme ton calcul avec 4 cartes de l'arrêt au 11ème retournement (quand on revient pour la première fois à 0000)
on remarque (conjecture) que si N est impair on se retrouve avec toutes les cartes revenues exactement à leur place avec un dernier retournement de tout le paquet de N cartes
et si N pair elles reviennent "toutes visibles" (0000) dans l'ordre exactement inverse après un dernier retournement de N-1 cartes

mais je reste sur ma conclusion provisoire :

Citation :
quant au devenir de ce paquet de cartes ... aucun idée.
(à part dérouler effectivement le processus au cas par cas et faire ce genre de conjectures)

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 18:49

Je ne comprends pas bien ce que tu veux dire.
Après combien de coups les cartes reviennent-elles dans l'ordre ?
Et d'autre part je ne vois pas vraiment en quoi cela m'avance pour montrer ce que j'ai à montrer. Je dois montrer que M = nk ou nk-1 avec M le nombre de coup avant de revenir à l'état initial, n le nombre de cartes dans le paquet et k un naturel différent de 0.

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 18:50

quand on retourne p cartes du paquet de n cartes alors les p premières sont inversées

on numérote les cartes de 1 à n du haut vers le bas et face vers le bas ...

on note (v, f) ou (1, 0) le fait que la carte soit face vers le bas ou face vers le haut

on considère la fonction   c_p  :  [[1, n]] \to [[1, n]] \times \{v, f\}   qui associe à tout entier k la position de la carte numérotée k et sa "face" après une manipulation de p cartes ...

on part de la situation initiale : c(k) = (k, f) = c_0(k)

et on considère la suite définie par récurrence : c_{n + 1}(k) = c o c^n(k)

en tout rigueur

Posté par
carpediem
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:02

quand on retourne p cartes du paquet de n cartes alors les p premières sont inversées

on numérote les cartes de 1 à n du haut vers le bas et face vers le bas ...

on note (v, f) ou (1, 0) le fait que la carte soit face vers le bas ou face vers le haut

on considère la fonction   c_p  :  [[1, n]] \to [[1, n]] \times \{v, f\}   qui associe à tout entier k la position de la carte numérotée k et sa "face" après une manipulation de p cartes ...

on part de la situation initiale : c^0(k) = (k, v)

et on considère la suite définie par récurrence : c^{n + 1}(k) = c_{p + 1  [n]}  o  c^n(k)

et on cherche le plus petits entier n tel que c^n = c^0

ça se programme aisément puisque c_p agit ainsi :

1 \le k \le p  =>  c_p(k) = (p - k + 1, ?*)  où étoile ?* est le contraire de ?

p + 1 \le k \le n  =>  c_p (k) = c_{p - 1} (k)  (elle est l'identité)

..

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:05

tu t'attaches à la partie la moins intéressante de ma conclusion : l'ordre des cartes
alors que le plus intéressant (pour le problème) dans ce que j'ai dit est

Citation :
on remarque (conjecture) que si N est impair on se retrouve avec toutes les cartes revenues exactement à leur place avec un dernier retournement de tout le paquet de N cartes
et si N pair elles reviennent "toutes visibles" (0000) dans l'ordre exactement inverse après un dernier retournement de N-1 cartes

le fait que selon la parité de N le dernier retournement effectué est exactement de N ou bien de N-1 cartes est la cause de ce qu'on demande

reste à le prouver.

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:08

je répondais à

JojoLeBarjo

Après combien de coups les cartes reviennent-elles dans l'ordre ?
Et d'autre part je ne vois pas vraiment en quoi cela m'avance

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:13

mathafou @ 14-12-2017 à 19:08

je répondais à
JojoLeBarjo

Après combien de coups les cartes reviennent-elles dans l'ordre ?
Et d'autre part je ne vois pas vraiment en quoi cela m'avance

Ah oui j'avais mal compris.
En effet, j'avais déjà pensé à prouver ce que tu dis en cherchant à montrer que le dernier coup avant d'arriver à la structure finale retourne soit n cartes soit n-1 cartes  en procédant par l'absurde.
Cependant, ta conjecture à propos de la parité de n est fausse
pour un paquet de 5 cartes, il faut 5*5-1 coups et pour 4 il faut 4*3-1

Posté par
JojoLeBarjo
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:14

carpediem @ 14-12-2017 à 19:02

quand on retourne p cartes du paquet de n cartes alors les p premières sont inversées

on numérote les cartes de 1 à n du haut vers le bas et face vers le bas ...

on note (v, f) ou (1, 0) le fait que la carte soit face vers le bas ou face vers le haut

on considère la fonction   c_p  :  [[1, n]] \to [[1, n]] \times \{v, f\}   qui associe à tout entier k la position de la carte numérotée k et sa "face" après une manipulation de p cartes ...

on part de la situation initiale : c^0(k) = (k, v)

et on considère la suite définie par récurrence : c^{n + 1}(k) = c_{p + 1  [n]}  o  c^n(k)

et on cherche le plus petits entier n tel que c^n = c^0

ça se programme aisément puisque c_p agit ainsi :

1 \le k \le p  =>  c_p(k) = (p - k + 1, ?*)  où étoile ?* est le contraire de ?

p + 1 \le k \le n  =>  c_p (k) = c_{p - 1} (k)  (elle est l'identité)

..


Je suis désolé mais je n'ai vraiment pas compris ce que tu as dis.

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:16

hélas, raté.

Posté par
mathafou Moderateur
re : Probleme de recherche mathématiques complexe 14-12-17 à 19:23

en tout cas ...



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !