Un ami en commun
Bonjour.
Mon message concerne l'exercice suivant.
On se donne deux entiers naturels $n$ et $m$ tels que : $n > m$.
On considère une assemblée de $n$ personnes dans laquelle chacun a exactement $m$ amis (au sein de cette assemblée).
On choisit deux personnes.
Quelle est la probabilité que ces deux personnes aient au moins un ami en commun ?
Mon idée a été celle-ci.
On assimile l'ensemble des $n$ personnes à $E= \llbracket 1 , n \rrbracket$.
À toute personne de l'assemblée, on associe une partie à exactement $m$ éléments de $E$.
Dénombrer les personnes n'ayant pas d'amis en commun, c'est dénombrer les couples $(U, V)$ de parties $E$ à $m$ éléments et disjointes.
Il y en a $\binom{n}{m} \times \binom{n-m}{m}$
La probabilité que les deux personnes n'aient aucun ami en commun est alors : $ \dfrac{\binom{n}{m} \times \binom{n-m}{m}}{\binom{n}{m}^2} $
d'où la probabilité que deux personnes aient au moins un ami en commun : $1- \dfrac{\binom{n}{m} \times \binom{n-m}{m}}{\binom{n}{m}^2} $
Voilà ce à quoi j'ai abouti et ce par quoi j'ai cru être convaincu ...
Qu'en pensez-vous ?
Je suis en fait gêné par le fait qu'en fin d'exercice, une application numérique est demandée avec $n=10^5$ et $m=200$.
Et comme (avec des moyens numériques classiques) de telles quantités sont impossibles à considérer (l'expression ne se simplifie pas très bien ça laisse d'énormes quantités), j'en suis venu à me dire qu'il y avait une erreur dans mon résultat (peut-être était-ce une erreur de dénombrer les couples de parties ...).
Auriez-vous une idée ?
Je vous remercie.
Mon message concerne l'exercice suivant.
On se donne deux entiers naturels $n$ et $m$ tels que : $n > m$.
On considère une assemblée de $n$ personnes dans laquelle chacun a exactement $m$ amis (au sein de cette assemblée).
On choisit deux personnes.
Quelle est la probabilité que ces deux personnes aient au moins un ami en commun ?
Mon idée a été celle-ci.
On assimile l'ensemble des $n$ personnes à $E= \llbracket 1 , n \rrbracket$.
À toute personne de l'assemblée, on associe une partie à exactement $m$ éléments de $E$.
Dénombrer les personnes n'ayant pas d'amis en commun, c'est dénombrer les couples $(U, V)$ de parties $E$ à $m$ éléments et disjointes.
Il y en a $\binom{n}{m} \times \binom{n-m}{m}$
La probabilité que les deux personnes n'aient aucun ami en commun est alors : $ \dfrac{\binom{n}{m} \times \binom{n-m}{m}}{\binom{n}{m}^2} $
d'où la probabilité que deux personnes aient au moins un ami en commun : $1- \dfrac{\binom{n}{m} \times \binom{n-m}{m}}{\binom{n}{m}^2} $
Voilà ce à quoi j'ai abouti et ce par quoi j'ai cru être convaincu ...
Qu'en pensez-vous ?
Je suis en fait gêné par le fait qu'en fin d'exercice, une application numérique est demandée avec $n=10^5$ et $m=200$.
Et comme (avec des moyens numériques classiques) de telles quantités sont impossibles à considérer (l'expression ne se simplifie pas très bien ça laisse d'énormes quantités), j'en suis venu à me dire qu'il y avait une erreur dans mon résultat (peut-être était-ce une erreur de dénombrer les couples de parties ...).
Auriez-vous une idée ?
Je vous remercie.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Il me semble qu'il n'y a pas de bijection allant de l'ensemble des personnes vers l'ensemble des parties à $m$ éléments. Pour des petites valeurs la formule est clairement fausse (pour $n = 2 > m = 1$ par exemple).
On a 2 personnes A et B, dans une assemblée de $n$ personnes.
A a $m$ amis.
Autrement dit : on a une urne avec $n$ boules dont $m$ sont rouges.
B a $m$ amis.
Autrement dit : on tire $m$ boules.
Quelle est la proba que A et B aient un ami en commun ?
Autrement dit, en résumant tout :
On a une urne avec $n$ boules dont $m$ sont rouges. On tire $m$ boules, quelle est la proba de tirer au moins une rouge.
Alors oui Lourran, en faisant comme tu le suggères, la probabilité de tirer au moins une boule rouge est alors : $ 1- \dfrac { \binom{n-1-m}{m}}{ \binom{n-1}{m}}$
Quant à ta remarque Bibix, le problème de la schizophrénie des personnes doit pouvoir se régler en remplaçant $n$ par $n-1$.
À ce problème près, on obtient alors l'expression que j'avais proposée.
Mais je suis assez dérangé par l'application numérique qui est demandée ($n=10^5, \ m=200$), vu l'énormité des quantités qui interviennent.
J'aurais donc deux questions :
- sommes-nous bien d'accord sur l'expression obtenue (la probabilité qu'ils aient au moins un ami en commun est $ 1- \dfrac { \binom{n-1-m}{m}}{ \binom{n-1}{m}}$) ?
- comment peut-on s'en sortir raisonnablement avec l'application numériques ($n=10^5, \ m=200$)
Chaque $C(n,p)$ peut être réécrit avec des factorielles, et il y a plein de choses qui se simplifient.
Peut-être qu'après ces simplifications, l'application pour n=10^5 sera réaliste.
En tout cas, un tableur quelconque me paraît suffisant pour faire ces calculs.
Chaque $C(n,p)$ peut être réécrit avec des factorielles, et il y a plein de choses qui se simplifient.
Peut-être qu'après ces simplifications, l'application pour n=10^5 sera réaliste.
En tout cas, un tableur quelconque me paraît suffisant pour faire ces calculs.
Alors on obtient : $\dfrac{\binom{n-1-m}{m}}{\binom{n-1}{m}} = \dfrac{(n-1-m)!}{m! \times (n-1-2 m) !} \times \dfrac{(n-1-m)! \times m !}{(n-1)!} = \dfrac{[(n-1-m)! ]^2}{(n-1)! \times (n-1-2m)!}$
Donc sauf erreur de ma part, ça fait "assez peu de choses" ($m!$) qui se simplifient ...
Numériquement c'est donc encore compliqué.
La personne B a $m$ amis.
On pourrait se poser la question : quid si B a A comme Ami, mais qu'il n'y a aucun individu C qui soit ami de A et ami de B. On va négliger ce point, en considérant que chaque individu a $m$ amis, dont lui même. Peu importe.
A a $m$ amis (donc $m$ individus rouges dans l'urne, qui en tout en contient $n$)
B a $m$ amis.
Quelle est la proba que le 1er ami de B ne soit pas parmi les $m$ individus rouges : $\frac{n-m}{n}$
Quelle est la proba que le 2ème ami de B ne soit pas non-plus parmi les $m$ individus rouges : $\frac{n-m-1}{n-1}$
Quelle est la proba que le m -ème ami de B ne soit pas non-plus parmi les $m$ individus rouges : $\frac{n-m-m}{n-m}$
Je mets non-plus en gras, volontairement : on est dans des probas 'conditionnelles'.
Quelle est la proba que tout ceci se produise simultanément : le produit de ces $m$ fractions : $\prod_{k=0}^{m-1} \frac{n-m-k}{n-k}$
Application numérique
$n=10^5$
$m=200$
$P$ peut être approximé par la formule $P= (\frac{10^5-300}{10^5-100}) ^{200}$ , ce qui donne $0.67$ : proba que A et B n'aient aucun ami en commun. ( $0.6697841$ avec la formule précise, $0.6697828$ avec l'approximation proposée, les 5 premières décimales sont identiques)
On a une assemblée de $n$ personnes, personne ne se connait, chaque personne va devenir ami aléatoirement avec exactement $m$ personnes, quelle est la probabilité que 2 personnes deviennent amis avec la même personne.
D'un point de vue de graphe tu as $n$ sommets, et ce que tu tires ce sont les arêtes. Mais dans la façon dont tu as écris l'énoncé j'ai l'impression que le graphe est déjà défini (donc il n'y a pas d'arêtes à tirer), et il faut tirer aléatoirement 2 sommets et avec cette formulation il y a le problème déjà cité plus haut : la réponse dépend de la structure du graphe.
Je vais rester sur 100000 personnes, mais chacun a 400 amis ( 399 amis, plus lui même)
Pour 100000 personnes, chacune ayant 399 amis, si on a 250 communautés fermées de 400 individus chacune, B et A ont une chance sur 250 d'être dans la même communauté. Soit ils ont 400 amis en commun, soit ils en ont aucun.
Et à l'opposé, si on a un maillage très lâche, dans lequel 2 personnes ont au maximum un ami en commun (voire 2 ou 3), alors comme $400 \times 400 > 100000$, on peut avoir certains maillages où tous les couples A,B ont au moins un ami en commun
A a 200 amis, donc 200 personnes sur les 100000 ont un marqueur rouge. On choisit aléatoirement 200 personnes (les 200 amis de B ). Quelle est la probabilité qu'au moins une de ces 200 personnes ait un marqueur rouge.
1) est-ce qu'on est forcément ami avec soi-même
2) est-ce qu'on peut être ami avec soi-même
3) est-ce qu'on n'est jamais ami avec soi-même
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Du fait de ces imprécisions, je considère qu'on est dans un exercice '''pour débutants'''. Et c'est d'ailleurs plus ou moins confirmé par les réponses d'Oudich.
L'exercice est pour débutants, le prof a donné un contexte 'original', pour changer des classiques urnes avec des boules, mais dans la tête du prof, c'est un truc simple. Et je pense vraiment que dans la tête du prof, ce que je propose est la bonne réponse. Mais, effectivement, si on est rigoureux, cet exercice n'est pas suffisamment explicite pour qu'on puisse apporter des réponses.
Lou16, tu peux même dire simplement:
"De part et d'autre de $n$ pour $n\in\{1,2,3,4,5,6\}$".
Cordialement,
Rescassol
J'affirme péremptoirement que toute affirmation péremptoire est fausse