Inscription / Connexion Nouveau Sujet
Forum Enigmes
Partager :

Horreur millions!

Posté par
Goudda
06-09-16 à 13:58

Salut,

Une urne contient 50 boules blanches numerotees de 1 a 50.
On tire au hasard 5 boules et on les peint en noir ensuite on les remet dans l`urne.
Ensuite on proccede de meme : on tire 2 boules au hasard on repeint en noir uniquement les boules blanches tirees et on les remet dans l`urne.
Et ainsi de suite jusqu`au nombre de tirages egal a k.

1. Combien faut-il de tirages en moyenne avec une probabilite de 99% pour que toutes les boules soient peintes en noir?
2. A supposer qu`apres un certain nombre de tirages il reste dans l`urne 10 boules ou moins (10 ou 9 ou 8 ou 7 ou 6) non peintes en noir quelle est la probabilite de tirer au moins une boule blanche?
  

Posté par
kenavo27
re : Horreur millions! 06-09-16 à 14:07

bonjour,
As-tu commencé quelque chose?

Posté par
Goudda
re : Horreur millions! 06-09-16 à 14:11

Ce n`est pas un exercice.
Je devais le mettre sur enigmes, il m`a sorti un menu limite alors j`ai appuye sur lycee.

Posté par
kenavo27
re : Horreur millions! 06-09-16 à 14:20

OK

Posté par
dpi
re : Horreur millions! 06-09-16 à 16:30

>Goudda

J'ai eu un moment de joie en me disant:
"ça y est enfin un volontaire pour poster des énigmes!"

Si tu parcours l'historique, tu verras l 'engouement des îliens
pour cette rubrique.
Donc  il y a de l'espoir

Posté par
LittleFox
re : Horreur millions! 06-09-16 à 17:51


On peut modéliser le problème par une chaîne de markov. Un état est repérenté par le nombre n de boules noires dans l'urne (de 0 à 50).

L'état de départ est n = 0. La probabilité de passer de n=0 à n=5 est 1 (premier tirage). Pour les autres états on a :
* P(n->n) (on tire 2 boules noires) = n/50*(n-1)/49
* P(n->n+1) (on tire une blanche et une noire) = n/50*(50-n)/49 + (50-n)/50*n/49
* P(n->n+2) (on tire deux blanches) = (50-n)/50*(49-n)/49
Toutes les autres autres transitions on une probabilité = 0. On peut vérifier que la somme des probabilités pour chaque état vaut bien 1.

1) Combien de tirage faut-il au minimum pour que la probabilité à priori (sinon il suffit de compter combien on a peint de boules ^^) d'avoir peint toutes les boules soit supérieure à 99% ?

Soit M la matrice de transition, on cherche le p minimum tel que M^p[0][50] soit > 0.99. On a M^206[0][50] = 0.989602 et M^207[0][50 ] = 0.990016 (aux erreurs d'arrondi près). Il faut donc 207 tirages.

2) Quelle est la probabilité de tirer au moins une boule blanche lorsqu'il y a 10 boules blanches ou moins dans l'urne.

La probabilité de tirer au moins une boule blanche est 1 moins la probabilité de tirer deux boules noires. P'(n) = 1-(n/50*(n-1)/49). On peut vérifier que P'(n) = P(n->n+1) + P(n->n+2).
Comme on a pas d'infos sur le nombre de tirage, on ne peut calculer la distribution des états (après 100 tirages on a 44% de chances d'avoir toutes les boules noires, 38% d'avoir 1 boule blanche, 14% d'en avoir 2, 3% d'en avoir 3, ...) On ne peut donc pas calculer la probabilité globale.
Supposons que cette distribution est uniforme (irréaliste voir plus haut), la probabilité est (P'(40) + P'(41) + ... + P'(50)) / 11 = 5060/(50*49*11) 18.76%

Posté par
LittleFox
re : Horreur millions! 06-09-16 à 18:41


Voici un petit graphique de ce qui se passe

Posté par
LittleFox
re : Horreur millions! 06-09-16 à 18:42

Oups

Horreur millions!

Posté par
Goudda
re : Horreur millions! 06-09-16 à 21:24

Merci pour ta reponse.
Pas de fonction generatrice a utiliser?

Posté par
LittleFox
re : Horreur millions! 07-09-16 à 10:45


Je connais pas trop les fonctions génératrices, mais après lecture de wikipédia , je ne pense pas que ce soit utile ici.

On pourrait définir une fonction génératrice pour chaque transition possible (n->n, n->n+1, n->n+2 et n->n+5) mais je vois pas à quoi ça peut nous servir .

Posté par
Goudda
re : Horreur millions! 07-09-16 à 14:00

LittleFox @ 07-09-2016 à 10:45


Je connais pas trop les fonctions génératrices, mais après lecture de wikipédia , je ne pense pas que ce soit utile ici.

On pourrait définir une fonction génératrice pour chaque transition possible (n->n, n->n+1, n->n+2 et n->n+5) mais je vois pas à quoi ça peut nous servir .


Te rends-tu compte de ce que tu viens de dire?
"Je (tu)  connais pas trop les fonctions génératrices, mais après lecture de wikipédia , je (tu) ne pense pas que ce soit utile ici."

So what? Apres lecture de Wikipedia tu sors un jugement definitif : pas utile ici.

Comment sais-tu que cela n`est pas utile ici?
Moi je pense profondement que l`immense majorite de ceux qui font des maths sont plus asservis a leur ego qu`au progres des maths. Les Perelman et les Grothendieck sont tres rares.
Je commence a detester les bipedes pour de bon.
Je me barre.
Ce sera mon dernier post.
Je renonce a publier ma solution au probleme du logarithme discret.
Je coupe internet et je me barre a la campagne.
Bonne chance a vous et au forum.

Posté par
dpi
re : Horreur millions! 07-09-16 à 17:58

Alors là je suis bouche bée
Rien de méchant chez littlefox.
Tu commençais à nous intéresser .

Posté par
LittleFox
re : Horreur millions! 08-09-16 à 09:46


Wuuut?
Bonnes vacances.

Si tu nous reviens avec une solution utilisant les fonctions génératrices, je serai heureux de la découvrir .

Posté par
Goudda
re : Horreur millions! 18-09-16 à 15:24

Si tu lis l`anglais lis ce precieux document :

https://www.math.upenn.edu/~wilf/gfology2.pdf

Il parle des fonctions generatrices.

Posté par
LittleFox
re : Horreur millions! 23-09-16 à 17:13

Bon, j'ai un peu (beaucoup) bossé pour intégrer une (petite) partie de la théorie sur les fonction génératrices et j'ai essayé de les utiliser dans notre cas.

Soit F_n(x) = \sum_{k \ge 0} a_{n,k}x^ka_{n,k} est la probabilité d'avoir n boules noires après k tirages, p_n=\frac{n(n-1)}{50*49} et q_n=\frac{2n(50-n)}{50*49}, on a :

 F_n(x) = \begin{cases}1, & \text{si}\ n = 0 \\0, & \text{si}\ 0 < n < 5 \\ \sum_{k>0}p_5^{k-1}x^k = \frac{x}{1-xp_5}, & \text{si}\ n = 5 \\\frac{x}{1-xp_n} \left [ q_{n-1}F_{n-1}(x)+(1-p_{n-2}-q_{n-2})F_{n-2}(x)\right ], & \text{si}\ n > 5  \end{cases}

En effet,
a_{0,k} = \begin{cases}1, & \text{si}\ k = 0 \\0, & \text{si}\ k > 0 \end{cases}
a_{n,k} = 0\ \text{si}\ 0<n<5
a_{5,k} = \begin{cases}0, & \text{si}\ k = 0 \\p_5^{k-1}, & \text{si}\ k > 0 \end{cases}
Pour n > 5,
a_{n,k+1} = a_{n,k}p_n + a_{n-1,k}q_{n-1} + a_{n-2,k}(1-p_{n-2}-q_{n-2}).
Donc \frac{F_n(x)-a_{n,0}}{x} = p_nF_n(x) + q_{n-1}F_{n-1}(x) + (1-p_{n-2}-q_{n-2})F_{n-2}(x). Or a_{n,0} = 0\ \text{si}\ 5<n .
Donc F_n(x)\frac{1-xp_n}{x} = q_{n-1}F_{n-1}(x) + (1-p_{n-2}-q_{n-2})F_{n-2}(x).

On en déduit F_6(x) = \frac{x}{1-xp_6} \left [ q_{5}\frac{x}{1-p_5} + 0\right ] = \frac{q_5x^2}{(1-xp_5)(1-xp_6)}. Et on peut vérifier que F_6(x) = \sum _{k>0} (\sum_{0\ge i\ge k-2} p_5^iq_5p_6^{k-2-i}) x^k.

F_7(x) = \frac{x}{1-xp_7} \left [ q_{6}F_6(x) + (1-p_5-q_5)F_5(x)\right ] \\= \frac{x}{1-xp_7} \left [ q_{6}\frac{q_5x^2}{(1-xp_5)(1-xp_6)}+ (1-p_5-q_5)\frac{x}{1-xp_5}\right ] \\=\frac{[q_5 q_6 x + (1-p_5-q_5)(1-xp_6)]x^2}{(1-xp_5)(1-xp_6)(1-xp_7)}

Ça se complique , je laisse de côté le calcul de F_{50}(x) pour l'instant.

Je pensais pouvoir tirer des info de proba avec des relations du genre F'_n(1)/F_n(1) = E(k|n=n) mais pour l'instant les calculs ne sont pas cohérents. Je ne sais pas où est l'erreur, un peu d'aide serait la bienvenue .

Posté par
LittleFox
re : Horreur millions! 26-09-16 à 13:59


Bon ben apparemment la formule F'_n(1^-)/F_n(1^-) = E(k|n=n) est correcte, j'étais juste fatigué . Ce que je veux dire par là c'est que l'espérance du nombre de tirage fait lorsqu'on sait qu'on a n boules est donnée par F'_n(1^-)/F_n(1^-) (avec f(1^-) =\lim_{x \rightarrow 1, x < 1} f(x)(c'est sûrement mal écrit donc je précise ).

Le truc c'est qu'on a besoin que de valeurs particulières de F_n(x) et F'_n(x) et pas de leur expression. Et ces valeurs on peut les calculer itérativement.

On a :
 F'_n(x) = \begin{cases}0, & \text{si}\ n < 5 \\\frac{1}{x(1-xp_n)}F_n(x) + \frac{x}{1-xp_n} \left [ q_{n-1}F'_{n-1}(x)+(1-p_{n-2}-q_{n-2})F'_{n-2}(x)\right ], & \text{si}\ n \ge 5  \end{cases}

Après calcul :

n F_(x) F'_n(x) E_n(k | n=n)
0 1.000 0.000 0.000
1 0.000 0.000 n ne peut jamais être 1
2 0.000 0.000 n ne peut jamais être 2
3 0.000 0.000 n ne peut jamais être 3
4 0.000 0.000 n ne peut jamais être 4
5 1.008 1.017 1.008
6 0.187 0.379 2.021
7 0.870 1.804 2.074
8 0.367 1.129 3.076
9 0.765 2.477 3.240
10 0.507 2.124 4.191
11 0.709 3.205 4.519
12 0.604 3.254 5.391
13 0.698 4.109 5.887
14 0.670 4.484 6.690
15 0.717 5.245 7.319
16 0.723 5.850 8.095
17 0.753 6.635 8.816
18 0.772 7.416 9.605
19 0.799 8.305 10.395
20 0.825 9.256 11.224
21 0.853 10.306 12.076
22 0.884 11.454 12.960
23 0.917 12.719 13.877
24 0.952 14.114 14.829
25 0.990 15.659 15.818
26 1.031 17.374 16.850
27 1.076 19.287 17.926
28 1.125 21.430 19.050
29 1.178 23.839 20.229
30 1.237 26.562 21.466
31 1.302 29.656 22.769
32 1.375 33.194 24.144
33 1.456 37.266 25.599
34 1.547 41.987 27.146
35 1.650 47.508 28.796
36 1.768 54.026 30.564
37 1.904 61.806 32.467
38 2.062 71.210 34.529
39 2.250 82.745 36.779
40 2.475 97.144 39.254
41 2.750 115.498 42.004
42 3.093 139.505 45.097
43 3.535 171.933 48.633
44 4.125 217.601 52.757
45 4.949 285.618 57.707
46 6.187 395.300 63.893
47 8.249 595.116 72.143
48 12.374 1045.783 84.516
49 24.747 2704.004 109.264
50++ +


Donc voilà finalement un résultat . Y a-t-il d'autre résultats intéressants à retirer de cette famille de fonction génératrices ? Ou un moyen d'expliciter les F_n(x) plus facilement? à voir .

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 00:00:00.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !