Bonsoir StanOfSky!

J'ai réfléchi à ton problème qui me semble très intéréssant. Je me demande dans quel domaine on attend la résolution. J'ai trouvé une modélisation avec des graphes orientés, des circuits eulériens et des anti-arborescences. Est-ce que tu as déjà entendu au moins un de ces termes?

Isis

Vi je connais les graphes orientés, les circuits eulériens et les anti-arborescences. bien que les anti-arborescences je ne pense pas avoir deja utilisé.
je suis parti la dessus aussi.
En fait j'ai deja essayé de modéliser en partant sur un jeu de 13 cartes : 13 paquets de 1 carte.
dans ce cas la j'arrive tres facilement à déterminer le nombre de cas où l'on gagne : 12!
et le nombre de cas total dans le jeu : 1 + 12*2 + 12*11*3 + 12*11*10*4 + 12*11*10*9*5 + ... + 12*11*10*9*8*7*6*5*4*3*2*12 + 12*11*10*9*8*7*6*5*4*3*2*1 = (i=1a12 i*(12!)/(13-i)) +12!
mais bon des que je passe à 52 cartes je sais plus trop comment faire.
Et à vrai dire je bosse sur d'autres choses en meme temps donc je peux pas m'y mettre à 100% (les exams c dans 4 jours)
Je cherche juste une petite idée pour orienté mon raisonnement

merci d'avance pour vos lumières

Oups erreur de raisonnement
le nombre de cas total du jeu c :
1 + 12 + 12*11 + 12*11*10 + .. + 12! + 12! = (i=1a12 12!/(13-i)) +12!

Bonsoir!

Voici enfin mon idée:
Je crée un graphe orienté avec des sommets A,2,...,J,Q,K. Les arcs sont ceux imposés par les positions des cartes. Par exemple si sur le tas A il y a un 10, je mets un arc de A à 10. Chaque distribution de cartes correspond à un graphe avec . En plus la position des cartes sur les tas induit un ordre précis de parcours dans ce graphe. L'algorithme de parcours que tu as proposé s'arrête après avoir éxaminé toutes les cartes si et seulement si ce parcours sur le graphe est un circuit eulérien.

Il y existe un algorithme pour construire un circuit eulérien dans un graphe G=(V,E) connexe avec qui fonctionne comme ça:
(0) Construire une anti-arborescence de racine
(1) Pour chaque sommet x numéroter les arcs sortants de 1 à et l'arc sortant appartenant à l'anti-arborescence prendra l'index .
(2) Partir de r et parcourir le graphe en prennant toujours l'arc non-utilisé de plus petit index.

L'idée de cet algorithme est que l'on peut parcourir le graphe comme on veut tant qu'on se garde pour la fin un chemin permettant de revenir à la racine pour éviter de rester bloqué sur un sommet. Pour ton problème de cartes je vais donc prendre le tas nommé As comme anti-racine. Choisir une anti-arborescence de racine A équivaut à choisir la dernière carte de chacun des tas 2,3,...,K. Donc pour trouver le nombre de distributions de cartes permettant à ton algo de visiter toutes les cartes je propose de fixer la dernière carte de chaque tas sauf A en construisant une anti-arborescences de racine A avec puis en disposant les autres cartes au hasard. Je veux donc compter ces anti-arborescences...

Comme chaque arbre couvrant sur G correspond à exactement une anti-arborescence de racine r fixée, je m'intéresse à compter le nombre d'arbres sur les n=13 sommets. Sur ces arbres (non-orientés) à compter on doit avoir et .

J'ai utilisé un résultat qui dit que sur n sommets on peut avoir arbres. Chacun de ces arbres correspond à un mot de n-2 caractères sur l'alphabet 1,2,3,...,n. Dans le cas des cartes l'alphabet est . Je choisis d'abord l'as qui restera en toute dernière position (4 possibilités) puis ensuite je compose un mot de longueur n-2 avec les 4n-1 caractères restants (à n'utiliser qu'une fois). Il y a donc en tout façons de fixer les dernières cartes des n-1 tas. Il nous reste 3n+1 cartes à distribuer donc (3n+1)! possibilités.

Le nombre de distributions "favorables" est .
Le nombre de toutes les distributions est (4n)!

La probabilité recherché est .

J'ai fait 3 petits exemples de ces arborescences avec n=4. Ces arborescences correspondent aux familles de distributions suivantes:


Cette probabilité est plus élevée que ce que j'attendais, mais je ne vois pas où j'ai commis d'erreur. Puis si c'est juste il y a probablement plus simple, mais j'ai préféré utiliser des outils que je connais bien...

Isis

wow impressionnant!!
c vrai que ca fait un petit moment que je n'ai pas touché aux graphes,et j'étais resté bloqué sur les algos sur les arbres, sur la construction d'automates, donc j'ai pas trop pensé à utilisé des graphes complets et les d+ d- (nombres d'arc entrant/sortant).
Pas assez habitué à utiliser ces outils
J'ai de mon coté essayé de modéliser les combinaisons gagnantes. Et j'ai remarqué que la proba de gagner etait assez importante aussi donc ton résultat ne m'étonne pas.
Je vais réfléchir à ta solution.
J'ai l'impression aussi que l'on doit toujours finir par un AS (la racine du jeu) je n'ai pas réussi à modéliser un seul exemple où l'avant derniere carte serait un AS et la derniere une autre. Dans ce cas j'avais abandonné les graphes, j'étais juste parti sur le fait que la combinaison des dernieres cartes devaient renvoyer un AS quelconque.
ton raisonnement m'a l'air tres bien. juste une petite question, ton resultat : 4* correspond à : 4*(n-2)!* ? tu multiplies par (n-2)! pour avoir le nombre de combinaisons possible avec les n-2 éléments tirés parmis les 4n-1 ?

Effectivement, très impressionnant, Isis

Oui StanOfSky, . Il s'agit de 4 * le nombre de mots de longueur n-2 où toutes les lettres sont disctinctes à choisir parmi 4n-1 lettres. Le 4 est pour choisir la couleur du dernier as, la dernière carte de la dernière pile visitée.

Il se peut que l'avant dernière carte visitée soit un as, mais la dernière ne peut être autre que l'as. On commence le parcours en A et pour visiter toutes les cartes la fin du parcours doit être nécéssairement en A aussi. Autrement ça voudrait dire qu'après le début du parcours en A on est revenu 4 fois en A et qu'on continue le parcours. Ceci n'est pas possible car il n'y a que 4 cartes sur le tas A. Donc dès que le 4^ème As sort la partie est finie.

Isis

decidement les exercices que je donne en DM connnaissent un véritable succes sur ce site c est la seconde personne qui "quémande" la solution sur internet.
d un coté la splendeur du raisonnement ci dessus ne fera pas longtemps illusion.
cordialement

Il faut dire que je ne connais pas trop de méthodes pour résoudre ce genre de problèmes. De plus, bien que formé à l'utilisation des graphes, on ne connait pas assez bien les algorithmes tel que ceux permettant de créer des circuits eulériens. J'ai pensé à utiliser les graphes, mais je ne savais comment bien m'y prendre. J'avais pensé a faire un graphes, avec 4 arcs entrants/sortants sur chacun des 13 sommets mais je se savais pas comment compter le nombres d'arbres ainsi créés.
Il me semblait évident que le choix des dernieres cartes etait le seul impératif mais comment le prouver mathématiquement??

La reponse est-elle juste, vu qu'ISIS en doute un peu.
Auriez vous une autre résolution, plus simple, et plus proche de notre niveau??
a noter que personne n'a su résoudre le probleme...a part ISIS

cordialement