Sujet
On considère ( \(\mathrm{A}_{0} ; \vec{i}, \vec{j}\) ) un repère du plan. Pour tout entier naturel \(n\), on note \(\mathrm{A}_{n}\) le point de coordonnées \(\left(n ; n^{2}\right)\).
On se place sur l'origine du repère puis on parcourt un chemin de \(N\) pas ( \(N \geqslant 1\) ) de sorte que chacun d'eux soit effectué aléatoirement et de manière équiprobable vers la droite (noté \(\mathbf{D}\) ) ou vers le haut (noté H).
Par exemple si \(\boldsymbol{N}=\mathbf{2}\), on a :
- 4 chemins possibles : DD, DH, HD et HH ;
- 3 arrivées possibles : le point \(\mathbf{A}_{1}\), le point de coordonnées ( \(2 ; 0\) ), ou celui de coordonnées ( \(0 ; 2\) ).
Nous appellerons chemin parabolique tout chemin ayant comme arrivée un des points \(\mathbf{A}_{n}\) (pour \(n \geqslant 1\) ) et passant par tous les précédents, c'est-à-dire \(\mathbf{A}_{0}, \mathbf{A}_{1}, \mathbf{A}_{2}, \ldots\) et \(\mathbf{A}_{\cdot n-1}\).
Par exemple :
- DH est un chemin parabolique (on part de \(\mathbf{A}_{0}\) et on arrive en \(\mathbf{A}_{1}\) );
- ainsi que HDHHDH (on part de \(\mathbf{A}_{0}\), on passe par \(\mathbf{A}_{1}\) et on arrive en \(\mathbf{A}_{2}\) );
- tandis que DD et HDHDD ne sont pas des chemins paraboliques.
Partie A
- Donner l'exemple d'une valeur de \(N\) pour laquelle il n'existe pas de chemin parabolique.
- Donner toutes les valeurs de \(N\) comprises entre 1 et 100 pour lesquelles il existe au moins un chemin parabolique.
- Compléter l'algorithme ci-dessous pour qu'il détermine s'il existe un chemin parabolique pour l'entier \(N\) saisi par l'utilisateur.
Variables: N,p(entiers)
Début
p prend la valeur 0
Saisir N
TantQue ................. < N
p prend la valeur p + 1
FinTantQue
Si
Afficher « Il existe un chemin parabolique pour cette valeur de N »
Sinon
Afficher « II n'existe pas de chemin parabolique pour cette valeur de N »
FinSi
Fin
Partie A
- Pour \(N=1\), il n'existe pas de chemin parabolique. En effet, pour cette valeur de \(N\), on arrive au point de coordonnées ( \(1 ; 0\) ) ou à celui de coordonnées ( \(0 ; 1\) ), donc sur un point qui n'est pas un des \(\mathrm{A}_{n}\).
- Pour une valeur de \(N\) donnée, il existe au moins un chemin parabolique si et seulement si on peut arriver sur un des \(\mathrm{A}_{n}\). Or, pour arriver en \(\mathrm{A}_{n}\), il faut avoir effectué dans un ordre indifférent \(n\) pas vers la droite et \(n^{2}\) vers le haut. Les valeurs de \(N\) pour lesquelles il existe au moins un chemin parabolique sont donc celles de la forme \(n+n^{2}\). Les valeurs de \(N\) comprises entre 1 et 100 pour lesquelles il existe au moins un chemin parabolique sont: \(1+1^{2}=2 ; 2+2^{2}=6 ; 3+3^{2}=1 ; 4+4^{2}=20 ; 5+5^{2}=30 ; 6+6^{2}=42 ; 7+7^{2}=56\); \(8+8^{2}=72 ; 9+9^{2}=90\), soit \(2,6,12,20,30,42,56,72\) et 90 .
- Algorithme
Variables : N,p (entiers)
Début
p prend la valeur 0
Saisir N
TantQue p + p \({ }^{\mathbf{2}}<\mathrm{N}\)
p prend la valeur p + 1
FinTantQue
Si \(\mathbf{p}+\mathbf{p}^{\mathbf{2}}=\mathbf{N}\)
Afficher « II existe un chemin parabolique pour cette valeur de N »
Sinon
Afficher « II n'existe pas de chemin parabolique pour cette valeur de N »
FinSi
Fin
Partie B
- Pour \(N=20\), un chemin est constitué de \(n\) pas vers la droite (avec \(0 \leqslant n \leqslant 20\) ) et de \(20-n\) pas vers le haut. Les arrivées possibles sont donc les points de coordonnées \((0 ; 20),(1 ; 19),(2 ; 18), \ldots,(20 ; 0)\). On a 21 arrivées possibles.
- On a deux possibilités pour le premier pas ( \(\mathbf{D}\) ou \(\mathbf{H}\) ). Pour chacun d'eux, on a encore 2 choix possibles pour le deuxième pas ( \(\mathbf{D}\) ou \(\mathbf{H}\) ), soit \(2^{2}=4\) chemins possibles pour les 2 premiers pas, etc. (on peut imaginer un arbre). Pour \(N=20\), on dénombre 220 chemins possibles.
- Pour \(N=20\), un chemin parabolique est du «type» \(\mathrm{A}_{0} \rightarrow \mathrm{~A}_{1} \rightarrow \mathrm{~A}_{2} \rightarrow \mathrm{~A}_{3} \rightarrow \mathrm{~A}_{4}\).
On compte
- 2 chemins possibles pour aller de \(\mathrm{A}_{0}\) à \(\mathrm{A}_{1}\)
- 4 chemins possibles pour aller de \(\mathrm{A}_{1}\) à \(\mathrm{A}_{2}\)
- 6 chemins possibles pour aller de \(\mathrm{A}_{2}\) à \(\mathrm{A}_{3}\)
- et 8 chemins possibles pour aller de \(\mathrm{A}_{3}\) à \(\mathrm{A}_{4}\).
Cela donne au total \(2 \times 4 \times 6 \times 8=384\) chemins paraboliques possibles.
Les chemins étant équiprobables, la probabilité d'effectuer un chemin parabolique est \(\frac{384}{2^{20}}=\frac{3}{8192}\).