\chapterimage{hunger}
\chaptertext{Sans instruction précise cette année,  voici des planches des années
  précédentes  qui peuvent  être traitées  avec Python.  Il y  a aussi  quelques
  exercices de probabilité inspirés des planches de\textsc{ BCPST}} 

\chapter{Python à l'oral de Centrale}






\begin{exercice}
Représenter  graphiquement le  système  dynamique défini  par une  suite
$u_{n+1}=f(u_n)$  et la  donnée  de  $u_0$. On  fera  figurer la  courbe
représentative de $f$ ainsi que la première bissectrice et bien sûr l'escargot.
\end{exercice}






\begin{exercice}
Soit $a\in[0,1[$.
\begin{enumerate}
\item  Démontrer  que pour  tout  $n\in\bbn$,  l'équation $(E_n):  \displaystyle
  \int_0^x \frac{t^n\exp(-t)}{n!}\d t = a$ d'inconnue $x\in\bbr_+$, admet une unique
  solution notée $x_n$.
\item Donnez une approximation de $x_n$ à 0,001 près en fonction de $a$ et $n$.
On              pourra             utiliser              la             fonction
\mintinline{python}{scipy.integrate.quad(f,binf,bsup)}. Faire différents tests. 
\item  Prolongement:  étudier la  monotonie  de  $(x_n)$ puis  son  comportement
  asymptotique.

\end{enumerate}

% \begin{somution}
%\begin{pythoncode}
% import math
% import numpy as np
% import scipy as sp
% import scipy.integrate as integ


% def approche(a,n):
%     f = lambda x: integ.quad(lambda t: t**n*np.exp(-t)/math.factorial(n), 0, x)[0] - a
%     borne = 0
%     while f(borne) < 0:
%         borne +=  1
%     gauche, droite = borne - 1, borne
%     while (droite - gauche) > 0.01:
%         milieu = gauche + (droite - gauche)*0.5
%         (gauche, droite) = (gauche, milieu) if f(milieu) > 0 else (milieu, droite)
%     return (gauche, droite)
%\end{pythoncode}    
%\end{solution}   


\end{exercice}



\begin{exercice}
  On      pose     $P_0(X)=1$      et,      pour     tout      $n\in\bbn^\star$,
  $P_n(X)=\frac{X(X-1)\cdots(X-(n-1))}$. On note $a_n=\int_0^1P_n$.

  \begin{enumerate}
  \item Calculer $a_0,..,a_{10}$ avec Python.  Conjecturer la valeur du rayon de
    convergence R de la série entière $\sum a_nx^n$.
\item  Calculer  R.   On  note  $f$  la  somme  associée   à  la  série  entière
  précédente. Montrer que $$∀x \in ]-R,R[, f(x)=\int_0^1(1+x)^t\d t$$
  \end{enumerate}

%   \begin{solution}
%     \begin{pythoncode}
% import scipy.integrate as integ

% def p(x,n):
%     tmp = 1
%     for k in range(n):
%         tmp *= (x - k) / (k + 1)
%     return tmp


% def a(i):
%     return integ.quad(lambda x: p(x,i), 0, 1)[0]      
%     \end{pythoncode}
    

%   \end{solution}
\end{exercice}







\begin{exercice}[Centrale 2011]
Soit $G$ le sous-groupe de $GL_2(\bbr)$ engendré par les deux matrices $S$ et $T$ suivantes :

\[ S=
\begin{pmatrix}
-1&0\\
0&1
\end{pmatrix}
,
T=\frac{1}{\sqrt{2}}
\begin{pmatrix}
-1&1\\
1&1
\end{pmatrix}
\]

Rappelons que c'est le plus petit sous-groupe de $GL_2(\bbr)$ contenant $S$ et $T$.
\begin{enumerate}
\item  Avec  Python,  créer les  matrices  $S$,
  $T$. Expliciter les éléments du groupe $\langle R\rangle$ engendré par la matrice $R=ST$ et préciser le cardinal de ce sous-groupe de $G$.
Quelles sont les matrices $SR$ et $R^7S$?
\item Montrer  que tout élément de  $G$ est soit une  puissance $R^k$ de
  $R$, soit un produit $R^kS$. Préciser le cardinal $n$ de $G$.
Dresser la liste de tous les éléments de $G$ et déterminer la nature géométrique des endomorphismes canoniquement associés dans l'espace euclidien $R^2$.
\item  La transformation $\Phi_S:g\mapsto S\cdot g$ définit une permutation de l'ensemble $G$.
À l'aide de Python, dresser la séquence des éléments
de $G$ et de leurs images par $\Phi_S$.
Quelle est la signature de la permutation de $G$ (qu'on peut identifier à l'ensemble $\{1,2,…,n\}$) ainsi définie ?
\end{enumerate}

Attention aux tests d'égalité sur des flottants!...
\end{exercice}





% \begin{solution}
% \begin{enumerate}
% \item On définit les matrices $S$ et $T$ puis on calcule $R$:

% \begin{lstlisting}
% S:=Matrix(2,2,[-1,0,0,1]);
% T:=Matrix(2,2,[-1,1,1,1])/sqrt(2);
% R:=S.T;
% \end{lstlisting}


% \[R=\frac{1}{\sqrt{2}}
% \begin{pmatrix}
% 1&-1\\1&1
% \end{pmatrix}
% \]

% La matrice $R$ est la  matrice d'une rotation d'angle $\frac{\pi}{4}$ et
% donc vérifie $R^8=I_22$. On en déduit:

% \[\langle R\rangle=\{I_2,R,R^2,...,R^7\}\]

% groupe cyclique de cardinal 8.
% On peut visualiser les éléments de $\langle R\rangle$ en écrivant

% \begin{lstlisting}
% seq(R^k,k=0..7);
% \end{lstlisting}


% On calcule $SR$ et $R^7S$:

% \begin{lstlisting}
% S.R;
% R^7.S;
% \end{lstlisting}


% On constate que $SR=R^7S=T$.

% \item Considérons $H=\langle R\rangle ∪\langle R\rangle S$.


% $H$ est évidemment une partie de $G$ contenant $S$ et $T$.
% On établit aisément $SR^{\ell} =R^{7\ell} S$ pour tout $\ell \in \Z$.
% On en déduit alors que $H$ est stable par produit.
% On en déduit aussi que $H$ est stable par passage à l'inverse car
% \[(R^kS)^{−1}=S^{−1}R^{−k}=SR^{−k}=R^{−7k}S\]
% Ainsi $H$  est un sous-groupe inclus  dans $G$ contenant $S$  et $T$. Or
% $G$ est le plus petit sous-groupe contenant $S$ et $T$ donc $G=H$.

% Il y a  8 éléments dans $\langle R\rangle$,  l'application $M\mapsto MS$
% étant injective, il y aussi  8 éléments dans $\langle R\rangle S$. Enfin
% les  éléments $\langle  R\rangle$  sont distincts  de  ceux de  $\langle
% R\rangle S$ car de déterminants distincts.
 
% On en déduit

% \[G=\{I_2,R,R^2,...,R^7\}\cup \{S,RS,R^2S,...,R^7S\}\]
% de cardinal $n=16$.

% La séquence de tous les éléments de $G$ est

% \begin{lstlisting}
% seq(R^k),k=0..7),seq(R^k.S),k=0..7);
% \end{lstlisting}

% Les endomorphismes  canoniquement associés  aux éléments $R^k$  sont des
% rotations, plus précisément, les rotations d'angles $\frac{k\pi}{4}$.

% Les endomorphismes  canoniquement associés  aux éléments $R^kS$  sont des
% réflexions.  L'axe  de réflexion  s'obtient  en  recherchant un  vecteur
% propre associé à la valeur propre 1. 

% \item  On obtient  la séquence  des  images respectives  de la  séquence
%   précédente donnant les éléments de $G$ en écrivant 

% \begin{lstlisting}
% seq(S.R^k),k=0..7),seq(S.R^k.S),k=0..7);
% \end{lstlisting}


% La permutation de $\{1,2,...,16\}$ correspondante est

% \[
% \left(
% \begin{array}{*{16}{l}}
% 1&2 &3 &4 &5 &6 &7 &8 &9&10&11&12&13&14&15&16\\
% 9&16&15&14&13&12&11&10&1&8 &7 &6 &5 &4 &3 &2\\
% \end{array}
% \right)
% \]


% Le nombre d'inversion de celle-ci est
% \[8+(14+13+12+11+10+9+8)+0+(6+5+4+3+2+1+0)\]
% soit encore
% \[(1+2+\cdots+14)+1=106\]
% La permutation considérée est donc paire, i.e. de signature 1.
% On peut aussi tenter un calcul direct avec Maple

% On définit la liste des éléments de $G$.

% \begin{lstlisting}
% L:=[seq(R^k,k=0..7),seq(R^k.S),k=0..7)]:
% \end{lstlisting}

% On définit la procédure donnant l'indice d'un élément de G

% \begin{lstlisting}
% indice:=proc(M)
% local k;
% global L;
% for k from 1 to 16 do
% if equal(M,L[k]) then RETURN(k) fi
% od
% end:
% \end{lstlisting}

% Enfin on calcule la signature par la formule:

% \[\varepsilon(\sigma)=\displaystyle\prod_{i<j}\frac{\sigma(j)−\sigma(i)}{j−i}\]

% ce qui se traduit par:

% \begin{lstlisting}
% product(product((indice(M[j])-indice(M[i]))/(j-i),j=i+1..16),i=1..15);
% \end{lstlisting}


% \end{enumerate}
% \end{solution}






\begin{exercice}[Centrale 2011]
 
  On définit pour $n \in \mathbb{N}^\star $ les nombres complexes
$$u_n  = \prod\limits_{k = 1}^n {\left( {1 + \frac{i}{{k^2 }}} \right)} \text{ et }v_n  = \prod\limits_{k = 1}^n {\left( {1 + 2\frac{i}{k}} \right)} $$
\begin{enumerate}
\item  On note, dans le plan complexe, $A_n $ et $B_n $ les points d'affixes respectives $u_n $ et $v_n $.

Utiliser Python pour visualiser les lignes polygonales $A_1 ,A_2 , \ldots ,A_n $ et $B_1 ,B_2 , \ldots ,B_n$ pour diverses valeurs de $n$, par exemple 500,1000\ldots.

\item  Étudier la convergence de la suite $(u_n )$.\\
S'il y a convergence, donner à l'aide de Python, une valeur
approchée (par module et argument) de  $\mathop {\lim }\limits_{n \to + \infty }
u_n $ à $10^{-3}$ près.

\item  Étudier la convergence de la suite $(v_n )$.\\
On pourra justifier l'existence d'une constante $L$ telle que :
$$\sum\limits_{k = 1}^n {\arctan \frac{2}{k}}  = 2\ln n + L + o(1)$$
et étudier la nature (convergente ou divergente) de la suite complexe $(z_n )_{n \geqslant 1} $ :
$$z_n  = \exp (2i\ln n)$$

  \end{enumerate}
\end{exercice}










\begin{exercice}[Centrale,  2010]

    \begin{enumerate}
        \item
            Démontrer que, si deux endomorphismes $u$ et $v$ d'un espace vectoriel $E$ commutent, alors, les sous-espaces
            propres de $u$ et l'image de $u$ sont stables par $v$.

            Dans les deux cas suivants :
            \[
            A = \left( \begin{array}{cccc}
                {20} & {12} & { - 4} & {12}  \\
                { - 4} & { - 3} & 9 & { - 5}  \\
                { - 4} & 1 & 5 & { - 5}  \\
                { - 8} & { - 10} & 6 & { - 2}  \\
            \end{array} \right)
            \quad \text{ et } \quad
            A = \left( \begin{array}{cccc}
                { - 12} & { - 16} & { - 8} & { - 4}  \\
                4 & {13} & 1 & { - 1}  \\
                4 & 5 & 9 & { - 1}  \\
                8 & {10} & 2 & 6  \\
            \end{array} \right)
            \]

        \item
            Préciser les matrices qui commutent avec $A$ (structure, dimension, base éventuelle).

        \item
            Etudier dans ${\mathcal{M}}_4 (\mathbb{R})$, puis dans ${\mathcal{M}}_4 (\mathbb{C})$, l'équation
            \[
            X^2  = A
            \]
            (nombre de solutions, un exemple de solution quand il y en a, somme et produit des solutions quand elles sont en nombre fini).
    \end{enumerate}




  \end{exercice}
  

 % \begin{enumerate}
 %            \item  C'est du cours.
 %            \item  On charge le package permettant les manipulations linéaires
 %                puis on définit la matrice

 %                On observe que dans le premier cas,  $A$ est diagonalisable  et
 %                semblable à $\diag(8,4,12,-4)$.

 %                De même dans le deuxième cas, $A$ est diagonalisable  et
 %                semblable à $\diag(-4,8,8,4)$.

 %                Puisque dans les deux cas la matrice $A$ est diagonalisable, les
 %                matrices commutant avec $A$ sont celles laissant stables les
 %                sous-espaces propres de $A$.

 %                \begin{itemize}
 %                    \item
 %                        Dans le premier cas, les matrices commutant avec $A$
 %                        sont de la forme $PDP^{-1}$ avec $D$ matrice diagonale
 %                        et $P$ la matrice de passage dans une base de
 %                        diagonalisation de $A$, obtenue précédemment avec \mpl.
 %                        L'ensemble de ces matrices est une sous-algèbre de
 %                        dimension 4 de $\Mn[4]{\K}$.

 %                    \item
 %                        Dans le deuxième cas, les matrices commutant avec $A$
 %                        sont de la forme $QΔQ^{-1}$ avec $Δ$ diagonale par blocs
 %                        de la forme suivante
 %                        \[
 %                        Δ=\begin{pmatrix}
 %                            a & 0 & 0 & 0 \\
 %                            0 & b & c & 0 \\
 %                            0 & d & e & 0 \\
 %                            0 & 0 & 0 & f \\
 %                        \end{pmatrix}
 %                        \]
 %                        et $Q$ la matrice de passage  dans une base de
 %                        diagonalisation de $A$, obtenue précédemment avec \mpl.
 %                        L'ensemble de ces matrices est une sous-algèbre de
 %                        dimension 6 de $\Mn[4]{\K}$.
 %                \end{itemize}

 %            \item
 %                \begin{itemize}
 %                    \item
 %                        Dans le premier cas, l'équation $X^2=A$ n'admet pas de
 %                        solution dans $\Mn[4]{\R}$ puisque $\det A < 0$.

 %                        Étudions l'équation dans $\Mn[4]{\C}$.  Si $X$ est solution,
 %                        alors $X$ commute avec $A$, donc $X$ laisse stable chacun des
 %                        sous-espaces propres de $A$, à savoir chacune des quatre droites
 %                        propres de $A$.  Donc la restriction de (l'endomorphisme
 %                        canoniquement associé à) $X$ à chacune de ces droites est une
 %                        homothétie.  Donc $X$ est diagonalisable dans toute base de
 %                        diagonalisation de $A$.

 %                        On obtient donc $2^4=16$ solutions, qui sont de la forme
 %                        \[
 %                        P\diag(±2\sqrt{2}, ±2, ±2\sqrt{3}, ±\ii\sqrt{2})
 %                        \]
 %                        où $P$ est la matrice de passage dans une
 %                        base de diagonalisation de $A$,  obtenue avec \mpl.

 %                    \item Même raisonnement : les solutions sont de la forme
 %                        \[
 %                        Q\diag(±\ii2,S, ±2)Q^{-1}
 %                        \]
 %                        où $S∈\Mn[2]{ℂ}$ vérifiant $S^2=I_2$ (\cad une symétrie de
 %                        $ℂ^2$). Il y a donc une infinité de solutions.
 %                \end{itemize}
 %        \end{enumerate}























\begin{exercice}[Comportement asymptotique des chaînes de Markov]

Zlot, Brzxxz  et Morzgniouf sont trois villes  situées respectivement en
Syldavie, Bordurie et Bouzoukstan.  Des trafiquants de photos dédicacées
du  groupe  ABBA  prennent  leur  marchandise le  matin  dans  n'importe
laquelle de  ces villes  pour l'apporter le  soir dans  n'importe quelle
autre. On  notera pour  simplifier $V_1$, $V_2$  et $V_3$ ces  villes et
$p_{ij}$ la probabilité qu'une marchandise  prise le matin dans la ville
$V_i$   soit  rendue   le  soir   dans  la   ville  $V_j$.   La  matrice
$P=(p_{ij})_{{1\leqslant   i   \leqslant  3}\atop   {1\leqslant   j\leqslant   3}}$  est   appelée
\textit{matrice de transition} de la chaîne de \textsc{Markov}.


\begin{definition}[Matrice stochastique]
  Une matrice dont  tous les coefficients sont positifs  ou nuls et dont
  la  somme  des  coefficients  de  chaque  ligne  vaut  1  est  appelée
  \textbf{matrice stochastique}.

Si, de plus, la somme des colonnes vaut 1, la matrice est dite \textbf{bistochastique}.
\end{definition}

Que peut-on dire d'une matrice de transition?



Voici le diagramme de transition des trafiquants suédophiles:


\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten                 >=1pt,auto,node
  distance=5cm,semithick, bend angle=10]
\tikzstyle{every state}=[fill=white,draw=black,text=black,minimum height = 2em]
\tikzstyle{accepting}=[fill=blue!20,draw=black,text=blue,accepting right,double]
\tikzstyle{initial}=[fill=green!20,draw=black,text=red,initial by arrow,initial text=]
 

 \node[state] (A) {$V_1$};
 \node[state] (C) [below right of =A] {$V_3$};
 \node[state] (B) [below left of =A] {$V_2$};

 \path 
       (C) edge[bend left] node[below left] {0,2} (A)
       (A) edge[bend left] node[above right] {0,1} (C)
       (A) edge[loop above] node[above] {0,8} (A)
  (B) edge[bend left] node[above left] {0,3} (A)
       (A) edge[bend left] node[below right] {0,1} (B)
       (B) edge[loop below ] node[below ] {0,2} (B)
(C) edge[bend left] node[below] {0,6} (B)
       (B) edge[bend left] node[above] {0,5} (C)
       (C) edge[loop below ] node[below ] {0,2} (C)
       ;
\end{tikzpicture}
\end{center}

La matrice de transition est:


$$
\begin{pmatrix}
0,8&0,1&0,1\\
0,3&0,2&0,5\\
0,2&0,2&0,6
\end{pmatrix}
$$


On notera  $x_i^{(k)}$ la proportion  de trafiquants qui se  trouvent au
matin du jour $k$ dans la ville $V_i$.


\begin{definition}[Vecteur d'état]
 On appelle
\textit{vecteur d'état}  tout élément $(x_1,...,x_n)$  de $\bbr^{n}$ tel
que $x_1+\cdots+x_n=1$. 
\end{definition}

Ainsi,  $x^{(k)}=\left(   x_1^{(k)},x_2^{(k)},x_3^{(k)}\right)$  est  un
vecteur d'état (pourquoi?).


\begin{recherche}
 Démontrez que: 
$$\forall k \in \llbracket 1,n\rrbracket,\quad x^{(k)}= x^{(k-1)}\cdot P$$

puis que:

$$\forall k \in \llbracket 1,n\rrbracket,\quad x^{(k)}=x^{(0)}\cdot P^k$$

\end{recherche}


Supposons que le chef de la mafia locale dispose de 1000 trafiquants qui partent tous le matin du jour 0 de la ville de Zlot. Quelle sera la proportion de trafiquants dans chacune des villes au bout d'une semaine ? d'un an ?

Il s'agit donc de calculer  des puissances successives de P.

On obtient les proportions au bout d'une semaine en 
calculant $ x^{(0)}\cdot p^7$ avec $x^{(0)}=\left(1000,0,0 \right)$.



Utilisez Python pour étudier la stabilité des proportions dans le temps.

   Observez  que  cette  matrice  \og à  l'infini\fg{}  a  trois  lignes
identiques.   Étudiez   le   produit   d'un  vecteur   ligne   de   \og
$A_{\infty}$\fg{} par A.

Troublant....En fait, ce résultat se généralise.


\begin{definition}[Matrice de transition régulière]
Une matrice de transition A est dite régulière si, et seulement si, il
existe  un entier  naturel $r$  tel que  $A^r$ a  ses  coefficients tous
\textbf{strictement} positifs.
\end{definition}


\begin{theoreme}[Théorème des chaînes de \textsc{Markov} régulières]
Soit A une matrice régulière. Il existe une matrice stochastique:

$$
A_{\infty}=\begin{pmatrix}
  a_1&a_2&\cdots&a_n\\
  a_1&a_2&\cdots&a_n\\
  \vdots&\vdots&\vdots&\vdots\\
  a_1&a_2&\cdots&a_n\\
\end{pmatrix}
$$

telles que $ \displaystyle\lim_{n \to +\infty} A^n =A_{\infty}$.


De plus, $v=(a_1,a_2,\cdots,a_n)$ est l'unique vecteur d'état stationnaire
(tel que $v\cdot A=v$).
\end{theoreme}

\end{exercice}






\begin{exercice}[Simulation]
Simulez le  tirage successif  de cinq jetons  avec remise dans  une urne
contenant cinq  jetons blancs  et neuf jetons  noirs. On  s'intéresse au
nombre de jetons blancs obtenus. \\
Déterminez avec \textsf{Python} un tableau de fréquences pour 1 000 000 simulations.\\
Calculez ensuite la valeur exacte de la probabilité d'obtenir exactement
deux jetons blancs en justifiant votre réponse.


On       pourra        utiliser       \mintinline{python}{randint(a,b)}       ou
\mintinline{python}{random()} de \mintinline{python}{numpy.random}  ainsi que la
fonction       \mintinline{python}{Counter}       de       la       bibliothèque
\mintinline{python}{collections}  qui  renvoie  le dixtionnaire  des  fréquences
d'une liste de résultats.


\end{exercice}







\begin{exercice}[Le lièvre et la tortue]

On  dispose  d'un  dé  cubique  bien équilibré,  d'un  lièvre  et  d'une
tortue. On lance le dé. Si un \og 6\fg{}
sort, le  lièvre gagne, sinon la  tortue avance d'un mètre.  La tortue a
gagné lorsqu'elle a avancé cinq fois de suite.\\
Quelle est la probabilité pour la tortue de gagner?\\
Retrouvez expérimentalement ce résultat en simulant 1 000 000 parties de ce
jeu excitant.

\end{exercice}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2014_15"
%%% End: 
