Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 17-10-2013 09:16:26

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 11×569

Probabilité de tirer des poitns consé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).

  • |
  • Répondre

#0 Pub

 #2 - 17-10-2013 21:06:33

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3207
Lieu: Luxembourg

probabilité de tirer des piints consécutifs sur un cercle

Ceci n'est pas un site d'aide aux devoirs ! lol
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 ddes points 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 big_smile

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 lol 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 : 172
Lieu: Bourgogne

Probabilité de tireer 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 sad.
     
                                     
    * P(n) = n!(N-n)! / N!

 #5 - 19-10-2013 14:05:28

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Probabilité de tirer des points conscutifs sur un cercle

Bonjour smile

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 ponts consécutifs sur un 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 points 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 points consécutifs sur un cerclr

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

Probabilité de tireer 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 !

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete