Je bosse en ce moment sur un nouveau prototype de jeu de bluff / ambiance / trahison etc.
J’ai besoin pour ce prototype de calculer des probabilités pour assurer un bon équilibre du jeu.
Seulement je suis une bille en probas et je me suis dit qu’il y avait sans doute ici des joueurs capables de m’aider.
Voilà ce que je cherche à déterminer :
Pour n joueurs, il y a n emplacements disponibles.
Chaque joueur va programmer secrètement l’emplacement qu’il va visiter.
Quelles sont les chances que deux joueurs se retrouvent au même endroit ?
Quelles sont les chances que trois joueurs se retrouvent au même endroit ?
Même question avec n-1 emplacements ?
Exemple : 4 joueurs, 4 emplacements A B C D.
Quelles sont les chances qu’il y ait deux joueurs en A ?
Pour que le jeu fonctionne il faut que les joueurs se retrouvent à deux sur le même emplacement (mais pas à trois) dans une majorité de cas. C’est pour cela que j’hésite à proposer n emplacements ou n-1 emplacements.
Avant de tenter quoi que ce soit, je va8snp’utot invoquer la personne la pexperte du forum AMHA : @ran-cadren, je fais appelle à toi, que les Dieux des mathématiques et des statistiques te donnent la force et le courage de transformer @Transludis en traducteur de chiffres plutôt que de lettres !!!
Sinon je dirais que c’est une loi binomiale de paramètre 2 (soit le nombre de tentatives puisque 2 joueurs) et de p = une combinaison sans répétition de n1 (le nombre d’emplacements) dans n2 (le nombre total de joueurs)
Alors c’est dit à la va-vite avec de vieux restes de mémoire et sans vérification, donc bon, je sens que j’aurais mieux fait de m’arrêter à l’invocation…
Je dirai 1 - (n-1)!/n^3 pour la proba que au moins deux joueurs de retrouvent à la même place.
Il faut que j’y réfléchisse un peu plus pour exactement 2 et exactement 3.
Par contre, pas sûr de piger ce que tu demandes à propos de n-1 emplacements ? Toujours le même nombre de joueurs mais un emplacement de moins ? Ou bien les joueurs ne peuvent choisir que parmi n-1 emplacements ? Et si c’est cette dernière formulation qui correspond à ce que tu cherches, quel est le critère pour choisir les n-1 emplacements possibles pour chaque joueur ?
n joueurs et n emplacements - soit n^^n possibilités (n à la puissance n)
cas 2 joueurs sont au même emplacement : ils peuvent occuper 1 des n emplacements, laissant (n-1) emplacement aux autres. Ils occupent chacun un emplacement différents, il y a donc (n-1)! possibilités pour eux, soit n*(n-1)! combinaisons possibles.
Donc la proba que 2 soient au même endroit (strictement) est de n*(n-1)! / n^^n
Cas 3 joueurs sur le meme emplacement : ils occupent un des n emplacements, laissant les n-1 autres aux autres joueurs.
A priori la proba serait de n*(n-1)! / 2 * n^^n
à 4 joueurs 4*6/256 = 9.375% pour le cas 2 joueurs au meme emplacement, et 4.6875% pour le cas 3 joueurs au meme emplacement
On va considérer que l’on pioche un emplacement parmi les n possibles et que donc le un joueur donné, on a 1/n chance de tomber sur un emplacement.
Le 2eme jouer aura également 1/n chance de tomber sur ce même emplacement ce qui fera qu’on aura (1/n)² chance que les 2 joueurs tombe exactement sur le même emplacement.
Il reste à multiplier cette proba par le nombre de combinaisons possible de « 2ème joueur » … Par exemple, si on joue à 4, il y aura un 1er joueur puis il restera 3 joueurs possible qui pourront tomber sur le même emplacement que le 1er joueur, soit un proba finale de (1/n)² + (1/n)² + (1/n)² = 3/n².
En généralisant à x joueurs et toujours n emplacements, ça ferait (x-1)/n² chance que 2 joueurs tombent sur le même emplacement.
Pour que 3 joueurs tombent sur un même emplacement il ne faudra pas seulement faire une addition mais plutôt multiplier par le nombre de combinaisons possibles de piocher 2 joueurs parmi le nombre de joueurs restant qui peuvent jouer après le 1er.
Soit une combinaison sans répétition de 2 joueurs parmi x-1 joueurs, ce qui nous donne :
C= (x-1)! * 2!(x-1-2)!) = (x-1)! / 2!(x-3)! = (x-1)(x-2)/ 2!
Et on re multiplie le tout par le nombre de joueurs total, x… Ce qui ne reviendrait pas à faire directement une combinaison de 3 joueurs parmi x peut-être ?
Proba finale pour 3 joueurs sur le même emplacements :
x/n³ * ((x-1)(x-2)) / 2!
= (x*(x-1)(x-2)) / (2!*n²) , avec n le nb d’emplacements et x le nb de joueurs…
Ou bien :
1/n³ * (x! / 3!*(x-3)!) = 1/n³ * (x(x-1)(x-2) / 3!)
= (x(x-1)(x-2)) / (3!*n³)
Ça me paraît un peu bancal comme raisonnement mais moins pire que les bêtises que j’ai déjà écrites…
Oui, ça on est d’accord, c’est le nombre de fonctions de {1, …, n} dans {1, …, n}.
Pour qu’ils aient tous des emplacements différents, il faut que la fonction soit une permutation (une bijection de {1,…n} vers lui même). Il y en a n!, donc avec une hypothèse d’uniformité il y a une probabilité n!/n^n d’avoir une configuration avec chacun sur son emplacement.
Donc pour avoir au moins deux joueurs au même endroit, la proba est de 1-n!/n^n.
Après ça se simule très bien. Je viens de faire un bout de code R et pour n=4, on obtient dans environ 70% des cas exactement 2 joueurs au même endroit et les 2 autres sur des emplacements différents (avec 100000 répétitions).
Edit : ah, ah, fun, j’ai trouvé un bug dans ma simulation grâce à mon calcul théorique ! Donc on obtient bien 56% environ dans la simulation.
Le calcul théorique est un peu plus complexe. On a donc deux personnes au même endroit et les n-2 autres sur n-1 emplacements. Ce deuxième terme revient à choisir un élément qu’on ne veut pas et à faire une bijection sur le reste, donc du (n-1)((n-2)!). Pour le premier terme, on choisit les deux mariés (2 parmi n, donc n(n-1)/2) et leur emplacement n. Donc je dirai un truc global en
n^2(n-1)^2((n-2)!)/2 mais il est possible que je compte des choses deux fois, c’est toujours le problème du dénombrement
Et donc si j’ai bon, on a une proba de [n^2(n-1)^2((n-2)!)]/[2n^n]. Pour n=4, ça donne 56.25 %.
Si tu sais programmer (ou au pire si tu arrives à convaincre chatGPT), le mieux est de faire une simulation parce que les calculs sont vites bien chiants, cf au dessus.
Tu pars dans une direction compliquée en utilisant des tirages indépendants comme modèle. C’est le bon modèle, mais en combinatoire on se trompe assez rapidement comme ça. C’est pour ça qu’il vaut mieux raisonner sur l’univers comme je le fais plus haut…
