Dénombrement : Qui est le bluffeur ?

[Bouchra]

Bonjour, voici une question que je me suis posé :

Soit n joueurs : 1,2,...,n :
Chaque joueur vote contre un autre joueur . les votes sont simultannés (genre : qui est le bluffeur? , le maillon faible ... :lol2: ). le joueur contre qui la majorité des joueurs a voté sera éliminé, il se peut qu'il y ait pas élimination
(par ex pour n= 4 : 3 3 1 1 : les joueurs 1 et 2 on voté contre le joueur 3 et les joueurs 3 et 4 contre 1).

Quel est la probabilité que le joueur 1 soit éliminé ?


---
Le nombre de votes possibles est bien sûr : (n-1)^n : (c'est le nombre de nombres à n chiffres qui peuvent être écrits en utilisant 1,2,...,et n, et tels que le ième chiffre est différent de i en partant de gauche).

On doit donc chercher N_n = le nombre de votes qui éliminent le joueur 1 : c'est le nombres de nombres à n chiffres écrits en utilisant 1,2,.. et n tels que le ième chiffre est différent de i, et où le nombre du chiffre 1 apparait plus (strictement) que les autres chiffres .

je trouve :
N_2 = 0
N_3 = 2
N_4 = 15
N_5 = 136
N_6 = 938
(sauf erreur).

Peut-on trouver une formule générale pou N_n ?
Merci d'avance pour vos réponses .

[aviateurpilot]

par ex pour n= 4 : 3 3 1 1

si les joueurs 1 et 2 ont voté contre le joueur 3 et les joueurs 3 et 4 contre 1
alors
2 votes contre le joueur 3
2 votes contre le joueur 4
0 votes contre le joueur 1
0 votes contre le joueur 2
donc 2 2 0 0 , pas 3 3 1 1
sinon j'ai pas compris l'exemple

[aviateurpilot]

just pour t'aider bouchra (si j'ai compris la question)

les sont des entiers naturels.


avec =le nombre de cas ou il existe j avec quelque soit i de
{}{}

[Bouchra]

Pour l'exemple 3 3 1 1 , en fait je présente les votes comme ceci :

Code: Tout sélectionner

Joueur                1     2      3   ....    n
Vote contre          f(1)  f(2)  f(3)        f(n)

f étant une application de {1, ..., n} dans {1, ...,n} qui ne
garde aucun point fixe (pour tout i de {1,...,n}, f(i) est
différent de i )

Sinon pour ton expression de N_n, il me semble que ça ne colle pas : par ex pour n=2, N_2 = 0 car la seule application f est : 2 1 qui n'élimine pas le joueur 1 .

[aviateurpilot]

moi j'ai vu le probleme d'une autre façon
est le nombre de votes contrer
il se peux que

[tize]

Le problème a l'air interessant, je chercherai mais par simple curiosité : d'ou vient-il ? Tu vas prochainement participer au Maillon faible ou c'est une question d'exam ...?

[Flodelarab]

Je suis en train d'y réfléchir. c très intéréssant car pas tout cuit.

Je suis pas d'ac avec tes chiffres.
Je pense plutot qu'on a :
N_2 = 0
N_3 = 2
N_4 = 6
N_5 = 18
N_6 = 45

La majorité des votes étant des votes d'égalité.

I'll be back!

[Bouchra]

moi j'ai vu le probleme d'une autre façon
est le nombre de votes contrer
il se peux que

Le problème c'est que, pour n=2 par ex, on ne peut pas avoir a_1 (nombre de votes contre le joueur 1 ) = 2 (donc a_2 =0) parce que le joueur 1 n'a pas le droit de voter contre lui .


> Tize : Pour l'origine de l'exo, je me suis posé la question comme ça en regardant "Qui est le bluffeur ?" Lol.

> Flodelarab :
Euh, pour moi : N_4 = 15 car :
2 3 1 1
2 4 1 1
3 4 1 1
4 3 1 1
2 1 1 3
3 1 1 2
4 1 1 2
4 1 1 3
2 1 4 1
3 1 2 1
3 1 4 1
4 1 2 1
2 1 1 1
3 1 1 1
4 1 1 1

--
Ravie que ça vous intéresse :we:

[Bouchra]

On doit donc chercher N_n = le nombre de votes qui éliminent le joueur 1 : c'est le nombres de nombres à n chiffres écrits en utilisant 1,2,.. et n tels que le ième chiffre est différent de i, et où le nombre du chiffre 1 apparait plus (strictement) que les autres chiffres .

je voulais bien sûr dire : ... le chiffre 1 apparait plus (strictement) que les autres chiffres.

[kazeriahm]

je dis peut etre une connerie mais il me semble que chaque joueur a la meme probabilité d'etre eliminé (on néglige le caractere humain lol) donc la probabilité que le i-eme joueur soit éliminé n'est elle pas de 1/n ?

enfin je vois pas dans ton énoncé de contraintes particulières qui fasse que le joueur 1 ait plus ou moins de chance d'etre eliminé que les autres (tu poses la question pour le joueur 1).

[Bouchra]

Oui oui, la probabilité p que le joueur i soit éliminé est la même pour tout i, mais on n'a pas n*p = 1, mais plutot n*p + q =1 avec q probabilité qu'aucun des joueurs ne soit éliminé, enfin il me semble. A confirmer .

[kazeriahm]

Ok autant pour moi

mais ca parait très compliqué alors parce que deja comme vous l'avez dit si n est impair, q=0, si il est pair ca revient a calculer le nombre de fonction f de {1,...,n} dans lui meme tel que pour tout i, il existe j different de i verifiant f(i)=f(j). Ensuite tu divises ce nombre par n^n et ca te donne q ?

[Bouchra]

mais ca parait très compliqué alors parce que deja comme vous l'avez dit si n est impair, q=0

Si n est impair, on n'a pas forcément q=0 (j'ai pas dit ça ), il y a déjà les dérangements (bijections qui ne gardent aucun point fixe) , ex : pour n= 5 ,
2 3 4 5 1.

ca revient a calculer le nombre de fonction f de {1,...,n} dans lui meme tel que pour tout i, il existe j different de i verifiant f(i)=f(j). Ensuite tu divises ce nombre par n^n et ca te donne q

on peut avoir ceci comme vote : 2 4 4 3 3 1 et donc pas d'élimination même si il n'existe pas de j différent de 1, f(1)=f(j)=2 .
je dirais plutôt :
q = A_n/(n-1)^n avec A_n le nombre d'applications de {1,...,n} dans {1,..,n} qui ne gardent aucun point fixe et telles que euh .. . je préfère dire que c'est le nombre de nombres écrits en utilisants les chiffres 1,2,... et n tels que le ième chiffre est différent de i , et tels que, si on note r_i le nombre du chiffre i, et j tel que r_j est le plus grand, j ne soit pas unique .

Effectivement ça parait très compliqué et l'est sans doute, j'ai pensé à calculer q et en déduire p, mais aparemment c'est pas plus simple. :lol2:
Une autre vision peut-être ?

[kazeriahm]

oula j'ai du mal... effectivement t'as raison Bouchra par rapport à mes erreurs...
parcontre je comprends pas pourquoi tu veux regarder les dérangements...
le joueur i peut avoir i voix et ne pas etre eliminé car deux autres joueurs auront le meme nombre de voix, maximal

donc on cherche le nb de fonctions f tq sup(f sur {1...n}) est atteint au moins deux fois...

[Bouchra]

Euh je crois que ton f(i) correspond au nombre de votes contre le joueur i. C'est ça ? Si oui f va de {1,...,n} dans {0,...,n}, non ?

Mon f(i) correspond au joueur contre lequel le joueur i a voté , d'où les dérangements .. (le joueur i n'a pas le droit de voter contre lui-même)

Et je n'utilise pas la première f paske y a des f qui ne peuvent pas exister dans le jeu. pour n=2, on peut pas avoir 2 votes contres le joueurs 1 et 0 votes contre le joueur 2 .

[kazeriahm]

bah ouai mais un dérangement c'est une bijection non?

dans ton cas c'est pas une bijection puisque tu veux que deux joueurs différents votent pour le meme...

enfin bref ca par en ******

[Bouchra]

J'avoue que ce n'est pas très clair, ce que j'ai dit. Quand je parle des dérangements, je parle d'une catégorie de votes qui n'éliminent aucun joueur. Pour moi f lie i de {1,...,n} à f(i) de {1,...,n} avec f(i) = j le joueur contre qui le joueur i a voté . je sais pas si c'est plus clair.

Peux-tu me montrer tous les votes possibles pour 3 joueurs pour voir si on parle de la même chose ? Pour moi, il y en a 8 :
2 1 1
2 1 2
2 3 1
2 3 2
3 1 1
3 1 2
3 3 1
3 3 2

avec a b c signifie : le joueur 1 vote contre le joueur a, le joueur 2 contre le joueur b, et le joueur 3 contre le joueur c .

merci .

[kazeriahm]

oui je suis daccord avec toi.

ce que je veux dire en fait c'est que très compliqué (j'en reviens à ton q, n*p+q=1) parce qu'on ne dénombres meme pas une sous partie de l'ensemble des bijections de {1...n} (si ca avait été le cas, et si on avait réussi à dénombrer et à diviser par n!=cardinal de l'ens des bijec....).

Enfin bref on se comprend. :we:

[Quidam]

Bonjour,

Très intéressant comme problème. Merci de l'avoir posé. Je ne trouve pas de solution générale, mais pour faire avancer la réflexion, j'ai fait un petit programme qui compte tout simplement tous les cas.

J'ai passé en revue tous les votes possibles (n^n) en éliminant au passage les votes non valables, ceux où un ou plusieurs des joueurs votent pour eux-mêmes.

Je trouve en résumé :

Code: Tout sélectionner

N_2 =       0 (sur         1 vote  valable)
N_3 =       2 (sur         8 votes valables)
N_4 =      15 (sur        81 votes valables)
N_5 =     136 (sur      1024 votes valables)
N_6 =    1515 (sur     15625 votes valables)
N_7 =   21486 (sur    279936 votes valables)
N_8 =  377216 (sur   5764801 votes valables)
N_9 = 7866216 (sur 134217728 votes valables)

Je suis conscient qu'il ne s'agit pas de maths ! Simplement, il m'est arrivé de résoudre un problème par un petit test numérique qui m'a mis sur la voie. Cela dit, ces résultats ne m'inspirent toujours pas, mais peut-être quelqu'un aura une idée...

Ci-dessous, les résultats détaillés.

Avec 2 joueurs...
Trouve 4 cas 1 votes valables et 3 votes non valables
Dans 0 cas élimination du joueur 1 (idem pour les autres)
Dans 1 cas égalité
2 X 0 + 1 = 1 cas !

Avec 3 joueurs...
Trouve 27 cas 8 votes valables et 19 votes non valables
Dans 2 cas élimination du joueur 1 (idem pour les autres)
Dans 2 cas égalité
3 X 2 + 2 = 8 cas !

Avec 4 joueurs...
Trouve 256 cas 81 votes valables et 175 votes non valables
Dans 15 cas élimination du joueur 1 (idem pour les autres)
Dans 21 cas égalité
4 X 15 + 21 = 81 cas !

Avec 5 joueurs...
Trouve 3125 cas 1024 votes valables et 2101 votes non valables
Dans 136 cas élimination du joueur 1 (idem pour les autres)
Dans 344 cas égalité
5 X 136 + 344 = 1024 cas !

Avec 6 joueurs...
Trouve 46656 cas 15625 votes valables et 31031 votes non valables
Dans 1515 cas élimination du joueur 1 (idem pour les autres)
Dans 6535 cas égalité
6 X 1515 + 6535 = 15625 cas !

Avec 7 joueurs...
Trouve 823543 cas 279936 votes valables et 543607 votes non valables
Dans 21486 cas élimination du joueur 1 (idem pour les autres)
Dans 129534 cas égalité
7 X 21486 + 129534 = 279936 cas !

Avec 8 joueurs...
Trouve 16777216 cas 5764801 votes valables et 11012415 votes non valables
Dans 377216 cas élimination du joueur 1 (idem pour les autres)
Dans 2747073 cas égalité
8 X 377216 + 2747073 = 5764801 cas !

Avec 9 joueurs...
Trouve 387420489 cas 134217728 votes valables et 253202761 votes non valables
Dans 7866216 cas élimination du joueur 1 (idem pour les autres)
Dans 63421784 cas égalité
9 X 7866216 + 63421784 = 134217728 cas !

[Bouchra]

kazeriahm : On est d'accord :happy2: .

Quidam :
Merci bcp pour tous ces détails.
J'ai tapé les premiers termes de la suite N_n ici (un site qui regroupe plein de suites), et elle y est pas.
Pour l'instant, je reconnais juste le nombre de votes valables qui est (n-1)^n ...


Et je me demande si on peut pas trouver une autre relation qui relie N_n et le nombre de cas d'égalité A_n ...

Excusez-moi si je dis trop de choses à la fois..