Inscription / Connexion Nouveau Sujet
Probleme de recherche mathématiques complexe
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.
salut
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 ....
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.
et je ne comprends toujours pas ...
on retourne et permute ?? 
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 ?
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é)
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 ...
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
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
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 :
quant au devenir de ce paquet de cartes ... aucun idée.
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.
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 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 :
et on considère la suite définie par récurrence : c_{n + 1}(k) = c o c^n(k)
en tout rigueur
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 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 :
et on considère la suite définie par récurrence :
et on cherche le plus petits entier n tel que
ça se programme aisément puisque c_p agit ainsi :
où étoile ?* est le contraire de ?
(elle est l'identité)
..
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
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.
je répondais à
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
je répondais à
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
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
on part de la situation initiale :
et on considère la suite définie par récurrence :
et on cherche le plus petits entier n tel que
ça se programme aisément puisque c_p agit ainsi :
..
Je suis désolé mais je n'ai vraiment pas compris ce que tu as dis.
Annuler
connectez vous