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 - 07-04-2019 15:27:40

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

PPatience

Bonjour à tous, je me suis éloigné du forum pendant un moment, dû à un manque de temps.
Voici une petite énigme pour me faire pardonner:

Dans un livre présentant un certain nombre de patiences et réussites avec des cartes, la première se présente comme suit:

Prendre un paquet de 32 cartes, le mélanger, puis parcourir le paquet en nommant successivement chaque valeur de carte (As, 7, 8, 9, 10, Valet, Dame, Roi, As, 7, 8 ...).
Si l'une des cartes tirées correspond à la valeur appelée, cette carte est retirée du jeu.

Une fois le paquet parcouru, on le reprend dans le même sens (sans le mélanger) et on répète le processus. La patience est considérée comme réussie si toutes les cartes ont été tirées du jeu.

Si lors d'un parcours des cartes, aucune carte du jeu n'est sortie, la patience est perdue, car chaque étape suivante sera identique, et ne fera pas diminuer la taille du paquet.

Exemple:
Supposons qu'il reste les cartes As,8,7,9,Dame dans le paquet
Un appel retirera les cartes 1 et 9
Le paquet sera donc 8,7,Dame
L'appel suivant retirera le 7.
Il restera donc 8 et Dame. La patience s'arrête alors car aucune carte ne pourra plus être sortie.

Il est important de noter qu'il n'y a strictement aucune stratégie, le résultat de la patience est défini dès le début.

Je pense qu'il ne vous faudra pas beaucoup de temps pour vous convaincre que la probabilité de gagner est très très faible lol

Cependant, le problème semble intéressant mathématiquement.

On peut donc considérer le problème généralisé suivant:

Supposons que l'on ait un paquet de carte ou chaque carte possède un numéro entre 1 et n. Pour chaque n, il existe k cartes possédant cette valeur.

Parmi tout les mélanges possibles, combien de mélanges aboutissent à une victoire?

J'ai trouvé la solution pour n=2, la méthode pour le prouver est assez élégante, donc je laisse un peu de temps pour chercher en réponses cachées.
Edit: J'ai également trouvé la solution pour k=2, qui est accessible également

Pour n > 2, le problème est beaucoup plus compliqué et je n'ai pas de réponse, je suis curieux de voir vos pistes.

Un indice dans le cas n=2:
Spoiler : [Afficher le message] Étant donné un configuration gagnante, démontrer que parmi les i premières cartes du jeu (sans en enlever), il y a plus de 1 que de 2 



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 07-04-2019 19:34:12

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 812

patienxe

Pour n=2, les mélanges victorieux sont ceux correspondants à des parenthésages corrects, où 1 correspond à ( et 2 à ). Il y a donc [latex]\dfrac{\binom{2k}{k}}{k}[/latex] mélanges corrects parmi les [latex]\binom{2k}{k}[/latex] mélanges, c'est-à-dire qu'on a une chance sur k de gagner.

 #3 - 07-04-2019 23:51:31

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

Pattience

Ok Ebichu, mais pas pour la valeur
Une petite idée de démo?

 #4 - 08-04-2019 08:47:03

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 812

patoence

Oui, c'est [latex]\dfrac{\binom{2k}{k}}{k+1}[/latex] plutôt.

Pour la démo, si tu prends un parenthésage correct, et si tu considères un "(" qui est à la bonne place (à un rang impair), alors le ")" correspondant est à la bonne place également (à un rang pair) car entre les deux, il y a un nombre pair de symboles ; de même si le "(" est à la mauvaise place. Ainsi, à chaque étape, on va supprimer des paires de parenthèses correspondantes, donc l'étape suivante commencera aussi avec un parenthésage correct, et ce jusqu'à ce que les cartes soient épuisées.

Réciproquement, si tu prends un parenthésage invalide, alors à partir d'un certain rang dans le tirage, il y a strictement plus de parenthèses ")" que de "(". Le tirage commence donc par "{parenthésage valide})". Lors du déroulement du jeu, on va épuiser les cartes du parenthésage valide du début, puis on sera face à un tirage commençant par ")", et cette parenthèse ne sera jamais supprimée.

 #5 - 08-04-2019 09:47:38

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

Pateince

Parfait Ebichu

Pour information, j'ai également résolu le cas ou k=2, qui n'est pas non plus trop compliqué

 #6 - 09-04-2019 16:03:33

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 43

Patiience

Bonjour.

Je traite le cas n=2 (cartes 1 et 2, k fois chacune)

Au maximum k tours possibles. En effet, le 1 doit être en tête à chaque tour (sinon perdu), il disparait à chacun de ces tours, et il y en a k.

Proposition de solution…
Partons de la fin. Lors de l’ultime tour, tous les 1 sont en position impaire et tous les 2 en position paire dans le paquet, puisqu’ils disparaissent tous.
Imaginons qu’il y ait K1 cartes 1. Donc K1-B1 cartes 2 (avec B1 = 0 ou 1 car il y a au plus 1 carte impaire de plus que de cartes paires).

Si cet ultime tour n’est pas le premier, ces cartes sont donc là car elles n’ont pas disparu au tour précédent. Les 1 étaient donc en position paire et les 2 en position impaire.
Lors de ce tour précédent, si K2 cartes 1 avaient été tirées, c’est donc qu’il y avait :
K2 cartes 1 en position impaire
K1 cartes 1 en position paire
K1-B1 cartes 2 en position impaire
K2-B2 cartes 2 en position paire (B2 = 0 ou 1 toujours)

Si ce tour était le premier, on doit avoir K1+K2=K pour les 1, et K1+K2-B1-B2=K pour les 2. Donc B1 = B2 = 0. On peut remonter autant de tour qu’on veut, on aura toujours des Bi =0 à la fin. Je leur tords le cou de cette façon. A chaque tour, autant de 1 que de 2, sinon on ne pourra jamais remonter au tas initial.

Revenons à notre ultime tour.
Si c’est aussi le premier, K1 = K, 1 possibilité
Sinon, 1=<K1<K. (K-1) possibilités.

Au tour précédent (décrit juste avant, sans le B2 donc) :
Si c’est le premier, K1+K2=K, K2 imposé, donc on hérite des possibilités du tour ultime : (K-1)
Si ce n’est pas le premier, (K-1)(K-2)/2 possibilités. Je ne détaille pas.

Au tour encore précédent, K3 cartes 1 ont disparues (et donc K3 cartes 2)
On avait donc
K3 cartes 1 en impair
K1+K2 cartes 1 en pair
K1+K2 cartes 2 en impair
K3 cartes 2 en pair

Si c’est le premier tour, (K-1)(K-2)/2 possibilités, par héritage du tour décrit juste avant
Si ce n’est pas le premier, (K-1)(K-2)(K-3)/6 possibilités. Dont héritera le tour précédent (dans l’ordre du tirage) si c’est le premier…
On peut encore écrire ça sous la forme (K-1) !/[i !*(K-1-i) !, avec i=3. Ce qui marchait aussi avec i=0, 1 et 2 pour les tours déjà décrits.
Comme il y a K tours max, on aura à la fin un nb de possibilités égal à somme( (K-1) !/[i !*(K-1-i) !), avec i variant de 0 à k-1.
Ce qui vaut 2^(K-1) comme le dit Pascal, un de mes potes. Ce qui doit être la solution recherchée si j’ai de la chance.
On peut appliquer la méthode pour K=2 et n quelconque, avec une distribution des K1 au premier tour sur les ‘parités’ distinctes du n° de carte. Mais j’ai un peu la flemme.

La méthode marche mal je pense si n>2 et k>2, car on génère de potentiels doublons en remontant les tours. Et la comptabilité ne sera pas très juste...
Va falloir trouver autre chose.

 #7 - 09-04-2019 20:40:51

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

parience

Toufau
Tu ne peux pas écrire K2-B2 avec B2 = 0 ou 1
En effet, si au dernier tour on avait juste un 1, au tour précédent, on pouvait avoir 111. Dans ce cas, on a B2 = 2.
De plus, je ne sais pas quelle définition tu as choisi pour ton K, mais s'il correspond au k de mon énoncé, on a K1 + K2 = 2K.
Quoi qu'il en soit, que les B_i soit binaires ou non, ton argument pour prouver qu'ils sont nuls tient toujours, et c'est une propriété fondamentale pour calculer le nombre d'issues favorables.

Tes calculs d'après en revanche oublient pas mal de détails.
Si dans le cas des parties en 2 tours, il y a bien K-1 possibilités au deuxième tour, il y a plus de K-1 parties en 2 tours.

Par exemple, si K = 2, voici plusieurs d'exemples de parties en 2 tours qui aboutissent toutes au même résultat lors du deuxième tour:
112212
121122
111222
Ton compte oublie donc beaucoup de résultats.

Pour 3 tours, tu donnes (K-1)(K-2)/2 possibilités.
Je ne sais pas d'où ça sort, mais fais attention, comme avant il y a plusieurs départ qui aboutissent à une même configuration, et ça devient plus compliqué car les 1 ne sont pas tous pairs ou impairs.

En tout cas, la valeur que tu donnes à la fin n'est pas la bonne.


Merci en tout cas pour ta participation, je te conseille d'essayer de conjecturer la forme globale des solutions, la récurrence n'est pas forcément le chemin le plus simple. Sinon, tu peux regarder le problème pour k=2, je l'ai trouvé plutôt plus facile (et ta méthode s'appliquera mieux dans ce cas)

 #8 - 10-04-2019 09:37:02

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 43

Paitence

Caduk.

Effectivement, j’ai un peu oublié les combinatoires possibles en passant d’un tour au précédent… Par exemple pour K=3, pas (k-1)*(k-2)/2 mais (k-1)*(k-2) (deux rangements possibles des cartes du 2eme tour). Ce qui fait au final 1+(k-1)+(k-1)(k-2) = 5 possibilités et non 4. Et le 'déficit' ce gâte de plus en plus… 

Par contre, je ne comprends pas forcément bien certaines de tes remarques

« Si au dernier tour on avait un 1, au tour précédent, on pouvait avoir 111 ». Sauf si j’ai mal saisi l’énoncé, ce n’est pas possible. Si on pouvait avoir 111 à un tour (qui ne peut être le premier), ces 3 cartes 1 auraient été en positions paires le tour précédent, donc précédées de 3 cartes 1 en position impaires (qui ont été tirées), ce qui ferait un déficit de 6 cartes 2 par rapport aux 1…et 12 au tour encore avant, etc. C’est pour ça que les Bi sont tous nuls, dans le cas contraire, on ne peut jamais revenir à un premier tour avec un nombre égal de 1 et de 2.

« on a K1 + K2 = 2K ». Dans l’énoncé, ce n’est pas k cartes de même valeur (K  cartes 1 et k cartes 2) ? si c’est le cas, on a bien k1+k2 =k.

Mais bon toujours est-il que je me suis gourré.

L’autre façon de traiter le pb que j’avais envisagée, et que je n’aimais pas trop, est basée sur une conclusion qu’on peut tirer immédiatement de la méthode de parité que j’utilise : en partant du début du tas, il doit à tout moment y avoir au moins autant de 1 que de 2 tirés. Réciproquement, si c’est le cas, c’est un arrangement gagnant, toujours pour la même raison de parité (autant de 1 en position paires qui restent au tour suivant que de 2 en impaires, etc à chaque tour). Donc il faut dénombrer les positions de départ correspondantes.

Etant assez nul en dénombrement, je ne sais pas faire. C’est pour ça que je n’aime pas trop cette méthode 😊

 #9 - 10-04-2019 11:17:21

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

patiencz

Effectivement, K1+K2 = K, je me suis embrouillé.
Pour les Bi, oui, le déficit augmente à chaque fois, ce qui fait que les Bi ne valent pas 0 ou 1, mais peuvent être plus grand.
Quoi qu'il en soit, ton argument suivant fonctionne quelque soit la valeur de Bi, donc il n'y a pas de problème.

Un indice pour t'aider à aborder le problème:
Spoiler : [Afficher le message] Étant donné un configuration gagnante, démontrer que parmi les i premières cartes du jeu (sans en enlever), il y a plus de 1 que de 2

Sinon, comme je te l'ai dit, le problème est peut être plus facile à aborder pour k = 2, surtout avec ta stratégie initiale.

 #10 - 10-04-2019 13:06:01

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 43

payience

Par rapport à ton indice, c'est la même chose que ce que j'écrivais (peut être mal formulé).
En tout cas c'est bien ce que la méthode de parité permet de démontrer : "sur les p premières cartes, quelque soit p, nb(1)>=nb(2)" Condition nécessaire et suffisante pour que l'arrangement soit gagnant.
Mon problème est juste d'en déduire le résultat...

 #11 - 10-04-2019 19:01:22

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 812

Patieence

Pour le cas k=2, j'ai eu un peu plus de mal à trouver que pour n=2.

Il y a [latex]2^{n-1}[/latex] mélanges, qui sont ceux obtenus en laissant un "1" en première position, puis en plaçant un "2" à un des deux emplacements possibles pour qu'il soit retiré du paquet au premier tour, puis en plaçant un "3" à un des deux emplacements possibles pour qu'il soit retiré du paquet au premier tour... ce qui fait [latex]2^{n-1}[/latex] possibilités. Enfin, dans chaque cas, on remplit les emplacements laissés vides avec 1,2,3... dans l'ordre.

Par exemple, voici un mélange obtenu pour n=5. On place d'abord 2,3,4,5 chacun à une des deux places possibles : 1.34..2..5, puis on remplit les trous avec 1,2,3,4,5 dans l'ordre : 1134232455. Autre exemple : 1.3...2.45 puis 1132342545.

La démo est casse-pieds à écrire, je trouve. Si tu as une version courte, je suis preneur.

 #12 - 10-04-2019 21:14:47

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

patiebce

Toufau
Oui, effectivement, tu avais bien formulé l'argument.
A partir de là, soit tu reconnais une structure mathématique assez connue (mais c'est possible que tu ne la connaisse pas) soit tu cherche à dénombrer. Le problème n'est pas si simple, on peut trouver des formules de récurrence mettant en jeu l'ensemble des dénombrements dans les cas plus petit. On peu aussi réussir à trouver la formule directement, mais ce n'est pas facile à trouver.
Par contre, dans le cas k = 2, le nombre de cas est plus facile à trouver, et sans nécessairement avoir besoin de culture mathématique.

Ebichu
Oui, c'est l'idée, même si je l'exprimais d'une manière légèrement différente. La démo n'est pas si longue ni compliquée. En tout cas, la formule est plus simple que pour le cas n=2

 #13 - 11-04-2019 08:03:07

TOUFAU
Habitué de Prise2Tete
Enigmes résolues : 0
Messages : 43

Paitence

Structure connue sans doute... mais pas de mon coté :-)
J'avais jeté un coup d'oeil sur une logique de récurrence, qui conduit - un peu intuitivement - à un S(n) = (n-3)s(n-1)+n(n+1)/2-1 (à partir de k=3). Donc un truc qui sent fort une série de factoriels pas très sympa.
Je laisse faire les pros.

 #14 - 11-04-2019 19:46:53

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,850E+3

pztience

C'est le principe des mots de Dick (voir du côté des nombres de Catalan)

 #15 - 11-04-2019 21:22:39

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

Paitence

Gwen
Oui!
Et pour k=2?

 #16 - 11-04-2019 23:51:24

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 812

patienve

Je me suis amusé à programmer le cas n=3. Pour k=2, ça fait 4 bons mélanges. Pour k=3, il y en a 32. Pour k=4, ça fait 380. Et pour k=5, il y en a 5531. OEIS ne connait pas cette suite. Et je dois avouer que c'est un sacré sac de noeuds, et que je n'en tire pas grand chose.

 #17 - 12-04-2019 00:18:10

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 284

patoence

Oui, ça se complique beaucoup pour des n plus grands car on n'a plus du tout la structure des mots de Dyck. Cependant, j'ai peut être un début pour généraliser k=3.
Ca me fait penser que le timer es fini, voila ma démo pour k=2:

Si une partie se finit en 2 tours, au deuxième tour, on doit avoir une suite continue et partant de 1. Supposons que la suite aille jusqu'à i

Pour que le paquet d'origine tombe sur cette configuration, il faut que i cartes de 1 à i soit permutées de manière à ce qu'aucune ne se trouve sur sa valeur, les n-i cartes restant à leur place. De plus, il faut que la permutation aboutisse à une configuration triée.
Notons A les k premières cartes et B les k dernières cartes.
Le 1 de A ne fait pas partie de la permutation car il est tiré lors du premier tour.
Soit j la plus grande carte initialement dans A dans la permutation. On a j = i, car si i était dans B, elle resterait à sa place suite à la permutation.

Soit un ensemble de cartes tirées de A (ne contenant pas 1), i sa plus grande valeur.
Une condition nécessaire pour obtenir une permutation valide est que l'on prenne dans B toutes les cartes non prises dans A et inférieure à i.
Cette condition est également suffisante, car si on trie les cartes, aucune ne sera à sa place. En effet, le 1 de B est forcément tiré, les cartes de A restant dans A seront donc au moins décalée de 1 position. Comme la carte i prend la dernière position disponible des cartes de B, les cartes de B restant dans B sont décalées d'au moins une position vers l'avant. Les cartes allant de A vers B ou de B vers A ne peuvent pas tomber sur leur valeur, car elle est déjà occupée.

En conclusion, à tout sous ensemble de [latex]A\backslash\{1\}[/latex] correspond une unique permutation (unique car elle est triée, si on prend 0 cartes, on à la configuration de base sans aucun changement). [latex]A\backslash\{1\}[/latex] est de taille [latex]k-1[/latex], donc il y a [latex]2^{k-1} [/latex] positions possibles

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)
Esmeralda gypsy (1) —

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