Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques DétentePour discuter des JFF, des problèmes intéressants. ÉnigmesÉnigmes entre membres [tout]Lister tous les topics de mathématiques

1 2 +

Niveau énigmes
Partager :

JFF : Toto collectionne les régions

Posté par
Fractal 10-06-06 à 17:47

Bonjour, une petite énigme...

Toto mange des céréales tous les matins et dans chaque paquet de céréales se trouve un autocollant représentant une région française.
Combien de paquets Toto devra-t-il acheter en moyenne pour avoir la série complète de toutes les régions?

On considèrera évidemment que tous les évenements sont indépendants et on ne considérera que les 22 régions de métropole.

Merci de répondre en blanqué...

Fractal

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 17:51

Salut Fractal,

Niveau de quelle classe ?

Estelle

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 10-06-06 à 17:54

Je dois me coucher. Mais je m'y mets demain. Je rejoins Fractal pour vous prie de répondre en blanqué.
Bonne fin de journée à tous.

Posté par
Fractalre : JFF : Toto collectionne les régions 10-06-06 à 17:54

Salut Estelle

Euhh, je sais pas vraiment, première ou terminale peut-être, il faut connaître les probabilités.

Fractal

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 17:57

Merci Fractal.

J'avais quand même compris qu'il fallait utiliser les probas, mais je voulais savoir 1ère ou Tle

Estelle

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 17:57

Bonsoir Nicolas.

Estelle

Posté par
Fractalre : JFF : Toto collectionne les régions 10-06-06 à 18:01

Je ne sais pas vraiment pour la bonne raison qu'on a pas eu le temps de faire les probas cette année donc je n'ai aucune idée de ce qui s'apprend en première et de ce qui s'apprend en terminale.

Mais je ne pense pas que l'énigme soit spécialement dure, avec un peu d'astuce tu devrais pouvoir arriver à la résoudre.

Bonne fin de journée Nicolas

Fractal

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 18:03

Citation :
Combien de paquets Toto devra-t-il acheter en moyenne pour avoir la série complète de toutes les régions?


Em moyenne ?

Estelle

Posté par
Fractalre : JFF : Toto collectionne les régions 10-06-06 à 18:08

Oui, si il a de la chance il lui suffira d'en acheter 22 mais il peut très bien en acheter 1000 sans pour autant avoir toutes les régions.
C'est pourquoi je demande la valeur moyenne, ou si tu préfères l'espérance de la variable aléatoire qui décrit le nombre de paquets achetés.

N'hésites pas à me demander si tu ne comprends pas.

Fractal

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 18:14

Je comprends mieux quand tu dis "espérance de la variable aléatiore"

Merci.

Estelle

Posté par
Fractalre : JFF : Toto collectionne les régions 10-06-06 à 18:20

Je sais, c'est pour ca que je l'ai dit comme ca

Fractal

Posté par
_Estelle_re : JFF : Toto collectionne les régions 10-06-06 à 18:38

Merci, alors.

Estelle

Posté par
Fractalre : JFF : Toto collectionne les régions 10-06-06 à 18:40

De rien

Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 11-06-06 à 06:43

Fractal, connais-tu la réponse à la JFF que tu proposes ?

Pour ma part, je crois avoir trouvé deux méthodes différentes, mais conduisant à des sommes apparemment non simplifiables... et obligeant au calcul numérique !

Nicolas

Posté par
Fractalre : JFF : Toto collectionne les régions 11-06-06 à 12:27

Bonjour Nicolas, oui je connais la réponse et elle peut s'exprimer sous forme rationnelle.

Fractal

Posté par
plumemeteorere : JFF : Toto collectionne les régions 11-06-06 à 14:39

Réponse approximative :

 Cliquez pour afficher

Posté par
Fractalre : JFF : Toto collectionne les régions 11-06-06 à 14:45

plumemétéore ->

 Cliquez pour afficher


Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 11-06-06 à 15:38

 Cliquez pour afficher

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 11-06-06 à 15:39

 Cliquez pour afficher

Posté par
Fractalre : JFF : Toto collectionne les régions 11-06-06 à 15:45

C'est bien ca, bravo Nicolas .

D'autres réponses?

Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 11-06-06 à 15:54

Je n'ai vraiment aucun mérite. J'ai juste lu la solution proposée par plumemeteore...

 Cliquez pour afficher


Nicolas

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 11-06-06 à 16:16

Fractal, je viens de conclure par l'une des deux autres méthodes dont je parlais ci-dessus, en arrivant au même résultat, après des calculs homériques. Je la posterai en LaTeX (donc non blanqué) après avoir reçu ton feu vert de fin de JFF.

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 12-06-06 à 17:52

Fractal, je viens à l'instant de "conclure" par la seconde de mes deux autres méthodes. Je ne parviens pas à l'expression simple de plumemeteore ou de ma 1ère autre méthode, mais à une somme très lourde de 21 termes, qui, après application numérique, conduit au même résultat.

Je pourrai également la poster après ton feu vert.

Nicolas

Posté par
Fractalre : JFF : Toto collectionne les régions 12-06-06 à 17:55

Bonjour, je pense que tu peux poster tes solutions maintenant, cela fait deux jours que l'énigme est en ligne et de toutes façons le forum est mort en ce moment (ça doit être les exams).

Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 12-06-06 à 18:01

Je les posterai demain : il va me falloir dpas mal LaTeX-ifié !
Mais tu voulais peut-être d'abord poster ta solution à toi ?

Posté par
Fractalre : JFF : Toto collectionne les régions 12-06-06 à 18:07

Ma solution est basée sur la même idée que plumemeteore mais elle est beaucoup moins bien formalisée que ce qu'elle pourrait être, donc à mon avis ta solution sera beaucoup mieux et plus complète que la mienne.

Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 12-06-06 à 18:20

OK. A demain, alors.
Je vais me coucher. Bonne fin de journée à tous !

Posté par
Skopsre : JFF : Toto collectionne les régions 12-06-06 à 18:57

Quel couche tôt

Skops

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 13-06-06 à 01:46

Ma maman m'a toujours dit que le sommeil était la moitié de la réussite.

Posté par
borneore : JFF : Toto collectionne les régions 13-06-06 à 16:51

Salut Nicolas. Ce sont les horaires "boulanger"

Posté par
_Estelle_re : JFF : Toto collectionne les régions 13-06-06 à 16:52

Tout à fait d'accord avec ta maman, Nicolas

Estelle

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 13-06-06 à 16:58

Précision : l'heure à laquelle j'ai écrit mon message n'est pas celle à laquelle je me suis couché, mais celle a laquelle je me suis levé.

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 13-06-06 à 17:15

Bonjour,

Avec l'accord de Fractal...
(que je remercie au passage pour l'énigme)

(1/3) Solution de Fractal et Plumemeteore

Rappel de la solution proposée par plumemeteore :
"Soit n le nombre de régions manquantes à un moment donné.
Il y a n/22 chances d'obtenir une région manquante, donc on l'obtient en moyenne après 22/n essais.
Pour l'ensemble de la collection, il y aura en tout en moyenne : 22/22 + 22/21 + 22/20... + 22/1 essais, ou 22 fois la somme des inverses de 1 à 22"

Si on souhaite formaliser un peu...

Lemme 1.
a) \forall q\neq 1,\; 1+q+q^2+...+q^{n}=\frac{1-q^n}{1-q}
b) \forall q\neq 1,\;\Bigsum_{k=1}^nkq^{k-1}=1+2q+3q^2+...+nq^{n-1}=\frac{nq^{n+1}-(n+1)q^n+1}{(1-q)^2}
c) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=1}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\Bigsum_{k=1}^{\infty}kq^{k-1}=\frac{1}{(1-q)^2}
d) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=n}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\fbox{\Bigsum_{k=n}^{\infty}kq^{k-1}=\frac{nq^{n-1}-(n-1)q^n}{(1-q)^2}}

Démonstration du lemme 1.
a) est la somme classique des termes d'une suite géométrique
b) s'obtient en dérivant a) par rapport à q
c) s'obtient en faisant tendre n vers l'infini dans c)
d) s'obtient par différence entre les expressions de c) et b)

Lemme 2 correspondant au "Il y a n/22 chances d'obtenir une région manquante, donc on l'obtient en moyenne après 22/n essais."
On considère l'épreuve de Bernoulli classique, avec X_i variable de Bernoulli (valant 1 avec une probabilité p et 0 avec une probabilité q), et S_n=X_1+...+X_n
Soit U_1 le plus petit n tel que S_n=1
Alors \fbox{\mathbb{E}(U_1)=\frac{1}{p}}

Démonstration du lemme 2.
\left\{\begin{array}{lcl} \\ \mathbb{P}(U_1=1) & = & p\\ \\ \mathbb{P}(U_1=2) & = & qp\\ \\ ...\\ \\ \mathbb{P}(U_1=k) & = & q^{k-1}p\\ \\ ... \\ \end{array}\right.
donc, si la somme dans le membre de droite a un sens :
\begin{array}{rcl} \\ \mathbb{E}(U_1) & = & \Bigsum_{k=1}^{\infty}k\mathbb{P}(U_1=k)\\ \\ & = & \Bigsum_{k=1}^{\infty}kq^{k-1}p\\ \\ & = & p\Bigsum_{k=1}^{\infty}kq^{k-1} \\ \end{array}
On applique le lemme 1.
\begin{array}{rcl} \\ \mathbb{E}(U_1) & = & p\frac{1}{(1-q)^2}\\ \\ & = & p\frac{1}{p^2}\\ \\ & = &\frac{1}{p} \\ \end{array}

Retour à l'exercice

Soit T_k le rang du premier paquet acheté où on trouve le k-ième autocollant (différent des k-1 trouvés auparavant).
On a évidemment : T_1=1

On cherche \mathbb{E}(T_{22}).

Ecrivons une simple somme téléscopique :
T_{22}=T_{1}+(T_{2}-T_{1})+...+(T_{22}-T_{21})

Par linéarité de l'espérance, on en déduit :
\mathbb{E}(T_{22})=\mathbb{E}(T_{1})+\mathbb{E}(T_{2}-T_{1})+...+\mathbb{E}(T_{22}-T_{21})

Or, pour tout k compris entre 1 et 21, T_{k+1}-T_k suit la même loi que le U_1 du lemme 2, avec p=\frac{22-k}{22} (probabilité de trouver un nouvel autocollant, alors qu'on en a déjà k différents).

Donc, pour tout k compris entre 1 et 21, \mathbb{E}(T_{k+1}-T_k)=\frac{22}{22-k}

Donc :
\mathbb{E}(T_{22})=1+\frac{22}{21}+\frac{22}{20}+...+\frac{22}{1}

Donc :
\fbox{\mathbb{E}(T_{22})=22\left(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{22}\right) = \frac{19093197}{235144} \simeq 81}

Toto devra donc acheter en moyenne 81 paquets pour récupérer les 22 autocollants différents.

Sauf erreur.

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 13-06-06 à 17:17


(2/3) 2ème solution, en conditionnant par rapport au moment où on trouve le 21ème autocollant

Cette solution est moins bonne que celle de plumemeteore et Fractal, qui m'avait échappé. Je suis donc parti sur cette autre piste, bien plus laborieuse !


Lemme 1.
a) \forall q\neq 1,\; 1+q+q^2+...+q^{n}=\frac{1-q^n}{1-q}
b) \forall q\neq 1,\;\Bigsum_{k=1}^nkq^{k-1}=1+2q+3q^2+...+nq^{n-1}=\frac{nq^{n+1}-(n+1)q^n+1}{(1-q)^2}
c) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=1}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\Bigsum_{k=1}^{\infty}kq^{k-1}=\frac{1}{(1-q)^2}
d) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=n}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\fbox{\Bigsum_{k=n}^{\infty}kq^{k-1}=\frac{nq^{n-1}-(n-1)q^n}{(1-q)^2}}

Démonstration du lemme 1.
a) est la somme classique des termes d'une suite géométrique
b) s'obtient en dérivant a) par rapport à q
c) s'obtient en faisant tendre n vers l'infini dans c)
d) s'obtient par différence entre les expressions de c) et b)

Retour à l'exercice

Soit T_k le rang du premier paquet acheté où on trouve le k-ième autocollant (différent des k-1 trouvés auparavant).
On a évidemment : T_1=1

On cherche \mathbb{E}(T_{22}).

On va essayer de trouver une formule de récurrence pour \mathbb{E}(T_{N}).

Exprimons \mathbb{P}(T_N=k) en conditionnant par rapport aux valeurs possibles de T_{N-1} :
\begin{array}{rcl} \\ \mathbb{P}(T_N=k) & = & \Bigsum_{j=N-1}^{k-1}\mathbb{P}(T_N=k/T_{N-1}=j)\cdot\mathbb{P}(T_{N-1}=j)\\ \\ & = & \Bigsum_{j=N-1}^{k-1}\left(\frac{N-1}{22}\right)^{k-j-1}\left(\frac{22-(N-1)}{22}\right)\mathbb{P}(T_{N-1}=j) \\ \end{array}

Donc, sous réserve de l'existence du membre de droite :
\begin{array}{rcl} \\ \mathbb{E}(T_N) & = & \Bigsum_{k=N}^{\infty}k\mathbb{P}(T_N=k)\\ \\ & = & \Bigsum_{k=N}^{\infty}k\Bigsum_{j=N-1}^{k-1}\left(\frac{N-1}{22}\right)^{k-j-1}\left(\frac{22-(N-1)}{22}\right)\mathbb{P}(T_{N-1}=j) \\ \end{array}

On intervertit les sommes :
\begin{array}{rcl} \\ \mathbb{E}(T_N) & = & \Bigsum_{j=N-1}^{\infty}\left(\frac{22-(N-1)}{22}\right)\left(\frac{N-1}{22}\right)^{-j}\mathbb{P}(T_{N-1}=j)\Bigsum_{k=j+1}^{\infty}k\left(\frac{N-1}{22}\right)^{k-1} \\ \end{array}

On pose \tau=\frac{N-1}{22} (on devrait écrire \tau_N, mais on préfèrera \tau pour rendre les notations moins lourdes).
\begin{array}{rcl} \\ \mathbb{E}(T_N) & = & \Bigsum_{j=N-1}^{\infty}\left(1-\tau\right)\tau^{-j}\mathbb{P}(T_{N-1}=j)\Bigsum_{k=j+1}^{\infty}k\cdot\tau^{k-1} \\ \end{array}

On applique le lemme 1 :
\begin{array}{rcl} \\ \mathbb{E}(T_N) & = & \Bigsum_{j=N-1}^{\infty}\left(1-\tau\right)\tau^{-j}\mathbb{P}(T_{N-1}=j)\frac{(j+1)\tau^j-j\cdot\tau^{j+1}}{(1-\tau)^2}\\ \\ & = & \Bigsum_{j=N-1}^{\infty}\left(1-\tau\right)\frac{j+1-j\cdot\tau}{(1-\tau)^2}\mathbb{P}(T_{N-1}=j)\\ \\ & = & \Bigsum_{j=N-1}^{\infty}j\mathbb{P}(T_{N-1}=j)+\frac{1}{1-\tau}\Bigsum_{j=N-1}^{\infty}\mathbb{P}(T_{N-1}=j)\\ \\ & = & \mathb{E}(T_{N-1})+\frac{1}{1-\tau} \\ \end{array}

Donc :
\mathbb{E}(T_N)=\mathbb{E}(T_{N-1})+\frac{22}{22-(N-1)}

Donc, par une récurrence immédiate :
\mathbb{E}(T_{22})=1+\frac{22}{21}+\frac{22}{20}+...+\frac{22}{1}

Donc :
\fbox{\mathbb{E}(T_{22})=22\left(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{22}\right) = \frac{19093197}{235144} \simeq 81}

Sauf erreur.

Nicolas

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 13-06-06 à 17:19

Le plus horrible (3/3) demain.
Pour l'instant, je vais me coucher... comme un boulanger.
Bonne fin de journée à tous.
Et encore merci, Fractal, pour cette JFF montrant la diversité des méthodes utilisables.

Nicolas

Posté par
_Estelle_re : JFF : Toto collectionne les régions 14-06-06 à 16:44

Bonjour,

Bien sûr, merci Fractal pour cette JFF.

Et merci Nicolas, pour le gros travail de correction/rédaction que tu as réalisé.

Estelle

Posté par
Skopsre : JFF : Toto collectionne les régions 14-06-06 à 16:46

J'aimerais bien voir la tête du plus horrible

Skops

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 16:49

Je suis en train de le taper. Tu ne vas pas être déçu. Une vraie horreur.

Posté par
Fractalre : JFF : Toto collectionne les régions 14-06-06 à 16:52

Mais il n'y a vraiment pas de quoi, ce n'est même pas moi qui ai inventé ce problème , je l'ai trouvé dans un article voulant démontrer que dans certains cas, la recherche d'une réponse approchée informatiquement est bien plus pratique que le raisonnement mathématique. Il citait un problème de ce genre en exemple en disant que la recherche de la valeur exacte est bien trop compliquée et qu'il vaut mieux le programmer pour avoir une approximation.
Par esprit de contradiction j'ai donc immédiatement cherché la valeur exacte qui n'était en fait pas si dure à trouver que ca (bon par contre j'ai trouvé la solution sans la prouver du tout de façon rigoureuse, donc merci beaucoup Nicolas pour tout ton travail de correction )

Fractal

Posté par
Skopsre : JFF : Toto collectionne les régions 14-06-06 à 16:55

J'aime bien les tout pleins de formule

Skops

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 16:57

De rien, chers co-Mathîliens.
Je ne mérite pas ces remerciements, encore moins quand vous verrez la 3.
Heureusement, je serai en train de dormir pendant que vous m'invectiverez par mél.

Posté par
Skopsre : JFF : Toto collectionne les régions 14-06-06 à 17:18

Je serais déçu si ya pas tout plein de latex
Skops

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 17:19

T'inquiète pas ! Tu es en train de me distraire. Je LaTeX-ifie à fond.

Posté par
Skopsre : JFF : Toto collectionne les régions 14-06-06 à 17:33

Génial

Skops

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 17:34

Comment voulez-vous que je me concentre dans des conditions pareilles ?

Posté par
Skopsre : JFF : Toto collectionne les régions 14-06-06 à 17:40

Un N
Un I
Un C
Un O
Un L
Un A
Un S

5$\fbox{Nicolas}

Skops la majorette

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 17:42

Encore 15 minutes, chère majorette.

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 17:54

C'est parti...

(3/3) 3ème solution, en essayant d'expliciter la probabilité que le 22ème autocollant soit obtenu au n-ième paquet

C'est la 2ème piste que j'ai essayé de suivre. Elle permet d'aboutir au bon résultat, mais pas sous une forme simple. Elle m'a été partiellement inspirée par ce fil : https://www.ilemaths.net/sujet-probabilite-de-tirage-de-dominos-70135.html

Lemme 1.
a) \forall q\neq 1,\; 1+q+q^2+...+q^{n}=\frac{1-q^n}{1-q}
b) \forall q\neq 1,\;\Bigsum_{k=1}^nkq^{k-1}=1+2q+3q^2+...+nq^{n-1}=\frac{nq^{n+1}-(n+1)q^n+1}{(1-q)^2}
c) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=1}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\Bigsum_{k=1}^{\infty}kq^{k-1}=\frac{1}{(1-q)^2}
d) \forall q\;\mathrm{tel}\;\mathrm{que}\; 0<|q|<1,\; \Bigsum_{k=n}^{\infty}kq^{k-1}\;\mathrm{converge}\;\mathrm{et}\;\fbox{\Bigsum_{k=n}^{\infty}kq^{k-1}=\frac{nq^{n-1}-(n-1)q^n}{(1-q)^2}}

Démonstration du lemme 1.
a) est la somme classique des termes d'une suite géométrique
b) s'obtient en dérivant a) par rapport à q
c) s'obtient en faisant tendre n vers l'infini dans c)
d) s'obtient par différence entre les expressions de c) et b)

Rappel 2.
Soit A_1, A_2, ..., A_n des parties d'un ensemble fini. Alors, en notant \mathrm{card} le cardinal d'un ensemble (= son nombre d'éléments), on a :
\fbox{\begin{array}{rcl} \\ \mathrm{card}(A_1\cup A_2\cup ...\cup A_n) & = & \Bigsum_{i=1}^n\mathrm{card}(A_i) - \Bigsum_{i_1<i_2}\mathrm{card}(A_{i_1}\cap A_{i_2})\\ \\ & & + ... + (-1)^{r+1}\Bigsum_{i_1<i_2<...<i_r}\mathrm{card}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_r})\\ \\ & & + ... + (-1)^{n+1}\mathrm{card}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_n}) \\ \end{array}}
où la somme \Bigsum_{i_1<i_2<...<i_r} comporte {n\choose r} termes.

Démonstration du rappel 2.
Par récurrence à partir de \mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B)-\mathrm{card}(A\cap B)

Remarque. On a bien sûr la même formule dans le cadre des probabilités, les A_i étant alors des événements au sein d'un univers fini :
\begin{array}{rcl} \\ \mathbb{P}(A_1\cup A_2\cup ...\cup A_n) & = & \Bigsum_{i=1}^n\mathbb{P}(A_i) - \Bigsum_{i_1<i_2}\mathbb{P}(A_{i_1}\cap A_{i_2})\\ \\ & & + ... + (-1)^{r+1}\Bigsum_{i_1<i_2<...<i_r}\mathbb{P}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_r})\\ \\ & & + ... + (-1)^{n+1}\mathbb{P}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_n}) \\ \end{array}

Notation. Pour n entier naturel, on note |[1,n]| l'ensemble des entiers compris entre 1 et n, c'est-à-dire \{1, 2, ..., n\}

Rappel 3. Le nombre de p-listes de |[1,n]|, c'est-à-dire le nombre de listes constituées de p éléments de |[1,n]|, ou encore le nombre d'élements de |[1,n]|^p est :
\fbox{L(n,p)=n^p}

Exemple. nombre de 3-listes de |[1,n]| est 2^3=8 :
(1, 1, 1)
(1, 1, 2) (1, 2, 1) (2, 1, 1)
(1, 2, 2) (2, 1, 2) (2, 2, 1)
(2, 2, 2)

Lemme 4. Soit p\ge n. Le nombre de p-listes de |[1,n]| contenant au moins une fois chaque élément de |[1,n]| est :
\fbox{L^*(n,p)=\Bigsum_{r=1}^n(-1)^{n-r}{n\choose r}r^p}

Remarque. Cela correspond à un tirage de p boules avec remise dans une urne qui en contient n différentes, en s'intéressant à l'ordre des boules tirées, et sachant que chaque boule devra avoir été tirée au moins une fois.

Démonstration du lemme 4.
Soit A_i l'ensemble des p-listes de |[1,n]| ne contenant pas i : A_i=\left(|[1,n]|\setminus\{i\}\right)^p
On a :
L^*(n,p)=n^p-\mathrm\left(\Bigcup_{1\le i\le n}A_i\right)

D'après le rappel 2,
\begin{array}{rcl} \\ \mathrm{card}(A_1\cup A_2\cup ...\cup A_n) & = & \Bigsum_{i=1}^n\mathrm{card}(A_i) - \Bigsum_{i_1<i_2}\mathrm{card}(A_{i_1}\cap A_{i_2})\\ \\ & & + ... + (-1)^{r+1}\Bigsum_{i_1<i_2<...<i_r}\mathrm{card}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_r})\\ \\ & & + ... + (-1)^{n+1}\mathrm{card}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_n}) \\ \end{array}

Or \mathrm{card}(A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_r}) est le nombre de p-listes de |[1,n]| ne contenant pas i_1, i_2, ..., i_r : il y en a (n-r)^p.

Comme on sait également que la somme \Bigsum_{i_1<i_2<...<i_r} comporte {n\choose r} termes, on en déduit :
\begin{array}{rcl} \\ \mathrm{card}(A_1\cup A_2\cup ...\cup A_n) & = & {n\choose 1}(n-1)^p - {n\choose 2}(n-2)^p\\ \\ & & + ... + (-1)^{r+1}{n\choose r}(n-r)^p\\ \\ & & + ... + (-1)^{n}{n\choose n-1}1^p + (-1)^{n+1}{n\choose 0}0^p \\ \end{array}
C'est-à-dire :
L^*(n,p)=\Bigsum_{r=0}^{n-1}(-1)^{r}{n\choose r}(n-r)^p
Après le changement d'indice n\to n-r :
L^*(n,p)=\Bigsum_{r=1}^n(-1)^{n-r}{n\choose r}r^p
CQFD.

Retour à la JFF, enfin !

Soit X_n le nombre d'autocollants différents en ma possession après avoir acheté n paquets.
Soit T_N le nombre de paquets qui me permet de posséder, pour la première fois, N autocollants différents.
On a : T_N\ge N (il faut au moins N paquets pour avoir N autocollants différents).

On cherche \mathbb{E}(T_{22}). Pour cela, on va essayer d'expliciter \mathbb{P}(T_{22}=n).

T_{22}=n\Longleftrightarrow X_{n-1}=21\;\mathrm{et}\; X_n=22
Donc :
\begin{array}{rcl} \\ \mathbb{P}(T_{22}=n) & = & \mathbb{P}(X_{n-1}=21\;\mathrm{et}\; X_n=22)\\ \\ & = & \mathbb{P}(X_{n}=22\, /\, X_{n-1}=21)\cdot\mathbb{P}(X_{n-1}=21)\\ \\ & = & \frac{1}{22}\mathbb{P}(X_{n-1}=21) \\ \end{array}

Comme, par définition, \mathbb{E}(T_{22})=\Bigsum_{n=22}^{\infty}n\mathbb{P}(T_{22}=n), on en déduit :
\fbox{\mathbb{E}(T_{22})=\frac{1}{22}\Bigsum_{n=22}^{\infty}n\mathbb{P}(X_{n-1}=21)}

Reste à calculer \mathbb{P}(X_{n-1}=21)

Le nombre de cas favorables est 22^{n-1}
Le nombre de cas possibles est basé sur :
- choix de l'autocollant non obtenu : 22 possibilités ; supposons qu'il s'agit de l'autocollant numéro i
- nombre de (n-1)-listes de |[1;22]|\setminus\{i\} tel que chaque élément de |[1;22]|\setminus\{i\} figure au moins une fois : L^*(21,n-1) possibilités

Donc :
\begin{array}{rcl} \\ \mathbb{P}(X_{n-1}=21) & = & \frac{1}{22^{n-1}}\cdot 22\cdot\left[\Bigsum_{r=1}^{21}(-1)^{21-r}{21\choose r}r^{n-1}\right]\\ \\ & = & \frac{1}{22^{n-1}}\cdot 22\cdot\Bigsum_{r=1}^{21}(-1)^{r+1}{21\choose r}r^{n-1} \\ \end{array}

On peut maintenant revenir à l'espérance de T_{22} :
\mathbb{E}(T_{22})=\Bigsum_{n=22}^{\infty}\frac{1}{22^{n-1}}n\Bigsum_{r=1}^{21}(-1)^{r+1}{21\choose r}r^{n-1}
On intervertit les deux sommes :
\mathbb{E}(T_{22})=\Bigsum_{r=1}^{21}(-1)^{r+1}{21\choose r}\Bigsum_{n=22}^{\infty}n\left(\frac{r}{22}\right)^{n-1}

On applique le lemme 1 :
\mathbb{E}(T_{22})=\Bigsum_{r=1}^{21}(-1)^{r+1}{21\choose r}\frac{22\left(\frac{r}{22}\right)^{21}-21\left(\frac{r}{22}\right)^{22}}{\left(1-\frac{r}{22}\right)^2}

C'est-à-dire :
\fbox{\mathbb{E}(T_{22})=\Bigsum_{r=1}^{21}(-1)^{r+1}{21\choose r}\frac{\left(\frac{r}{22}\right)^{21}}{\left(1-\frac{r}{22}\right)^2}\left(22-21\frac{r}{22}\right)}

Cette somme n'est pas jolie, mais c'est une somme finie, de 21 termes. Je trouve avec mon tableur préféré :
\fbox{\mathbb{E}(T_{22})\simeq 81,1978915}

Ouf, désolé et sauf erreur.

Nicolas

Posté par
Fractalre : JFF : Toto collectionne les régions 14-06-06 à 18:00

On remarquera que la précision est meilleure car on trouve environ 81,1978915 avec cette méthode contre environ 81 avec les autres


Merci beaucoup Nicolas pour ces réponses très détaillées


(sinon, on peut voir qu'il a été super rapide pour poster la solution (2/3) : en se fiant aux heures marquées en haut à gauche, il a mis 2 minutes pour tout écrire )

Fractal

Posté par
Nicolas_75 Correcteurre : JFF : Toto collectionne les régions 14-06-06 à 18:02


Je t'en prie, Fractal.
Merci d'avoir donné du grain à moudre à mes neurones.
Quant aux 2 minutes, non, vous ne saurez pas mon secret !

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

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 !