|
#1 - 17-10-2013 09:16:26
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
probabilité de tirer des points conqécutifs sur un cercle
Bonjour,
Une petite énigme de dénombrement/probabilité et sa généralisation.
1/ Soit un cercle avec N points, je tire au sort 2 points, quelle est la probabilité que ces 2 points soient consécutifs (côte à côte) ?
2a/ Et avec 3 points, quelle est la probabilité qu'au moins 2 de ces points soient consécutifs (côte à côte) ? 2b/ Quelle est la probabilité que les 3 soient consécutifs ?
3/ Question subsidiaire, donner les 2 formules généralisant ce problème de tirage de n points consécutifs sur un cercle à N points (n<N).
#2 - 17-10-2013 21:06:33
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3221
- Lieu: Luxembourg
Probabilité de tirer ds points consécutifs sur un cercle
Ceci n'est pas un site d'aide aux devoirs ! Bon, une énigme du chef, ça ne se refuse pas, même si j'ai vraiment horreur des probas.
1/ Numérateur = N Dénominateur = N.(N-1) / 2 Rapport = 2 / (N-1) pour N>2
2a/ Numérateur = N.2.(N-2) / 6 Dénominateur = N.(N-1).(N-2) / 6 Rapport = 2 / (N-1) pour N>3
2b/ Numérateur = N Dénominateur = N.(N-1).(N-2) / 6 Rapport = 6 / [(N-1).(N-2)] pour N>3
3a/ Numérateur = N.2.(N-2)! / [(N-n-2)!.(n-2)!] Dénominateur = N! / [(N-n)!.n!] Rapport = 2 / (N-1) pour N>n
3b/ Numérateur = N Dénominateur = N! / [(N-n)!.n!] Rapport = (N-n)!.n ! / (N-1)! pour N>n
Il est surprenant que les questions 1; 2a et 3a aient la même réponse: j’ai dû me planter quelquepart !
#3 - 17-10-2013 22:14:38
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
probabilité de tirer des pointd consécutifs sur un cercle
EfCeBa a écrit:Une petite énigme de dénombrement/probabilité et sa généralisation.
Oh p*tain, une énigme d'EfCeBa ! Hosannah
1/ [latex]\frac{2}{N-1}[/latex] à mon avis : on tire un point au hasard sur le cercle, il reste donc N-1 points dont 2 sont voisins du premier. Le choix du premier point n'est pas vraiment un choix, puisque la situation à l'issue de ce "choix" est toujours exactement la même à une petite rotation près.
2a / Soit le deuxième point est déjà à côté du premier (proba [latex]\frac{2}{N-1}[/latex]) ;
soit il est espacé du premier de seulement un point (proba [latex]\frac{2}{N-1}[/latex]), auquel cas il reste trois positions du troisième point qui vérifient les contraintes de voisinage (proba [latex]\frac{3}{N-2}[/latex])
soit il est plus loin que ça (proba [latex]\frac{N-5}{N-1}[/latex]) et il y a quatre positions du troisième point qui assurent le "voisinage" demandé (proba [latex]\frac{4}{N-2}[/latex])
D'où une proba, après simplification, de [latex]\frac{6(N-3)}{(N-1)(N-2)}[/latex]
2b / Avec la même démarche : [TeX]\frac{2}{N-1} \times \frac{2}{N-2} + \frac{2}{N-1} \times {1}{N-2}[/TeX] soit [latex]\frac{6}{(N-1)(N-2)}[/latex]
3 / Ouhlà, pas ce soir, j'ai la migraine Pour la deuxième, ça sent le [latex]\frac{n!(N-n)!}{(N-1)!}[/latex]. Ca colle pour [latex]n=3[/latex], mais aussi pour [latex]n=N-2[/latex] (ça donne [latex]\frac{2}{N-1}[/latex] pour une simple raison de symétrie : choisir [latex]N-2[/latex] points qui sont tous consécutifs revient à choisir les 2 points restants voisins. Et pour [latex]n=N-1[/latex], ça fait 1, bonne nouvelle. Ca ne marche plus pour le choix de N points parmi N, mais disons 1, en gros. Je tente la récurrence demain, si je me sens d'attaque.
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#4 - 17-10-2013 23:06:45
- Fito11235
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 173
Proabbilité de tirer des points consécutifs sur un cercle
Un vrai beau problème de dénombrement et d'utilisation de la formule de probabilité: Nombre de cas favorables/Nombre de cas possibles
1) N choix pour le premier point et qu'1 choix pour le 2eme point puisqu'on tourne dans un seul sens ( je me suis fait avoir au départ en prenant 2 choix pour le 2ème) donc N cas favorables pour avoir 2 points consécutifs. Le nombre de cas possibles est donné par la combinaison de 2 éléments parmi N
D'où P = N/(C N 2) avec C N 2 = N(N-1)/2 C'est à dire P = 2/(N-1) après simplification.
2) a) En avoir au moins 2, c'est en avoir 2 ou 3 : Il y a N possibilité d’en avoir 2 consécutifs et N-4 possibilités pour le 3ème p point et N autres possibilités d’en avoir 3 consécutifs. Le nombre de cas favorable est donc N(N-4) + N = N(N-3) en factorisant Le nombre de cas possibles est donné par la combinaison de 3 éléments parmi N
D'où P = N(N-3)/(C N 3) avec C N 3 = N(N-1)(N-2)/6 C'est à dire P = 6(N-3)/(N-1)(N-2) après simplification.
2) b) N choix pour le premier point, 1 choix pour le 2ème point et 1 choix pour le 3ème
Le nombre de cas possibles est donné par la combinaison de 3 éléments parmi N
D'où P = N/(C N 3) avec C N 3 = N(N-1)(N-2)/6 C'est à dire P = 6/(N-1)(N-2) après simplification.
3) * P(au moins 2) = 1- P(aucun) avec P(aucun) = N(N-2)(N-4)...(N-2n) / C n N
Ca doit pouvoir s'arranger mais le temps va me manquer . * P(n) = n!(N-n)! / N!
#5 - 19-10-2013 14:05:28
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Probabbilité de tirer des points consécutifs sur un cercle
Bonjour
Si N <= 2 alors le problème est trivial. Supposons N > 2.
1/ Le nombre de façon possible de choisir 2 points parmi N est [latex]{N\choose 2} = {N(N-1)\over 2}[/latex]
Le nombre de paires de points consécutifs est exactement N.
Donc la probabilité d'avoir deux points consécutifs est [latex]{N\over N(N-1)/2} = {2\over N-1}[/latex]
3/ (et 2b pour n=3). De manière générale si on remplace 2 par un n quelconque, n < N alors la probabilité d'avoir n points consécutifs est [latex]N\over{N\choose n}[/latex].
2/a Pour chaque paire de point consécutifs, j'ai N-2 choix pour le troisième points. Donc le nombre de triplets qui contient deux point consécutifs est N(N-2). Edit: arghhh, non comme ça j'en compte trop, en fait il y en a N(N-3)
Donc la probabilité qu'en choisissant 3 points j'en ai au moins deux consécutifs est :
[latex]{N(N-3)\over {N\choose 3}} = {N(N-3)\over {N(N-1)(N-2)/3!}} = {6(N-3)\over (N-1)(N-2)}[/latex] avec N > 3.
3/ De manière générale si on remplace 3 par n, n < N et 2 par k, 2<= k < n alors la probabilité d'avoir au moins k points consécutifs en en tirant n est :
[latex]N(N-k-1)\over {N\choose n}[/latex] avec N > k.
Il y a sûrement plus simple.
#6 - 28-10-2013 11:14:23
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
probabilité de tirer des points consécutifs sur ub cercle
Bravo pour votre participation à ce problème.
Tout le monde est d'accord sur les questions 1 et 2.
La réponse la plus intéressante est dans la généralisation :
Soit un cercle avec N points, je tire au sort n points, quelle est la probabilité que ces n points soient consécutifs (côte à côte) ?
Franky1103, MthS-MlndN et Fito11235 ont proposé [TeX]\frac{(N-n)!n!}{(N-1)!}[/TeX] Formule que cogito a joliment simplifiée : [TeX]N\over{N\choose n}[/TeX] Bravo !
Enfin, le point qui a posé le plus de problèmes :
Soit un cercle avec N points, je tire au sort n points, quelle est la probabilité qu'au moins 2 de ces n points soient consécutifs (côte à côte) ?
Selon Franky1103, [TeX]\frac{2}{N-1}[/TeX] Selon Fito11235 [TeX]N(N-2)(N-4)...(N-2n) / {N\choose n}[/TeX] Selon cogito [TeX]N(N-3)\over {N\choose n}[/TeX] Visiblement tout le monde n'est pas d'accord.
Je vais à vous proposer une autre formule : [TeX]\frac{\binom{N+n-1}{n-1}+\binom{N+n-2}{n-1}}{\binom{N}{n}}[/TeX] Je l'ai trouvée en faisant des essais successifs, à partir des nombres issus de mes résultats dénombrant manuellement les cas.
Malheureusement je n'ai pas réussi à la retrouver mathématiquement, alors je vous conseille de la prendre avec précaution.
Si vous avez une idée de comment le démontrer, je peux vous donner mes chiffres (nombre de cas sans points consécutifs) : n=5 N=11 => 11 n=5 N=12 => 36 n=5 N=13 => 91 n=4 N=10 => 25 n=4 N=11 => 55 n=4 N=12 => 105 n=4 N=13 => 182
Le nombre de cas total étant [latex]{N\choose n}[/latex].
#7 - 29-10-2013 01:23:29
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Probabilité de tirer des poinnts consécutifs sur un cercle
Pour la 3a je trouve pour [latex]n \geq 2[/latex] :
Il faut avoir [latex]2n \leq N[/latex]
et alors la probabilité d'avoir au moins 2 points consécutifs est : [TeX]1-\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX] Voici mon raisonnement :
On choisit une orientation sur le cercle. On tire un premier point sur le cercle, le point n°0. Ce point n°0 et l'orientation du cercle fournissent un repère pour l'emplacement des [latex]n-1[/latex] points suivants. On procède ensuite successivement au tirage des points n°1 à [latex]n-1[/latex].
Voici un exemple de tirage avec N=10 et n=4 : 0XX3X21XXX
On dénombre tout d'abord le nombre de façons de tirer ces [latex]n-1[/latex] points :
Il y a [latex]N-1[/latex] possibilités pour le point n°1, puis [latex]N-2[/latex] possibilités pour le point n°2, ... et enfin [latex]N-n+1[/latex] possibilités pour le point n°[latex]n-1[/latex]. Ce qui donne au total [latex](N-1)\times ... \times (N-n+1)[/latex] tirages possibles.
Parmi tous ces tirages possibles, on va à présent dénombrer ceux où il n'y a pas 2 points consécutifs. Pour cela, on compte le nombre de façons d'assembler des "dominos" doubles du type iX pour i variant de 1 à [latex]n-1[/latex] ainsi que des "dominos" simples X.
Par exemple le tirage sans 2 points consécutifs 0XX3X2X1XX correspond à la suite de dominos 0X-X-3X-2X-1X-X.
Il y a [latex]n-1[/latex] dominos à placer du type iX et [latex]N-2n[/latex] dominos X, ce qui fait au total [latex]N-n-1[/latex] dominos à placer. Une suite de dominos est déterminée par les rangs des dominos du type iX dans cette suite, rangs compris entre 1 et [latex]N-n-1[/latex]. Pour le domino 1X il y a [latex]N-n-1[/latex] possibilités, Pour le domino 2X il y a [latex]N-n-2[/latex] possibilités, ... et enfin pour le domino (n-1)X il y a [latex]N-2n+1[/latex] possibilités. Ce qui donne au total [latex](N-n-1) \times ... \times (N-2n+1)[/latex] tirages sans 2 points consécutifs.
La probabilité d'avoir un tirage sans 2 points consécutifs est donc [TeX]\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX] et la probabilité d'avoir un tirage avec au moins 2 points consécutifs est donc [TeX]1-\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX] CQFD.
#8 - 29-10-2013 11:13:43
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
probabilité de tirer des pounts consécutifs sur un cercle
titoufred, je n'ai pas vérifié ton résultat, mais après quelques investigations supplémentaires :
Combien de façons différentse y a-t-il de tirer n points parmi N sur un cercle, de telle façon qu'au moins 2 de ces n points ne soient pas consécutifs (côte à côte) ?
J'obtiens les valeurs suivantes : 2; (nombre de facon de tirer 1 point parmi 2) 3; (1 point parmi 3) 4, 2; (1 point parmi 4, 2 points parmi 4) 5, 5; 6, 9, 2; 7, 14, 7; 8, 20, 16, 2; 9, 27, 30, 9; 10, 35, 50, 25, 2; 11, 44, 77, 55, 11; 12, 54, 112, 105, 36, 2; ... Qui a pour généralisation : [TeX]\frac{N}{n}\binom{N-n-1}{n-1}[/TeX] Donc, Soit un cercle avec N points, je tire au sort n points, quelle est la probabilité qu'au moins 2 de ces n points soient consécutifs (côte à côte) ?
Ma nouvelle réponse serait : [latex]1-\frac{\frac{N}{n}\binom{N-n-1}{n-1}}{\binom{n}{N}}[/latex]
#9 - 29-10-2013 11:32:33
- EfCeBa
- Administrateur
- Enigmes résolues : ∞+1
- Messages : 11×569
probabulité de tirer des points consécutifs sur un cercle
titoufred, apparemment tes formules, qui s'écrivent aussi [TeX]\frac{(N-n-1)!(N-n)!}{(N-1)!(N-2n)}[/TeX] et dont ta réponse [TeX]1-\frac{(N-n-1)!(N-n)!}{(N-1)!(N-2n)}[/TeX] sont équivalentes aux miennes, on retrouve bien les mêmes valeurs, bravo !
Mots clés des moteurs de recherche
|
|