\documentclass[12pt,a4paper,twoside]{article}

\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen
%\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
%\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{Tas de sable (ENS Lyon Math-info 99)}
   \texte
    On appelle \emph{configuration} une matrice $M$ de dimensions
    $p\times q$ à coefficients
    entiers naturels. Si un élément $m_{i,j}$ est $\geq4$, on peut lui
    retrancher $4$ et ajouter $1$ à chacun de ses voisins immédiats
    (les éléments $m_{i-1,j}$ si $i\neq1$, $m_{i+1,j}$ si $i\neq p$,
    $m_{i,j-1}$ si $j\neq1$ et $m_{i,j+1}$ si $j\neq q$).
    Si $M'$ est le résultat de cette transformation, on
    écrit $M\rightarrow M'$ ou, plus précisément,
    $M\xrightarrow{i,j}M'$.
   \question
    Montrer que la relation $\rightarrow$ termine; autrement dit, quelle que
    soit la configuration de départ et la suite de transformations
    effectuées, on arrive à une configuration bloquée dans laquelle
    aucun élément n'est $\geq4$.
   \question
    Peut-on avoir deux configurations bloquées distinctes à partir d'une
    même configuration de départ $M$?
   \question
    Mêmes questions avec des configurations sans bord (matrices
    << infinies >>).
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
   \cquestion (D'après Bruno Petazzoni)
    Pour une configuration donnée, on note
    $$h(M)=\sum_{i,j}m_{i,j}
     \text{ et }w(M)=\sum_{i,j}(i+j-2)^2m_{i,j}\text{.}$$
    Pour une transformation $M\rightarrow M'$ sur un site $(i,j)$ non
    périphérique ($1<i<p$, $1<j<q$), on a
    $$h(M')=h(M)\text{ et }w(M')-w(M)=2(i+j-3)^2+2(i+j-1)^2-4(i+j-2)^2=4\text{.}$$
    Donc, si $M^{(0)}\rightarrow\dotsb\rightarrow M^{(n)}$ est une suite de transformations
    non périphériques, alors
    $$4n\leq w(M^{(n)})=\sum_{i,j}(i+j-2)^2m_{i,j}^{(n)}\leq
     (p+q-2)^2h(M^{(n)})=(p+q-2)^2h(M^{(0)})\text{.}$$
    Partant de $M$ une suite de
    ${\displaystyle\left\lfloor\frac{1}{4}(p+q-2)^2h(M)\right\rfloor+1}$
    transformations consécutives contient au moins une transformation
    périphérique qui diminue d'au moins $1$ la quantité $h(M)$. Au total,
    une telle suite issue de $M$ contient donc au plus
    ${\displaystyle h(M)\left(\left\lfloor\frac{1}{4}(p+q-2)^2h(M)
     \right\rfloor+1\right)}$
    transformations.
   \cquestion
    Non. Comme $\rightarrow$ termine, on peut démontrer ce résultat en
    supposant qu'il est vrai pour toutes les configurations $M'$
    telles que $M\rightarrow M'$: Soient $M\xrightarrow{*}M_1$
    et $M\xrightarrow{*}M_2$ deux
    suite de transformations avec $M_1$ et $M_2$ bloquées.
    Si $M$ n'est pas bloquée, il existe un couple $(i,j)$
    tel que $m_{i,j}\geq4$. Pour $k=1,2$,  l'une  au moins des
    transformations $M\xrightarrow{*}M_k$ est la transformation $(i,j)$.
    Or, comme une transformation équivaut à ajouter à la matrice
    une autre matrice (une transformation est une translation),
    les transformations commutent et on a donc
    $M\xrightarrow{i,j}M'\xrightarrow{*}M_k$. En appliquant l'hypothèse
    à $M'$, on obtient $M_1=M_2$.
   \cquestion
    Les résultats précédents sont encore valables.
    \par
    Montrons d'abord la terminaison dans le cas où la configuration initiale
    est un carré d'éléments tous égaux. Plus précisément,
    $m_{i,j}=t$ pour $|i|\leq p$ et $|j|\leq p$  et $m_{i,j}=0$
    pour les autres $(i,j)\in\Z\times\Z$; où $p,t\in\N^*$.
    Soit $M=M^{(0)}\rightarrow M^{(1)}\rightarrow\dotsb$ est une suite infinie
    de transformations.
    Pour tout entier $N$, d'après la question 1, il
    existe un rang $K$ pour lequel les éléments $\geq4$
    de $M^{(K)}$ sont en dehors du carré $|i|,|j|\leq N$. Mais on voit par
    récurrence que, pour tout $k$, d'une part il existe au moins un élément
    non nul de $M^{(k)}$ dans chacun des quatre quadrants du plan, et
    d'autre part les éléments non nuls de $M^{(k)}$ forment un ensemble
    connexe (en un sens évident). Ainsi, si $m_{i_0,j_0}^{(K)}\geq4$
    et si $m_{i_1,j_1}^{(K)}\neq0$ où $(i_1,j_1)$ se trouve dans le quadrant
    oppposé à celui de $(i_0,j_0)$, il existe un chemin de $(i_0,j_0)$
    à $(i_1,j_1)$ formé d'éléments non nuls de $M^{(K)}$ et, par conséquent,
    $h(M)=h(M^{(K)})\geq N$: il suffit donc de choisir $N>h(M)$ pour obtenir
    une contradiction.
    \par
    Dans le cas d'une configuration $M$ quelconque, il suffit de 
    considérer une configuration du type précédent $\geq$ à $M$.
    \par
    Le fait qu'une configuration n'a qu'un seul réduit se déduit alors
    du cas borné.    
\end{parenthese}\end{document}
