Problème de combinatoire

[invite7545be06]

Bonjour,

Je ne sais pas vraiment si la question va dans cette partie ou plutôt celle de Mathématiques du collège et du lycée, mais voilà mon problème :

Dans un jeu, on a deux joueurs A et B qui ont autant de chances de gagner à chaque tour. Un match s'arrête dès qu'un des deux joueurs a remporté 4 tours. Il peut donc y avoir au plus 7 tours dans un match. Par exemple, on peut avoir comme enchaînements de tours BBBB, ABABABA, AAABBBB, ...

J'aimerais savoir s'il y a un moyen rapide pour dénombrer toutes les possibilités différentes, ou s'il faut plus ou moins toutes les noter à la main en séparant en différents cas et se demander quelles possibilités il y a pour 4 tours (seulement deux, AAAA ou BBBB), puis pour 5 (8 possibilités il me semble, mais pour 6 et 7 ça devient plus fastidieux et je risque d'en oublier ou d'en compter en double), ...

Merci
-----

[invitec5eb4b89]

Ca dépend : est-ce que tu considères que l'ordre dans lequel les parties sont gagnées est important ? Est-ce que par exemple les suites AAABA et AABAA sont équivalentes ?

[NicoEnac]

Ca dépend : est-ce que tu considères que l'ordre dans lequel les parties sont gagnées est important ? Est-ce que par exemple les suites AAABA et AABAA sont équivalentes ?

Je ne pense pas car sinon AAAAB et AAABA seraient équivalentes alors que la première n'est pas une solution possible (si A gagne 4 fois, le jeu s'arrête)

[invite7545be06]

Oui, l'ordre est important.

[A voir en vidéo sur Futura]

[invitec5eb4b89]

Je ne pense pas car sinon AAAAB et AAABA seraient équivalentes alors que la première n'est pas une solution possible (si A gagne 4 fois, le jeu s'arrête)

Ah oui, mince, ben disons AAABA et AABAA... Mais on a répondu à la question...

Ce n'est pas un problème de dénombrement classique (enfin je ne crois pas). On peut toujours, pour éviter de se casser la tête, générer toutes les possibilités (tous les arrangements de 5, 6 et 7 objets choisis parmi deux) puis éliminer avec un petit programme celles qui ne répondent pas aux critères du problème.

[invite7545be06]

Quel programme ?

[invitec5eb4b89]

Ben par exemple en R (mais on peut peut être le faire sous excel...). J'ai essayé le code suivant quand les parties vont jusqu'à durer 7 tirages :

symb <- c("A","B")
mat    <- permutations(2,7,repeats.allowed=T)
maxnum   <- apply(mat,1,function(l) max(c(sum(l==1),sum(l==2))))
whichmax <- apply(mat,1,function(l) which.max(c(sum(l==1),sum(l==2))))
ind <- which( (maxnum == 4) & (mat[,7] == whichmax) )
apply(matrix(symb[mat[ind,]],ncol=7),1,paste,collapse="")

Comme résultat, je trouve les parties suivantes :

"AAABBBA" "AAABBBB" "AABABBA" "AABABBB" "AABBABA" "AABBABB" "AABBBAA" "AABBBAB" "ABAABBA" "ABAABBB" "ABABABA" "ABABABB" "ABABBAA" "ABABBAB" "ABBAABA"
 "ABBAABB" "ABBABAA" "ABBABAB" "ABBBAAA" "ABBBAAB" "BAAABBA" "BAAABBB" "BAABABA" "BAABABB" "BAABBAA" "BAABBAB" "BABAABA" "BABAABB" "BABABAA" "BABABAB"
 "BABBAAA" "BABBAAB" "BBAAABA" "BBAAABB" "BBAABAA" "BBAABAB" "BBABAAA" "BBABAAB" "BBBAAAA" "BBBAAAB"

J'ai synthétisé le code au maximum, il n'est donc pas très lisible. L'algorithme que j'ai implémenté est le suivant :

1. Générer tous les arrangements avec répétitions de 7 objets choisis parmi 2
2. Repérer parmi les deux objets lequel est majoritaire
3. Garder un arrangement s'il comporte au plus 4 fois l'objet majoritaire et si la dernière occurrence de cet objet apparait pendant le 7eme tirage

Une fois que toutes les possibilités ont été générée, il suffit de les compter !

Voilà, bon courage,
V.

ps : j'ai implémenté le code sous R parce que ça m'amuse, mais je ne pourrai pas t'aider si tu décides de le faire sous excel.