Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-03-2011 17:38:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Carte 2

Un deuxième opus bien plus facile que le premier smile

On dispose d'un tas de n cartes numérotées de 1 à n . On prend connaissance de la valeur v1 de la première carte puis on inverse l'ordre des v1 premières cartes . On prend connaissance de la valeur v2 de la nouvelle première carte puis on inverse l'ordre des v2 premières cartes ...

Un exemple avec 5 cartes :

Etape a : 32451
Etape b : 32451
Etape c : 32451
Etape d : 42351
Etape e : 42351
Etape f : 42351
Etape g : 53241
Etape h : 53241
Etape i : 53241
Etape j : 14235
Etape k : 14235

Et c'est fini !!!

Les manipulations peuvent-elles durer indéfiniment ou doivent-elles nécessairement s'arrêter à un moment donné ( avec la carte numérotée 1 au top ) ?

Bon courage smile

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 03-03-2011 00:31:05

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Carte 2

Problème joli et original... je vais réviser les permutations un peu wink

 #3 - 03-03-2011 01:14:36

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Cares 2

J'imagine un raisonnement par récurrence sur le nombre de cartes n pour prouver que le processus est nécessairement fini, quelque soit la permutation de départ.
Premiers pas de raisonnement :

- quand la carte n+1 est à la fin du paquet, on se ramène au cas de n cartes car la dernière carte ne peut jamais bouger du fond de son paquet.
- idem quand la carte n+1 est en tête de paquet, elle passe au fond en une manip
- quand la carte 1 est au fond du paquet, il faut pouvoir faire venir la carte n+1 en tête de paquet : est-ce possible ?

L'idéal étant même de montrer qu'une suite de manipulation n'a pas de cycle (sauf une fois le 1 en haut du paquet), et qu'on finit forcément par retomber sur le cas où le 1 est en premier.
En testant sur 4 cartes, je m'aperçois que tout se termine en 4 manip maximum, et qu'on termine très souvent sur 1234. Peut-on toujours terminer en au plus n manip ?
Y a plus qu'à généraliser !

(je vois bien venir l'entourloupe du genre : mais non L00ping, il va falloir trouver un contre-exemple parce que ça marche pas pour tous les n ! lol)

 #4 - 03-03-2011 03:09:28

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

cartzs 2

Le nombre de tas de n cartes est fini donc il existe forcément une étape à laquelle on retombe sur une configuration du tas de cartes déjà faite. A partir de cette étape, les manipulations sont périodiques.
On se place dans une suite d'étapes périodique. Soit v la plus grande valeur que prend la première carte dans cette suite d'étapes. Si on se place à une configuration où v est la valeur de la première carte, on constate qu'à la configuration suivante cette carte devient la v ième carte du tas. Supposons par l'absurde que v est supérieur ou égal à 2, alors les autres premières cartes qui suivent ont forcément des valeurs strictement inférieures à v (par récurrence), ainsi la carte avec valeur v ne peut plus apparaitre en première carte. Cela contredit la périodicité. Donc v=1.
Donc on a nécessairement la valeur 1 en première carte à un moment ou à un autre.

 #5 - 03-03-2011 10:26:39

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Carttes 2

Ah oui, bien plus facile en effet.

1. Un arrangement de cartes donné ne peut transformer notre paquet qu'en un seul autre arrangement. Ça paraît logique, mais c'est très utile pour la suite.

2. Il n'y a qu'un nombre fini d'arrangements

3. Supposons un arrangement initial qu'on peut transformer sans s'arrêter. Dans ce cas, on doit forcément revenir sur un arrangement qu'on a déjà vu (d'après 2.), et du coup à partir de celui-là, nos transformations vont forcément "tourner en boucle" (d'après 1.) Donc si une série de transformation ne s'arrête jamais, c'est qu'elle boucle (c'est pas aussi évident que ça en a l'air).

4. La première carte ayant une valeur V, elle se retrouvera toujours en position V après inversion.

5. Supposons un arrangement initial qu'on peut transformer sans s'arrêter. Dans ce cas, il boucle à partir d'une certaine carte. Soit V la plus grande valeur de carte qu'on peut avoir en première position parmi celles qui sont dans la boucle. Après transformation, cette carte se retrouve en position V. Toutes les premières cartes suivantes dans la boucle sont inférieures à V, donc aucune d'entre elles n'inversera les cartes au delà de la v-ième, et du coup la carte V restera toujours en position V. Elle ne peut donc pas revenir en 1ère position, ce qui est absurde vu qu'il doit s'agir d'une boucle.

Il n'existe donc pas d'arrangement initial tel que la série de transformation ne s'arrête jamais.

 #6 - 03-03-2011 11:09:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

carres 2

Bonnes réponse d'Irmo et Scarta smile

Vasimolo

 #7 - 03-03-2011 11:46:34

debutant1
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 116

carres 2

vrai pour 1,2,3 cartes

les cartes n'ont de valeur qu'en position 1
le nombre de combinaisons est fini


supposons que c'est vrai pour n-1 cartes

pour n cartes 3 choix possibles :
.......... la carte n est en position n.......  on retombe au cas n-1
........ la carte n ne passe pas en position 1 et le jeu se termine comme un jeu n-1

........ la carte n passe en position 1 et immédiatement  en position n


donc le jeu s'arrêtera pour n cartes

 #8 - 03-03-2011 14:50:10

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Cartees 2

Oui, le 1 finit toujours par arriver en position 1.

Preuve :

Soit [latex]L_0[/latex] liste des numéros en situation initiale, et [latex]L_{i}[/latex] liste des numéros à l'étape [latex]i[/latex].

Pour [latex]0\leq j\leq n[/latex],[latex] L_i(j)[/latex] est le [latex]j[/latex]-ème élément de la liste [latex]L_i[/latex].

Supposons par l'absurde que :

(Hyp. 1) le [latex]1[/latex] ne soit jamais en tête (=[latex]\forall i\geq 0: L_i(1)\neq 1[/latex]), alors [latex](L_i)_{i\geq 0}[/latex] est une suite infinie sans point fixe.

Soit [latex]E[/latex] l'ensemble des nombres [latex]k[/latex] qui se retrouvent en tête (en position [latex]1[/latex]) à une étape [latex]i_k[/latex],  [latex]E=\{k~/ 1\leq k\leq n \wedge L_{i_k}(k)=k\}[/latex], et soit [latex]m[/latex] le cardinal de [latex]E[/latex].  Etant donné qu'un élément [latex]k[/latex] qui est en tête à une étape, est à sa place à l'étape suivante (i.e. en position [latex]k[/latex]), [latex]E[/latex] représente aussi bien l'ensemble non-vide des éléments qui sont à leur place à une certaine étape. Bien sûr, ils peuvent éventuellement rebouger pendant les étapes ultérieures.

Soit [latex]k_1[/latex] le plus grand élément de [latex]E[/latex], [latex] k_2[/latex] le second plus grand, ...,[latex] k_j[/latex] le [latex]j[/latex]-ème plus grand, etc

On constate qu'au-delà de l'étape [latex]i_{k_1}[/latex] l'élément [latex]k_1[/latex] est à sa place (c-à-d [latex] L_{i_{k_1}}(k_1)=k_1[/latex]) et ne bougera plus ; en effet, pour qu'il bouge il faudrait qu'apparaisse en position [latex]1[/latex] un élément plus grand que [latex]k_1[/latex],
or [latex]k_1[/latex] est le plus grand des éléments susceptibles de se retrouver en position [latex]1[/latex].

En raisonnant de même sur le 2ème plus grand de [latex]E[/latex], on peut généraliser : au-delà de l'étape [latex]i_{k_j}[/latex] les éléments [latex]k_1,k_2,...,k_j[/latex] sont à leur place et ne bougent plus. 

Mais comme le cardinal [latex]m[/latex] de [latex]E[/latex] est fini, au-delà de l'étape [latex]i_{k_m}[/latex] plus aucun élément ne bouge, autrement dit [latex] L_{i_{k_m}} = L_{i_{k_m}+1}[/latex], or ceci n'est pas possible, sauf si [latex] L_{i_{k_m}}(1)=1[/latex] contrairement à l'hypothèse (1).

Mais ... où as-tu déniché ça ???

 #9 - 03-03-2011 22:34:12

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

carted 2

Bravo aussi à Débutant et Gasole smile

Vasimolo

 #10 - 04-03-2011 00:32:40

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

cattes 2

Vraiment, j'ai adoré ce petit problème... je suis immensément curieux de savoir d'où tu le sors ? De ton imagination ? C'est un secret ? smile

 #11 - 04-03-2011 14:44:58

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

caryes 2

Je tente donc un raisonnement par récurrence pour montrer que quelque soit n, le processus se termine toujours.

pour n=2 : que l'on parte de 12 ou 21 on aboutit à 12.

si on suppose la proposition vraie pour n
Premier cas : la carte n+1 est au fond du paquet
On se ramène alors au cas à n cartes, car la carte n+1 de bougera pas du fond du paquet.
Second cas : la carte n+1 est en tête du paquet
On se ramène au premier cas car à la manip suivante, la carte n+1 se retrouvera au fond du paquet
Troisième cas : la carte n+1 n'est ni au fond ni en tête du paquet
Appelons k la carte du fond du paquet. En fait le rôle joué par les cartes n+1 et k peuvent s'inverser. En effet, si k=1, l'idée est d'amener forcément la carte n+1 en tête du paquet. Or si on remplace n+1 par 1, cela ne change rien : le 1 ne joue aucun rôle dans les suites de manipulations, uniquement quand il arrive en tête du paquet où tout s'arrête. Donc d'après la proposition au rang n, on sait qu'on va pouvoir amener n+1 en tête du paquet, et on se ramène au second cas.
Si k n'est pas égal à 1, cela ne change rien, on peut échanger le rôle de n+1 et k. On se ramène alors au rang n, avec les cartes {1,...,k-1,k+1,...,n+1}. Si on avait besoin du k en tête du paquet pour résoudre le problème, alors on va arriver à amener n+1 en tête de paquet, et on se ramène au cas 2. Sinon, le 1 arrivera en tête du paquet
Donc proposition vraie au rang n+1

Et le processus s'arrête quelque soit n !

Je crois qu'on peut même montrer que le processus s'arrête en au plus n étapes ?

 #12 - 05-03-2011 00:49:15

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

vartes 2

J'ai de sérieux doutes à propos de ta solution 007 smile

Vasimolo

 #13 - 05-03-2011 00:55:24

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

cattes 2

Ah, il existe donc des contre-exemples ...
Pour quel n ?
J'arrive pas à voir l'erreur de ma démo, du coup sad

 #14 - 05-03-2011 01:00:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Cartees 2

Le résultat est juste mais j'ai des doutes sur la "démo" smile

Vasimolo

 #15 - 05-03-2011 01:23:57

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

vartes 2

Je parie que c'est le dernier cas qui pose problème.
Sur un exemple je vais essayer d'expliquer mon raisonnement.

Prenons la permutation 8 4 5 2 1 7 9 3 6
Ici k=6 et n+1=9
Tant que 9 n'est pas arrivé en tête du paquet, le 6 va rester au fond. Et quand il arrive en tête du paquet, on se ramène aux autres cas.

Si on imagine qu'on avait la série 8 4 5 2 1 7 6 3, on sait d'après le rang n qu'on peut amener le 1 en tête de paquet.
Si cela peut se faire sans l'aide du 6 en tête du paquet, alors le 6 peut valoir n'importe quelle valeur (en l'occurrence ici 9), cela ne changera rien. Et le 1 arrivera en tête.
Si par contre on a besoin du 6 en tête, alors on fait les manip sur la config de départ comme si le 9 était un 6, et au moment où le 6 arrive en tête de paquet, on se souvient qu'en fait il est un 9, et on se ramène aux cas précédents.

Y a une escroquerie quelque part ? Je n'ai quasi aucun doute sur ma démo, donc ça veut certainement dire que je fais une boulette quelque part hmm

 #16 - 05-03-2011 10:22:52

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Crates 2

J'ai mis du temps à trouver une démonstration qui me plaise pour ce résultat intuitif : oui, à chaque fois, on arrêtera avec un 1 en première position.

Je propose de procéder par récurrence :

Pour 2 cartes : 1-2 ou 2-1 puis 1-2 sont les seules possibilités de suite, c'est donc vérifié.

Pour n cartes :
1er cas : la carte de valeur n est en position p (p<n). On la remplace par la carte de valeur q qui était en position n.
On a donc maintenant les n-1 premières cartes de valeur 1 à n-1, au peut donc appliquer l'hypothèse de récurrence, et on sait que l'on arrivera à un état fixe commençant par 1.
Si on a atteint cet état fixe sans passé par une étape où la carte de valeur q est passée en position 1, alors cette la valeur de cette carte n'a pas eu d'importance et on on remet la carte de valeur q à la place de la carte de valeur n et le tour est joué.
Si on a atteint la carte de valeur q a atteint la position 1, alors on doit refaire le remplacement maintenant. La carte de valeur n est alors en position 1, à l'étape suivante elle sera en position n (et l'on se retrouve dans le second cas).
2ème cas : la carte de valeur n est en position n. On applique l'hypothèse de récurrence sur les n-1 première cartes et le tour est joué.

Conclusion : les manipulations ne dureront pas indéfiniment.

 #17 - 05-03-2011 11:10:42

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Carets 2

Bonne démo de 007 ( j'avais mal compris ) et de Dylasse smile

On peut faire très très court avec un peu d'astuce !!!

Vasimolo

 #18 - 05-03-2011 12:40:23

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

cattes 2

Oui, sûrement qu'il y a une astuce... mais avec l'astuce le problème n'est pas de l'avoir (on est tous plus ou moins astucieux) mais de la trouver. Un indice pour cette astuce ?

 #19 - 05-03-2011 12:44:59

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

xartes 2

Il y a plusieurs façons ; l'une d'elle est de considérer la valeur de la plus grande carte passant en position 1 .

Vasimolo

 #20 - 05-03-2011 12:46:47

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Cartes 22

Ben c'est ce que j'ai fait pour l'instant... c'est mon [latex]k_1[/latex] parce qu'on sait qu'après elle ne bougera plus.

 #21 - 05-03-2011 18:01:53

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

artes 2

Beaucoup de bonnes réponses smile

J'avais vu la solution comme ça , mais on peut bien sûr faire autrement :

On note V la valeur de la carte la plus haute passant sur le dessus du tas . Elle ne peut pas revenir en position 1 car après 1 elle passe en position V . On note V la nouvelle valeur de la carte la plus haute passant en position 1 , ...

Merci pour la participation smile

Vasimolo

PS pour Gasole : Je tiens à jour depuis très longtemps des petits carnets dans lesquels je note des problèmes glanés à droite et à gauche ainsi que quelques idées personnelles . J'ai le défaut de ne pas noter les références à supposé que je les aie connues à un moment ou un autre . Pour celui-ci je ne peux pas te répondre , il fait parti de ceux que je préfère car il ne demande pratiquement aucune connaissance : c'est trop facile ( mais sans intérêt ) de coincer tout le monde avec un résultat super pointu smile

 #22 - 05-03-2011 19:06:18

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

caetes 2

Super ton petit carnet alors big_smile

J'adore les petits problèmes qui en sortent, et je partage ton point de vue sur celui-ci !

 #23 - 05-03-2011 19:09:06

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

Cartes

Les tests que j'ai faits sur n=4 montrent que ça se termine en au plus 4 étapes.
Vous pensez que c'est vrai quel que soit n ?

 #24 - 05-03-2011 19:41:30

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Cartes

En partant de 24153 il faut 6 étapes... n+1 au plus ?

 #25 - 05-03-2011 20:05:21

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1986
Lieu: Paris

aCrtes 2

Evidemment, il aurait fallu que je teste sur n=5 ...
Je pense donc que ma conjecture, même avec n+1, est à jeter à la poubelle smile

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete