Invite
Message de Glozi (sans compte)
Bonjour,
Bernard-maths, ce n'est pas possible lorsque $n\geq 3$, en effet déjà il y a une probabilité de $1/n$ pour que le premier arrivant choisisse sa place. S'il a bien choisi sa place alors tous les autres feront de même, et donc on a une probabilité supérieure ou égale à $1/n$ que le dernier soit à sa place. Mais dès que $n\geq 3$ alors ce n'est pas la seule possibilité pour que le dernier ait son siège attribué (par exemple le premier choisi le siège 2 au hasard, et le deuxième choisi le siège 1 au hasard (car sa place était occupée) alors les suivants seront tous à leur place).
Ainsi cette probabilité est plus grande que $1/n$ (strictement) dès que $n\geq 3$.
Bonne journée
Bernard-maths
Bonjour !
Glozi, sur ta réponse je viens de relire l'énoncé avec attention (!), et je me rends compte qu'il y a des places numérotées !!!
Je vais reprendre mes calculs !
@ +
Michel-Coste
Bonjour,
Quand le passager n°n arrive, une et exactement une des deux places 1 et n est occupée par un passager qui l'a choisie au hasard (soit le passager n°1 qui choisit au hasard, soit un des suivants entre 2 et n-1 qui a trouvé sa place occupée). Il y a donc bien équiprobabilité. Autrement dit :
Il est certain qu'il existe un unique k entre 1 et n-1 tel que passager k occupe place 1 ou place n,
et pour tout k de 1 à n-1, probabilité (passager k occupe place 1 sachant que passager k occupe place 1 ou place n) = 1/2.
Variante : sur l'ensemble de toutes les histoires possibles, il y a une involution qui échange simplement les étiquettes des places n°1 et n°n. Il y a donc autant d'histoires où le passager n°n termine à la place n que d'histoires où il termine à la place 1.
Bernard-maths
Bonsoir !
Bon, j'ai fait un arbre :
Si le passager
1 prend sa place 1 alors tout le monde est bien placé, donc n aussi ; P(1 prend 1) = 1/n.
Si le passager
1 prend la place n alors n est mal placé ; P(1 prend n) = 1/n.
Sinon
1 prend une place parmi (n-2). Il faut alors placer n en dernier, et les (n-2) autres sur (n-1) places laissées par
1. Deux cas se présentent ...
SOIT aucun des (n-2) ne prend la place n, et donc n est bien placé ;
SOIT l'un des (n-2) prend la place n ... et n est mal placé !
Dans cet arbre il y a deux cas favorables pour que n soit bien placé. Reste à faire les calculs !!!
Remarquons que la 2ème flèche verte est la cas contraire de la 2ème rouge, pour les (n-1) places ... on a vu ça y'a pas longtemps ?
Bons calculs, Bernard-maths
Michel-Coste
Dans les deux cas "n mal placé", n est en fait placé en 1, ce qui permet de faire de très très grosses économies de calcul.
Bernard-maths
@ Michel !
Oui, je cherche mieux, mais je suis sur un autre sujet urgent ...
J'ai fait cet arbre à l'ordre 4, et on trouve bien 1/2 ...
Bernard-maths
Zebulor
Bonjour,
en attendant le retour de Bernard Maths, on peut aussi voir que:
- soit le premier passager s'assoit sur la place 1 et chacun des $n$ passagers occupe sa place réservée.
- soit il s'assoit sur une autre place $x$ comprise entre 2 et $n$ et les places suivantes 2 à $x-1$ sont occupées.
Ensuite le passager $x+1$ prend une place entre $x+1$ et $n$...etc de sorte qu'on a une récurrence
Sinon le début de solution de Glozi post 18 a le mérite d'être synthétique...
Invite
Message de Glozi (sans compte)
Bonjour,
Zebulor, dans ta deuxième option, si la premier passager s'assoit sur la place $x$ entre $2$ et $n$. Alors, ce sont les places $2$ jusqu'à $x$ qui seront occupées. Puis lorsque vient le tour du passager $x$, il reste $n-x+1$ personnes non assises dans l'avion (en comptant la personne $x$). On décrète alors que la nouvelle place de $x$ est la place $1$ (qui est libre). En faisant ça alors on se trouve dans la même situation qu'au début mais avec $n-x+1$ passagers et sièges au lieu des $n$ de départ (le passager $x$ joue le rôle du passager $1$ et il va choisir sa place au hasard sachant que l'ancienne place $1$ est celle qui ne dérangera personne ensuite). Ainsi avec les notations de mon post 18, on voit que $\mathbb{P}(A_n | X= x) = p_{n-x+1}$ dès que $2\leq x \leq n-1$.
Finalement, on trouve pour $n\geq 2$ :
$$p_n = \sum_{x=1}^{n-1}\mathbb{P}(X=x)\mathbb{P}(A_n | X=x) = \frac{1}{n} \times 1 + \frac{1}{n}\sum_{x=2}^{n-1}p_{n-x+1} = \frac{1}{n}+\frac{1}{n}\sum_{x=2}^{n-1}p_x.$$
Ceci permet de montrer par récurrence que $p_n=1/2$ dès que $n\geq 2$.
Sinon j'ai bien aimé la solution donnée par Michel Coste, c'est très joli !
Bonne journée
Zebulor
Bonjour,
@Glozi : très jolie formulation .. !
A te relire si j'ai bien compris tu pars en fait simplement de :
$A_n=A_n \cap (\bigcup_{p=1}^n ( X=p))$, sachant que $\bigcup_{p=1}^n ( X=p)$ forme un système complet d'événements
Glozi a écritSinon j'ai bien aimé la solution donnée par Michel Coste, c'est très joli !
Elle exprime la symétrie illustrée par : $\sum_{x=2}^{n-1}p_{n-x+1} = \sum_{x=2}^{n-1}p_x.$
Glozi a écriton peut exprimer les $\mathbb{P}(A_n | X=k)$ (pour $k\geq 2$) en fonction de certains $p_k$...
C'est le coeur du sujet me semble t il, qui demande le plus de réflexion
Bonne journée.
Invite
Message de Glozi (sans compte)
Exactement Zebulor, c'est aussi connu sous le nom des de la formule des probabilités totales si je ne m'abuse. (ensuite on utilise la formule des probabilités conditionnelles).
Moralement, c'est juste une disjonction de cas en fonction de quel place choisi le premier passager.
Bonne journée
Invite
Message de Glozi (sans compte)
Bonsoir,
Zebulor si tu modifies ton message après qu'on t'ait répondu la conversation risque de perdre son sens :p
Sinon pour moi la solution de Michel Coste n'a pas grand chose à voir avec le calcul $\sum {p_{n-x+1}}= \sum p_x$ (ou alors il faut que tu m'expliques). Pour moi cette égalité entre sommes est juste un calcul formel (on prend les termes de la somme dans l'autre ordre).
Il faudrait la confirmation de Michel Coste, mais selon moi on peut utiliser son argument ainsi :
Soit $N\in \{1,\dots,n\}$ la variable aléatoire qui correspond au numéro du premier passager qui choisi le siège $1$ ou $n$.
Par exemple s'il y a $n=4$ personnes :
passager $1$ choisit $3$
passager $2$ choisi $2$ (pas le choix)
passager $3$ choisi $4$ (au hasard)
passager $4$ choisi $1$ (le seul qui reste).
Alors $N=3$ car avant le passager $3$ les deux sièges $1$ et $4$ étaient libres mais plus après qu'il se soit assis.
Il y a deux choses à remarquer :
1. Les passagers $N+1$ jusqu'à $n-1$ vont tous s'assoir à leur place.
2. Le passager $N$ aura choisi le siège $1$ ou $n$ avec équiprobabilité.
Je te laisse te convaincre du premier point si tu veux.
Pour le deuxième point il s'agit de voir que la loi de la variable aléatoire $Y$ du choix du passager $N$ est la même que la loi du choix d'un passager conditionnellement à choisir la place $1$ ou $n$. (je pense que cela peut se prouver rigoureusement en distinguant selon la valeur de $N$ avec les probas totales par exemple).
Ainsi la proba que le $N$ième passager choisisse $1$ est $1/2$. Et à la fin le dernier passager va choisir l'autre option (donc il aura également proba 1/2 d'être à sa place).
Bonne soirée
Zebulor
re,
Glozi a écritBonsoir,
Zebulor si tu modifies ton message après qu'on t'ait répondu la conversation risque de perdre son sens :p
Tu as raison ! je vais relire ce qu'a écrit Michel Coste.
Alors pour mettre les choses au clair ton post précédent ne portait que sur ceci : $A_n=A_n \cap (\bigcup_{p=1}^n ( X=p))$
Bonne soirée
Michel-Coste
Je reprends l'argument que j'ai donné (ce n'est la vraiment le mien).
Je préfère mathématiser complètement en parlant de l'ensemble Ω des permutations σ de {1,…,n} telles que, pour tout k tel que 1<k≤n, s'il n'existe pas de ℓ<k tel que σ(ℓ)=k, alors σ(k)=k.
La remarque fondamentale est que, pour tout σ∈Ω, tout entier k tel que 2≤k≤n−1 est dans σ({1,…,n−1}). En effet, ou bien il existe ℓ<k tel que σ(ℓ)=k ou bien σ(k)=k. On a donc σ(n)=1 ou σ(n)=n.
Soit τ la transposition (1,n). Pour tout σ∈Ω, τ∘σ∈Ω. La deuxième remarque importante est que la probabilité de l'issue σ est égale à la probabilité de l'issue τ∘σ. En effet, les événements \(E_k=\{\sigma\in \Omega\mid \sigma(k)=1\text{ ou }\sigma(k)=n\}\) pour \(k=1,\ldots,n-1\) forment un système complet d'événements d'après la première remarque, et \(P(\sigma(k)=1\mid E_k)=P(\sigma(k)=n\mid E_k)=1/2\).
La conclusion \(P(\sigma(n)=n)=1/2\) suit de ces deux remarques, sans aucun calcul.
Zebulor
Bonjour,
je reviens sur cette discussion et redescends de plusieurs crans dans la mathématisation en proposant une autre manière de voir les choses :
$E_n$ : le passager $n$ est à sa place $n$
$A_1$ : le passager 1 est à sa place 1
$A_p$ : le passager 1 est à la place p
$F_p$ : parmi les passagers $p$ à $n$, l'un au moins est à sa place
Alors on a : $E_n$=$A_1 \bigcup (\bigcup_{p=2}^{n-1} (A_p \bigcap F_p)) $
On devrait pouvoir trouver $P(E_n)$ de cette manière...
Invite
Message de Glozi (sans compte)
Bonsoir,
Je crois que je n'ai pas bien compris l'idée derrière $F_p$, en effet prenons un exemple si $n=4$, le premier passager choisit le siège $2$ (au hasard), le passager $2$ choisit le siège $4$ (au hasard) le passager $3$ choisit le siège $3$ (car c'est libre), le passager $4$ choisit le siège $1$ (pas le choix). Alors $A_2$ se produit et $F_2$ se produit (puisque $3$ s'est assis à sa place). Pourtant $E_4$ n'est pas réalisé.
(par ailleurs pour ne pas se faire avoir au niveau des notations je pense qu'on pourrait noter que $A_1$, $A_p$ et $F_p$ dépendent tous de $n$).
Peut être que tu voulais $F_p$ : "l'un des passager de $p$ à $n-1$ s'assoit à la place $1$" ?
Bonne soirée
Zebulor
Bonsoir Glozi,
oui pour la réponse à ta question finale et ton contre exemple parle de lui même.
Ca ne marche pas mais on doit pouvoir dénombrer des bijections en posant bien le problème
Invite
Message de Glozi (sans compte)
Bonjour,
Je m'étais posé la question avec des bijections.
J'ai essayé de formaliser
On pose $$\Omega := \{\sigma \in \mathfrak{S}_n | \forall 2\leq i \leq n, \sigma(i)\neq i \Rightarrow \exists j<i, \sigma(j)=i\}.$$
$\Omega$ représente notre univers, un $\sigma \in \Omega$ représente une "histoire" ($\sigma(i)=j$ signifie que le passager $i$ s'assied sur le siège $j$.
Première remarque : il faut voir que toutes les histoires $\sigma$ ne sont pas equiprobables.
Deuxième remarque : (pour $n\geq 2$)
Si $E_1 :=\{\sigma \in \Omega | \sigma(n)=1\},$
et $E_n :=\{\sigma \in \Omega | \sigma(n)=n\},$
Alors $E_1$ et $E_n$ sont disjoints et forment une partition de $\Omega$ (car on a vu que le dernier passager s'assoit ou bien à la place 1 ou bien à la place n).
Maintenant, si $\sigma$ est une histoire. On considère $T(\sigma) := \min\{i, \sigma(i) \in \{1,n\}\}$
On pose $F : \Omega \to \Omega$
telle que $\sigma'=F(\sigma)$ verifie :
$\sigma'(T(\sigma))=\sigma(n)$,
$\sigma'(n)=\sigma(T(\sigma))$,
$\sigma'(i)=\sigma(i)$ pour les autres $i$.
Autrement dit dans une histoire, on attend le premier passager qui va s'assoir à la place 1 ou n et on change l'histoire en disant que s'il prenait le siege 1 alors il prend le siege n et vice versa. (il faudrait verifier que $F$ est bien definie à valeur dans $\Omega$)
Alors on verifie egalement que $F$ est une bijection (c'est une involution). Qui envoit $E_1$ sur $E_n$ et $E_n$ sur $E_1$.
On verifie surtout que $\mathbb{P}(\sigma)= \mathbb{P}(F(\sigma))$ (c'est le point clé du raisonnement et cela utilise seulement le fait qu'après $T(\sigma)$ l'histoire est deterministe, et que le passager $T(\sigma)$ a autant de chance de choisir 1 ou n puisque son choix est uniforme).
On deduit en sommant sur les $\sigma\in E_1$ que
$$\mathbb{P}(E_1) = \mathbb{P}(E_2).$$
Et si $n\geq 2$ alors
$$\mathbb{P}(E_1) + \mathbb{P}(E_2) =1.$$
On deduit la proba 1/2 quand $n\geq 2$.
Bonne journée
Invite
Message de Glozi (sans compte)
Sinon l'approche que tu proposes avec $E_n = A_1 \cup \bigcup (A_p \cap F_p)$
est selon moi assez proche de ce que j'avais proposé au debut de de fil. C'est une approche dynamique :
Il suffit de voir que si $2\leq p\leq n-1$ alors $\mathbb{P}(F^{(n)}_p |A^{(n)}_p)$ est en fait egal à $\mathbb{P}(E^{(n-p+1)}_{n-p+1})$
(je me suis permis de faire apparaître la dependance de ces événement sur le nombre de passager en exposant)
Bonne journée
Zebulor
Bonjour,
intéressante ta tentative avec des bijections.. belle analyse...
Bonne soirée :-)
Zebulor
Bonjour,
j'ai trouvé une autre voie avec des puissances de 2 dans cette affaire ...
Je reprends le post de Glozi :
en effet prenons un exemple si $n=4$, le premier passager choisit le siège $2$ (au hasard), le passager $2$ choisit le siège $4$ (au hasard) le passager $3$ choisit le siège $3$ (car c'est libre), le passager $4$ choisit le siège $1$ (pas le choix).
Donc :
1 est en 2
2 est en 4
3 est en 3
4 est en 1
d'où la construction d'une bijection $f$ telle que f(1)=2, f(2)=4, f(3)=3 et f(4)=1.
Une prof de maths me suggérait de considérer les itérés de f(1) qui contiennent le dernier passager que sont : $f^{(2)}(1)=4, f^{(3)}(1)=1$.
Alors j'ai creusé l'idée...
Dans cet exemple le cycle de 1 qui contient 4 qu'est (1,2,4) est d'ordre 3 parce qu'il contient 3 éléments.
L'idée est d'abord de s'intéresser alors à toutes les bijections pour un $n$ fixé supérieur ou égal à 2 telles que le dernier passager n'est pas à sa place.
En généralisant pour $n$ quelconque, on considère l'événement $A_p$ : le cycle de 1 d'ordre $p$ qui contient $n$ s'écrit :
$(1,f(1), ......,f^{(p-1)}(1)=n)$ où $p \in [\![2;n]\!]$
A $p$ fixé dans l'intervalle précédent il y a $\binom{n-2}{p-2}$ cycles possibles. En sommant sur tous les $p$ et après calculs on obtient $2^{n-2}$ cycles de 1 contenant $n$.
Ensuite on examine toutes les bijections (toujours pour un $n$ fixé) telles que le dernier passager est à sa place.
Si on considère une de ces bijections, elle est nécessairement construite comme suit :
_un cycle de 1 d'ordre $m$, où $m \in [\![1;n-1 ]\!]$
_$f(k)=k$ pour tout $k \in [\![m+1;n]\!]$ car dans ces configurations, à partir d"un rang quelconque chaque passager prend la place qu"il a reservée, y compris le dernier nécessairement.
Le cas $m=1$ est simple : chaque passager $j$ est à la place $j$, y compris le dernier $n$...
Sinon on se ramène à l'étude du cas précédent et en sommant sur tous les $m$ allant de 2 à $n-1$ ça donne
$2^0+2^1+.....+2^{n-3}=2^{n-2}-1$ bijections
Au total on a $2^{n-2}-1+1=2^{n-2}$ configurations où le dernier passager est à sa place.
La probabilité que le dernier passager soit à sa place est donc : nombre de cas favorables/nombre de cas possibles= $\dfrac {2^{n-2}}{2^{n-2}+2^{n-2}}=\dfrac {1}{2}$
A noter que si $n$ passe à $n+1$ le nombre de dispositions possibles des passagers double...