Dénombrement, probabilité et boules

OShine

Bonsoir
Q1) Je ne vois pas comment trouver la bijection. J'ai essayé avec des exemples mais je ne trouve pas le même cardinal...
Pour $n=3$ et $r=2$ : 

• $E$ est l'ensemble des parties de $\{1,2,3\}$ de cardinal $2$ donc $\{1,2 \}$, $\{1,3\}$ et $\{3,2\}$.
• $F$ est l'ensemble des parties de $\{1,2,3,4\}$ n'ayant aucun terme consécutif. Donc ici $\emptyset$, $\{1 \}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{1,4\}$.

mateo

Bonjour Oshine,
La première ligne de définition de $F$ est incomplète : il manque : "de cardinal $r$".
Cela se voit en lisant la deuxième ligne : "Plus précisément ...".
D'autre part, tu as oublié $\{2 ; 4\}$ dans $F$.
Cordialement,

OShine

Bien vu merci.

OShine

Pour la bijection j'ai une idée mais je ne comprends pas d'où sort le $n+r-1$.
J'associe à chaque $x_k$ l'entier $x_k+k-1$.
Et on veut $x_k+k-1 \leq n$ soit $x_k \leq n-k+1$.

PetitLutinMalicieux

Bonjour

Pourquoi ne pas faire une double récurrence sur n et r ?

JLT

OShine a dit :

Pour la bijection j'ai une idée mais je ne comprends pas d'où sort le $n+r-1$.
J'associe à chaque $x_k$ l'entier $x_k+k-1$.
Et on veut $x_k+k-1 \leq n$ soit $x_k \leq n-k+1$.

Ben voilà tu l'as ta bijection. C'est $\{x_1<\cdots<x_r\}\mapsto \{x_1,x_2+1,\ldots,x_r+r-1\}$.

lourrran

Pour la bijection j'ai une idée mais je ne comprends pas d'où sort le n+r−1

Drôle de question ! (comme d'habitude)
Dans ce cas, construit ta bijection, avec $E$ de cardinal $n$ et $F$ de cardinal $k$, et regarde ensuite quelle relation relie $k$ et $n$ et $r$.
Ici, ils ont été cools, ils t'ont dit que tu vas finalement trouver $k=n+r-1$

OShine

@lourrran je n'ai pas compris on ne connait pas la cardinal de $E$.

@JLT ok merci j'essaie de démontrer qu'elle est bijective.

lourrran

Le cardinal de E, on ne le connait pas. Exact. 
Mais si on connaît un élève de lycée, peut-être que lui, il peut nous aider. Ou si on a un livre de cours sous la main, en lisant les tout premiers paragraphes sur les dénombrements, on peut peut-être trouver la formule magique.  

Ceci dit, il y a effectivement beaucoup d'imprécisions dans l'avant dernière ligne de mon précédent message.

OShine

Voici mon raisonnement. 

JLT

Soit $\Phi : E\to F$ définie par $\Phi(\{x_1<\cdots<x_r\}) =\{x_1,x_2+1,\ldots,x_r+r-1\}$.

1) Montrer que $\Phi$ est bien définie, c'est-à-dire que $\{x_1,x_2+1,\ldots,x_r+r-1\}$ appartient bien à $F$.

2) De même, définir une application $\Psi : F\to E$ et montrer qu'elle est bien définie.

3) Vérifier que $\Psi\circ\Phi=\mathrm{Id}_E$.

4) Vérifier que $\Phi\circ\Psi=\mathrm{Id}_F$.

5) Conclure.

PetitLutinMalicieux

"@lourrran je n'ai pas compris on ne connait pas la cardinal de E."

J'ai bien ri à cette blague. C'était une blague, n'est-ce pas ?

Je vois l'exercice comme étant une réflexion permettant d'utiliser le dénombrement de E, supposé évident, pour obtenir le dénombrement de F, supposé difficile.

Pour le dénombrement de E, on tire r parmi n, indépendamment de l'ordre, et sans répétition, c'est donc une combinaison. Il y a $C_n^r$ possibilités.

lourrran

Oui PLM.
Mais maintenant, imagine quelqu'un qui commence les cours par la fin. Les formules considérées comme classiques, il les apprendra à la fin de son cursus, peut-être, s'il arrive jusque là.
Ca change tout !

OShine

Cet exercice est issu de X-ENS oral 2 022 PSI sur Beos.
Merci @JLT.
1) Soit $\{x_1, \cdots, x_r \} \in E$. Alors pour tout $i  \in \{1, \cdots, r \}, \ x_i  \in  \{1, \cdots, n \}$. 
Soit  $ k \in \{0, \cdots, r-1 \}$. Alors $1 \leq 1+k \leq  x_k + k  \leq n+k \leq n + r-1 \}$. Donc  $\phi $ est bien définie.
2) Je définis $\psi $ par $\boxed{\psi ( \{ a_1 < a_2 < \cdots < a_r  \})=  \{ a_1 ,  a_2 -1 , \cdots , a_r -(r-1)  \} }$ de  $F $ dans  $E $. 
Comme $\forall k \in \{0, \cdots, r \}$. Alors $1 \leq   a_k   \leq  n + r-1 $. On sait que $a_1 \geq 1$ donc  $\forall k \in \{0, \cdots, r \} ,\ a_k \geq 1 $. De plus, $a_r \leq  n + r-1 \implies a_r -(r-1) = a_r - r +1 \leq n$ donc  $\forall k \in \{0, \cdots, r \}, \ a_k \leq n $.
Donc  $\psi $ est bien définie.
3) et 4) Évident.
5) Donc $\boxed{card \ E = card \ F =  \binom{n}{r}}$.
Q2a)  Il y a $ \binom{49}{4}=\boxed{ 211876} $ possibilités.
Notons $A$ cet évènement. On a $P( \bar{A})= \dfrac{ \binom{49}{1}}{ \binom{49}{4}}= \dfrac{1}{4324}$.
Finalement $ \boxed{P(A)= \dfrac{4323}{4324} }$
Est-ce correct ?

JLT

Pour 1) et 2) tu n'as pas utilisé la propriété "n'ayant aucun terme consécutif" dans ta démonstration donc ce n'est pas complet.

Pour Q2a je ne comprends pas ce que tu as fait. Qu'est-ce que tu as pris pour $n$ et $r$, et comment utilises-tu la question précédente ?

lourrran

Question 1 :
On a 49 boules numérotées de 1 à 49, et on en prend 4 simultanément.
Quelle est la probabilité qu'au moins 2 des 4 boules aient des numéros consécutifs.
- Bof, pas beaucoup , peut être 10% max 
- Bof, aucune idée, peut-être une chance sur 3, ou une chance sur 2
- Enorme, plus de 99%

Question 2 : 
On se pose la même question, mais avec 50 boules au lieu de 49.
Est-ce que la probabilité demandée augmente, ou diminue ?

Question 3 : 
On se pose la même question mais avec 6 boules au lieu de 49.
Combien vaut la probabilité qu'au moins 2 des 4 boules aient des numéros consécutifs ? 

Question 4 : 
La réponse 4323/4324 est elle raisonnable ?

Amédé

Rien à voir @OShine : je te pensais sur la plage à profiter de tes vacances.

OShine

@JLT en effet merci ça se vérifie facilement.

J'ai pris $n=49$ mais je ne vois pas comment trouver $r$. J'ai voulu calculer la probabilité de l'événement contraire.

@lourrran en effet la probabilité va être beaucoup plus faible je sentais que c'était faux. 
Ça devrait être moins de 25%.

JLT

Donc tu as répondu en sortant un $\binom{49}{1}$ au hasard.

Cherche à voir le lien avec l'ensemble $F$ de la question précédente.

lourrran

Tu sentais que c'était faux.
Mais comme d'habitude, plutôt que réfléchir, tu as demandé aux autres de réfléchir pour toi.
Tu as une formule, tu l'appliques pour 49 boules, pour 50 boules, tu compares.
Tu vois que selon cette formule, plus on a de boules, plus la proba d'avoir 2 numéros consécutifs augmente, la formule est forcément fausse.
Pas la peine de montrer au monde entier qu'un prof de collège dénommé OShine ne sait pas réfléchir.

OShine

Ici on a $r=4$ et $n+r-1=49$ donc $n=46$
Posons $A$ : "Au moins deux des $4$ boules ont des numéros consécutifs" alors $\bar{A}$ est l'évènement : "Aucune des $4$ boules ont des numéros consécutifs"
Donc $P(\bar{A}) = \dfrac{\displaystyle\binom{46}{4}}{\displaystyle\binom{50}{4}}=\dfrac{163185 }{230 300} $
Ainsi $P(A)=\dfrac{67 115}{230 300}$. Soit $\boxed{P(A)=\dfrac{13 423}{46 060} \approx 0,058 \approx 5,8 \%}$

JLT

Comment tu as calculé $P(\bar{A})$ ?

OShine

Je bloque à la question 2.b.

JLT

Réponds déjà à ma question.

OShine

Nombre de cas favorables / Nombres de cas possibles.

JLT

Comment as-tu calculé le nombre de cas possibles ?

OShine

Ah c'est une erreur d'étourderie, le nombre de cas possibles est $\displaystyle\binom{49}{4}$.
Donc $P(\bar{A})=\dfrac{\binom{46}{4}}{\binom{49}{4}}=\dfrac{163 185}{211 876}= \dfrac{7 095}{9 212}$
Donc $\boxed{P(A)=  \dfrac{2 117}{9 212} \approx 0,23}$

PetitLutinMalicieux

???

Tirer 4 parmi 49 ou 4 parmi 50 c'est pareil. Tu ne peux pas passer de 5% de chance à 23% soit presque 1 chance sur 4. Je n'ai pas fait le calcul mais ton sens critique devrait hurler.

lourrran

La première formule écrite, c'était 13423/46060  
Mais le calcul fait par OShine, c'était 13423/230300 ; dans la simplification par 5, il y a le dénominateur qui est passé à l'as. 

Qui déjà disait que le niveau du prof tend asymptotiquement vers le niveau de ses élèves quand le prof ne cherche pas à progresser ? Apparemment, il faudrait compléter la formule.

Soc

OShine a dit :

Je bloque à la question 2.b.

Tu en choisis 3 non consécutives parmi ... et parmi ces 3 tu choisis celle que tu doubles.

OShine

Bien vu @lourran mais 23 % de chance ça m'a l'air élevé c'est étrange non ? 

Pour la question $2.b$ je ne trouve pas.

lourrran

23%, c'est beaucoup... 
Je prends 4 boules, j'en regarde 3.
Supposons qu'il n'y a pas de numéros consécutifs parmi ces 3 boules... donc je suis dans les 85% ou 90% ou 95% de cas où l'histoire commence bien.
L'histoire va-t-elle bien se terminer ?
La 4ème boule va-t-elle me faire échouer ou pas. Je connais les numéros des 3 premières boules, il reste 46 numéros. Sur ces 46 numéros, il y en a 6 qui vont me faire perdre (peut-être que 5  si j'ai le n°1 ou le n°49 en main, ou si j'ai par exemple les n° 14 et 16).
Il y a  6 numéros ou parfois 5, ou rarement 4 qui peuvent me faire perdre, sur les 46 numéros restant.
Je vais perdre dans environ 11% des cas.
Si la 2ème boule et la 3ème boule ont été 'gentilles', j'ai encore 11% de risques de perdre au moment de dévoiler le n° de la 4ème.

Du coup, 23%, ça paraît plausible. 

OShine

@lourrran sur les $46$ numéros ce n'est pas plutôt entre $4$ et $6$ qui vont te faire gagner ? On cherche à avoir $2$ numéros consécutifs ou plus. 

@Soc
Merci.
On choisit $3$ boules non consécutives et une $4$ ième boule qui doit être consécutive avec l'une des $3$ autres. Je dois déterminer le nombre de cas favorables.

OShine

Le nombre de cas favorables d'avoir aucune consécutives parmi les $3$ choisies est : $\displaystyle\binom{47}{3}$ d'après Q1.
Le nombre de cas favorables d'avoir une boule consécutive à une des $3$ choisies je n'arrive pas à le calculer car ça dépend de la position des boules, si une des boules est en première/dernière position.

JLT

On considère $a_1<a_2<a_3<a_4$ avec exactement deux des nombres consécutifs. Il y a plusieurs cas :

1) $a_1$ et $a_2$ consécutifs

2) $a_2$ et $a_3$ consécutifs

3) $a_3$ et $a_4$ consécutifs.

Plaçons-nous dans le cas 3. On constate que $a_4$ est uniquement déterminé puisque $a_4=a_3+1$. Combien y a-t-il de manières de placer $a_1$, $a_2$ et $a_3$ ?

Soc

Le principe de la bijection de E dans F est d'insérer un espace, un décalage, après les r-1 première boules que tu as tiré (forcément, après la dernière cela ne sert à rien).

Dans la question 2.b il faut adapter la même idée à un cas légèrement plus complexe. On va tirer non pas r boules mais r-1, et la dernière on va choisir consécutivement à laquelle des r-1 on va la placer.

OShine

@JLT je ne suis pas sûr du tout j'ai des difficultés en dénombrement.

3) Il y a $49$ boules. $a_3$ peut être placé partout excepté en position 1,2 et 49 donc $49-3=46$ possibilités. 
$a_1$ peut être placé partout excepté en position 47, 48 et 49 donc $49-3=46$ possibilités. 
$a_3$ peut être placé partout excepté en position 1,2 et 49 donc $49-3=46$ possibilités. 
$a_4$ est uniquement déterminé donc $1$ possibilité.
$a_2$ peut être placé partout excepté en position 1,48 et 49 donc $49-3=46$ possibilités. 

Il y a $46^3$ manières de placer $a_1$, $a_2$ et $a_3$.

JLapin

Puisque tu as des difficultés en dénombrement, tu ne veux pas commencer par le début :
https://www.mathraining.be/chapters/35

lourrran

Une fois que $a_1$ a été choisi, par exemple $a_1=40$, est-ce qu'il y a $46$ possibilités pour $a_2$ ?
Je sais que tu refuses systématiquement d'apprendre les cours dans l'ordre. À ce point là, c'est pathologique. 

OShine

@JLapin merci, la formule de combinaison avec répétition je ne l'ai jamais vu auparavant. 

@lourrran
Non, il reste que $6$ possibilités pour $a_2$.
Mais ici comment savoir si on choisit en premier $a_1$, $a_2$ ou $a_3$ ? 
J'ai relu le cours de dénombrement de L1 mais je ne sais pas l'appliquer à cette question 2.b.
Je ne vois pas le lien entre le cours et la question de JLT.

JLT

$a_1,a_2,a_3$ sont trois nombres distincts deux à deux non consécutifs compris entre 1 et 48 donc d'après la question 1,...

lourrran

Tu as relu le cours de L1 entre hier midi et hier soir.
Relire le cours de L1, ça veut dire faire les exercices qui vont avec. Il faut au moins une semaine. Il faut au moins autant de temps pour faire plusieurs exercices de L1 que pour faire 1 seul exercice un peu avancé.

Comment savoir si on choisit en premier $a_1$, $a_2$, $a_3$ ? Avec les tirages simultanés, il y a différents réflexes qu'on finit par acquérir. Ce sont des réflexes qu'on acquiert en faisant des exercices simples.

OShine

Cas $3$ : 

$a_1$, $a_2$ et $a_3$ sont non consécutifs donc d'après la question $1$ il y a $\binom{47}{3}$ possibilités.
$a_4$ est uniquement déterminé donc au total $\binom{47}{3}$ possibilités.

Cas $2$ : 

$a_1$, $a_2$ et $a_4$ sont non consécutifs donc d'après la question $1$ il y a $\binom{47}{3}$ possibilités.
$a_3$ est uniquement déterminé donc au total $\binom{47}{3}$ possibilités.

Cas $1$ : 

$a_1$, $a_3$ et $a_4$ sont non consécutifs donc d'après la question $1$ il y a $\binom{47}{3}$ possibilités.
$a_2$ est uniquement déterminé donc au total $\binom{47}{3}$ possibilités.

Au final, si je note $B$ l'évènement de Q2b, on a $P(B)=\dfrac{ 3 \binom{47}{3} }{\binom{49}{4}}$

Donc $P(B)=\dfrac{48 645}{211 876} = \dfrac{45}{196} \approx 0,23$ ça ne me semble pas logique...

JLT

Revois soigneusement le cas 3.

Soc

@JLT: Pourquoi le cas 3 spécifiquement? Il me semble que c'est la même faute dans les 3 cas.

@OShine: Il faudrait que tu explicites le bijection dans des cas concrets pour qu'elle te parle davantage. Par exemple si tu dois choisir 3 non consécutifs parmi 10, au lieu de cela tu prends 3 parmi 8. Si les 3 parmi 8 sont {2;5;6} ta bijection transformera cela en ... ?

OShine

J'ai corrigé le cas 3 mais les autres cas je retrouve la même chose.

Cas $3$ :  
$a_1,a_2,a_3 \in [|1,48|]$ donc $n+r-1=48$ avec $r=3$ ainsi $n=46$.
Il y a donc $\binom{46}{3} = 15 180$ possibilités.

Cas $2$ :  
$a_1,a_2,a_4 \in [|1,49|]$ donc $n+r-1=49$ avec $r=3$ ainsi $n=47$.
Il y a donc $\binom{47}{3} $ possibilités.

Cas $1$ :  
$a_1,a_3,a_4 \in [|1,49|]$ donc $n+r-1=49$ avec $r=3$ ainsi $n=47$.
Il y a donc $\binom{47}{3} $ possibilités.

Soc

@OShine: Pourquoi le cas 3 spécifiquement? Il me semble que c'est la même faute dans les 3 cas.

OShine

Je ne comprends pas où est l'erreur.

Soc

@OShine: Il faudrait que tu explicites le bijection dans des cas concrets pour qu'elle te parle davantage. Par exemple si tu dois choisir 3 non consécutifs parmi 10, au lieu de cela tu prends 3 parmi 8. Si les 3 parmi 8 sont {2;5;6} ta bijection transformera cela en ... ?

OShine

En $\{2,4,5\}$ d'après la bijection que j'ai exhibée.

Soc

Tu prends la bijection dans le mauvais sens. Ni {2;5;6} ni {2;4;5} ne peuvent être des éléments de F.

Pour E on cherche à choisir 3 boules dans [1;8] ou bien pour F on cherche à choisir 3 boules non consécutives dans [1;10].
{2;5;6} est un élément de E et on cherche son image dans F, quelle est-elle?