Tag Archives: Mpsi/Pcsi

L’urne d’Ehrenfest, épisode 1

Une urne contient {N} boules indiscernables au toucher, de couleur bleue ou rouge.
On répète la « manipulation » suivante : « tirer une boule au hasard de l’urne et la remplacer par une boule de la couleur opposée »
On note {X_{n}} le nombre de boules bleues après la {n}-ième manipulation.
Dans cette partie, on calcule {\text{E}(X_{n})} et sa limite quand {n\rightarrow+\infty}.…Lire l’article…

Le dernier non effacé

On écrit à la suite tous les entiers de {1} jusqu’à {2017}.
On les efface de {3} en {3} : d’abord {1}, puis {4}, puis {7}, etc.
On recommence sur la liste restante 2,3,5,6,8,9,11,\ldots et ainsi de suite.
Quel est le dernier nombre affiché, et au bout de combien d’itérations?
Illustrer tout cela avec Python.

Cliquer ici pour voir le corrigé

La dernière moyenne

On écrit une liste de n nombres réels.
On en efface deux, pris au hasard, pour les remplacer par leur demi-somme.
On répète cette opération jusqu’à ce qu’il reste un seul réel X.
Quelle est la valeur minimum possible pour X? Illustrer avec Python.

Cliquer ici pour voir le corrigé

Pavage par des dominos

Soit {{\mathcal U}_{n}} une surface rectangulaire de 4*n cases.
Soit {u_{n}} le nombre de façons de remplir {{\mathcal U}_{n}} par des dominos (horizontaux ou verticaux).
On voit ci-dessous un exemple de remplissage du rectangle {{\mathcal U}_{9}}.
article-28-01-17-fig1

  1. 1. Trouver une relation de récurrence vérifiée par les {u_{n}}.
    Indication : comment la dernière colonne a-t-elle été remplie?
  2. 2. Écrire une fonction Python permettant de calculer {u_n}.
    Vérifier, par exemple, que {u_{30}=21096536145301}.
  3. 3. On définit le polynôme {P(x)=x^4-x^3-5x^2-x+1}
    Déterminer les racines {x_{1}\lt x_{2}\lt x_{3}\lt x_{4}} de P.
    Vérifier numériquement avec Python.
  4. Prouver que : {\forall\, n\in\mathbb{N},\;u_{n}=\dfrac1{\sqrt{29}}(-x_{1}^{n+1}-x_{2}^{n+1}+x_{3}^{n+1}+x_{4}^{n+1})}
  5. 4. Montrer que, sur un intervalle à préciser: {\displaystyle\sum_{n=0}^{+\infty}u_{n}x^n=\dfrac{1-x^2}{P(x)}}


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 8

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5, Ep6, Ep7.
Soit A une matrice \mu-magique d’ordre n, avec \mu\gt0.
On sait que {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}{\alpha_{k}>0}, {\displaystyle\sum_{k=1}^{m}\alpha_{k}=\mu}, les {P_{k}} des matrices de permutation.
On sait aussi qu’il y a une solution avec {m\lt (n-1)^{2}+1},

On demande ici d’écrire une fonction decomp d’argument A, et renvoyant la liste {L=[[\alpha_{1},P_{1}],[\alpha_{2},P_{2}],\ldots,[\alpha_{m},P_{m}]]} au sens de l’écriture précédente.

Si {A} est bistochastique, on obtient ainsi une représentation de {A} comme barycentre (à coefficients strictement positifs) de matrices de permutation.

On vérifiera emipiriquement que l’algorithme décompose {A} en une combinaison linéaire d’au plus {(n-1)^{2}+1} matrices de permutation (il est donc plutôt optimal).

Pour vérifier le bon fonctionnement de la fonction decomp, on écrira une fonction recomp reconstituant la matrice {A} à partir de sa décomposition.


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 7

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5, Ep6.
Écrire une fonction Python traverse d’argument une matrice carrée {A=(a_{i,j})} et renvoyant la première permutation {\sigma} (au sens lexicographique) telle que les {a_{\sigma(j),j}} soient non nuls.
Dire que {\sigma} existe, c’est dire que {A} est traversable.
Si ce n’est pas le cas, traverse renverra la liste {[-1,-1,\ldots,-1]} de longueur {n}.

Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 6

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4, Ep5.
Soit {A} une matrice positive magique de somme {\mu>0}.
On sait que {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}, (avec {\alpha_k>0}, {\displaystyle\sum_{k=1}^{m}\alpha_k=\mu}, les {P_k} matrices de permutations).
On va montrer que {m} peut être rendu inférieur ou égal à {(n\!-\!1)^2\!+\!1}.

Pour cela, on suppose {m>(n\!-\!1)^{2}\!+\!1}: l’objectif est de réduire le nombre de matrices {P_{k}} (tout en gardant les propriétés: les {\alpha_{k}>0} et de somme {\mu}).

  1. 1. Montrer que les matrices 0-magiques forment un EV de dimension {(n-1)^{2}}.
  2. 2. Montrer qu’il existe des \beta_{k} non tous nuls, tels que : {\displaystyle\sum_{k=1}^{m}\beta_{k}P_{k}=0\quad\text{et}\quad\displaystyle\sum_{k=1}^{m}\beta_{k}=0}Indication: considérer les matrices {P_{k}-P_{1}}, avec {2\le k\le m}.

  3. 3. Justifier la possibilité de choisir {j\in\{1,\ldots,m\}} tel que : {\dfrac{\alpha_{j}}{\beta_{j}}=\min\biggl\{\dfrac{\alpha_{k}}{\beta_{k}},\;1\le k\le m,\;\beta_{k}>0\biggr\}}Quitte à tout renuméroter, on suppose {j=m}.
  4. 4. Montrer que {A=\displaystyle\sum_{k=1}^{m-1}\delta_{k}P_{k}}, où {\delta_{k}=\alpha_{k}-\alpha_{m}\dfrac{\beta_{k}}{\beta_{m}}}.

    Indiquer le signe des {\delta_{k}}, et leur somme.

    Énoncer le résultat obtenu (en en donner la version bistochastique).


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 5

Pour les notations et les résultats précédents : Ep1, Ep2, Ep3, Ep4.
Soit {A} une matrice positive magique de somme {\mu>0}.
On sait qu’il existe {\sigma_{1}} dans {\mathcal{S}_{n}} tel que {\sigma_{1}(A)=\displaystyle\prod_{j=1}^{n}a_{\sigma_1(j),j}}\gt 0.
  1. On note P_{1}=P_{\sigma_{1}}. Soit \alpha_{1}=\min\{a_{\sigma_{1}(j),j},\;1\le j\le n.
    Montrer que A_{1}=A-\alpha_{1} P_{1} est positive, magique de somme \mu'\in[0,\mu[.
    Observer que, par rapport à A elle a au moins un coefficient nul supplémentaire.
  2. Montrer qu’on peut écrire {A=\displaystyle\sum_{k=1}^{m}\alpha_{k}P_{k}}, avec des \alpha_{k}>0 tels que {\displaystyle\sum_{k=1}^{m}\alpha_{k}=\mu}, les P_{k} étant des matrices de permutation.
    Cas particulier: si A est bistochastique (\mu=1), cela signifie qu’elle peut s’écrire comme barycentre à coefficients strictement positifs de matrices de permutation.


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 4

On reprend les définitions et les notations de l’épisode 1.
Pour {A\in\mathcal{M}_{n}(\mathbb{R})}, et pour {\sigma\in\mathcal{S}_{n}}, on note {\sigma(A)=\displaystyle\prod_{j=1}^{n}a_{\sigma(j),j}}.
On dit que {A} est traversable s’il existe {\sigma\in\mathcal{S}_{n}} telle que {\sigma(A)\ne0}.
On souhaite montrer l’équivalence des propositions:
{(\star)\quad} {A} n’est pas traversable
{(\star\star)} {A} possède une sous-matrice nulle de taille {r\times s}, où {r+s=n+1}

  1. 1. Montrer que permuter les lignes ou colonnes ne modifie pas la traversabilité.
  2. 2. Prouver que {(\star\star)} implique {(\star)}.
  3. 3. Établir que {(\star)} implique {(\star\star)} par récurrence sur {n}.
  4. 4. En déduire que toute matrice magique de somme {\mu>0} (et en particulier toute matrice bistochastique) est traversable (raisonner par l’absurde).


Cliquer ici pour voir le corrigé

Matrices bistochastiques, épisode 3

On reprend les définitions et les notations de l’épisode 1.
On prouve ici la réciproque du résultat final de l’épisode 2: on va donc montrer que tout élément extrémal de {\mathcal{B}_{n}(\mathbb{R})} est une matrice de permutation P_{\sigma}.
Pour cela, soit {C=(c_{i,j})} bistochastique sans être une matrice de permutation.
On doit montrer qu’il existe {A,B} bistochastiques distinctes telles que {C\in\,]A\,;B[}.

  1. 1. Montrer qu’il existe deux suites (i_{k})_{k\ge0} et (j_{k})_{k\ge0} de {[[0,n\!-\!1]]} telles que :{\forall\, k\in\mathbb{N},\begin{cases}i_{k}\ne j_{k+1}\\j_{k}\ne j_{k+1}\end{cases}\text{ et }\begin{cases}0\lt c_{i_{k},j_{k}}\lt 1\\0\lt c_{i_{k},j_{k+1}}\lt 1\\0\lt c_{i_{k+1},j_{k+1}}\lt 1\end{cases}}Indication: choisir {(i_{0},j_{0})}, puis {j_{1}} puis {i_{1}} et repartir de {(i_{1},j_{1})}
  2. 2. La suite {(j_{k})_{k\ge0}} n’étant pas injective, certaines valeurs de {j_{k}} se répètent.
    Quitte à renuméroter, on peut dire qu’il existe {m\ge1} tel que {j_{m+1}=j_{0}}.
    On définit alors la matrice {D=(d_{i,j})} par : {\forall\, k\in[[ 0,m]],\;\begin{cases}d_{i_{k},j_{k}}=1\\d_{i_{k},j_{k+1}}=-1\end{cases}\quad\text{et}\quad d_{i,j}=0\text{ sinon}}Montrer que pour {\lambda>0} assez petit, {\begin{cases}A=C-\lambda D\\B=C+\lambda D\end{cases}} sont bistochastiques.
    Conclure.


Cliquer ici pour voir le corrigé