%%%% format LATEX 2.09

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%   Enonc\'{e} de la premi\`{e}re \'{e}preuve de math\'{e}matiques
%%%%%%%%%%%%%%%%%            Agr\'{e}gation interne 2004
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%                   MACROS
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagestyle{plain}

\parindent=0pt
\frenchspacing

\textheight=230mm

\textwidth=165mm
\topmargin  -10mm
\footskip 14mm
\headheight  6mm
\headsep 7.5mm
\oddsidemargin -5mm
\evensidemargin -5mm
\voffset 0mm
\hoffset 4mm

\def\longtetep{165mm}
\def\longtetei{165mm}

\parskip 3pt
\renewcommand{\footnoterule}{\vskip 3pt \hbox to 2.35cm{\hrulefill} \vskip 3pt}

\font\twelvesym=msbm10 at 12pt
\font\tensym=msbm10
\font\sevensym=msbm7
\font\fivesym=msbm5

\font\twelvegoth=eufb10 at 12pt
\font\tengoth=eufb10
\font\sevengoth=eufb7
\font\fivegoth=eufb5

\newfam\gothfam
\textfont\gothfam=\tengoth
\scriptfont\gothfam=\sevengoth
\scriptscriptfont\gothfam=\fivegoth
\def\goth{\fam\gothfam\tengoth}


\def\C{{\bf C}}
\def\N{{\bf N}}
\def\Q{{\bf Q}}
\def\R{{\bf R}}
\def\Z{{\bf Z}}

\def\d{\displaystyle}


\def\SG{{\goth S}}
\def\IG{{\goth I}}

%%%%%%%%%%%%%%%%%%%%%

\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\vt{\vrule height 0mm depth 2mm width 0mm}
\def\vtt{\vrule height 0mm depth 3mm width 0mm}
\def\vttt{\vrule height 0mm depth 13mm width 0mm}
\def\vtr#1{\vrule height 0mm depth #1mm width 0mm}
\def\wtr#1#2{\vrule height #2mm depth #1mm width 0mm}

% ****************************************************************************
% ****************************************************************************



% Fonctions usuelles:

\def\sh{\mathop{\rm sh}\nolimits}
\def\exp{\mathop{\rm exp}\nolimits}
\def\ch{\mathop{\rm ch}\nolimits}
\def\th{\mathop{\rm th}\nolimits}
\def\cotan{\mathop{\rm cotan}\nolimits}
\def\arctan{\mathop{\rm Arctan}\nolimits}
\def\argth{\mathop{\rm Argth}\nolimits}
\def\argsh{\mathop{\rm Argsh}\nolimits}
\def\argch{\mathop{\rm Argch}\nolimits}
\def\arcsin{\mathop{\rm Arcsin}\nolimits}
\def\arccos{\mathop{\rm Arccos}\nolimits}
\def\build#1_#2^#3{\mathrel{\mathop{\kern 0pt#1}\limits_{#2}^{#3}}}







% Convergence

\def\tend#1#2#3#4{\build\hbox to #1mm{\rightarrowfill}_{#3\rightarrow #4}^{}#2}
\def\tendbis#1#2#3#4#5{\build\hbox to #1mm{\rightarrowfill}_{#3\rightarrow #4}^{#5}}



%Fleches, applications et diagrammes

        %fleche horizontale vers la droite (#1 longueur de la fl\^{e}che, #2 au dessus
\def\dfl#1#2#3{\smash{\mathop{\hbox to #1mm{\rightarrowfill}}
\limits^{\scriptstyle#2}_{\scriptstyle#3}}}

        %fleche horizontale vers la gauche (#1 longueur de la fl\^{e}che, #2 au dessus
\def\gfl#1#2#3{\smash{\mathop{\hbox to #1mm{\leftarrowfill}}
\limits^{\scriptstyle#2}_{\scriptstyle#3}}}


        %fleche verticale vers le bas (#1 longueur de la fl\^{e}che, #2 \`{a} gauche et #3
\def\bfl#1#2#3{\llap{$\scriptstyle #2$}\left\downarrow
\vbox to #1mm{}\right.\rlap{$\scriptstyle #3$}}

        %fleche verticale vers le haut (#1 longueur de la fl\^{e}che, #2 \`{a} gauche et #
\def\hfl#1#2#3{\llap{$\scriptstyle #2$}\left\uparrow
\vbox to #1mm{}\right.\rlap{$\scriptstyle #3$}}



\def\diagram#1{\def\normalbaselines{\baselineskip=0pt
\lineskip=10pt\lineskiplimit=1pt}   \matrix{#1}}


% application f A B a b donne f : A  -> B
%                                a |-> b

\def\application#1#2#3#4#5{\begin{tabular}[t]{cccc}
                                              $\d #1\,:$&$\d #2$&$\d \longrightarrow$&$\d #3$\\
                                                        &$\d #4$&$\d \longmapsto$&$\d #5$\\
                           \end{tabular}}

        % applicationbis A B a b donne   A  -> B
        %                                a |-> b


\def\applicationbis#1#2#3#4{\begin{tabular}[t]{ccc}
                                              $\d #1$&$\d \longrightarrow$&$\d #2$\\
                                              $\d #3$&$\d \longmapsto$&$\d #4$\\
                           \end{tabular}}



%Expression en rm dans un $  $

\def\Ker#1{{\rm Ker}\left(#1\right)}
\def\Im#1{{\rm Im}\,#1}
\def\dim#1{{\rm dim}\left(#1\right)}
\def\rg#1{{\rm rg}\left(#1\right)}
\def\Mat#1{{\rm Mat}\left(#1\right)}
\def\Vect#1{{\rm Vect}\left(#1\right)}
\def\Tr#1{{\rm Tr}\left(#1\right)}
\def\et{\ {\rm et}\ }
\def\ou{\ {\rm ou}\ }
\def\Card{\ {\rm Card}\ }

% Ecrire en caligraphique

\def\ca#1{{\cal #1}}

% Num\'{e}ro de question (d\'{e}cal\'{e}e dans la marge)

\def\ques#1{\vskip .5cm \hskip -1.6cm \hbox to 1.58cm{\bf #1 \hfill}}


% Titre (corrig\'{e}s ou \'{e}nonc\'{e}s)

\def\titre#1{
\begin{center}
{\huge \bf #1}
\end{center}
\vskip 1cm
\thispagestyle{empty}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%       D\'{e}but de l'\'{e}nonc\'{e}
%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}
\thispagestyle{empty}

{\huge
\hskip 10cm \fbox{\ SESSION DE 2004\ }

\vskip 1cm
{\bf concours interne

de recrutement de professeurs agr\'{e}g\'{e}s

et concours d'acc\`{e}s \`{a} l'\'{e}chelle de r\'{e}mun\'{e}ration}

\vskip 1cm
\hskip 10cm \fbox{section{\,}: math\'{e}matiques}

\vskip 1cm
premi\`{e}re \'{e}preuve de math\'{e}matiques

\vskip 1cm
\hskip 10cm \fbox{dur\'{e}e{\,}: 6 heures}}

{\large
\vskip 2cm
\hskip .5cm Calculatrice de poche, y compris programmable, alphanum\'{e}rique
ou \`{a} \'{e}cran graphique, \`{a} fonctionnement autonome, non imprimante, autoris\'{e}e
conform\'{e}ment \`{a} la circulaire n$^{\circ}$99-186 du 16 novembre 1999.

\hskip .5cm L'usage de tout ouvrage de r\'{e}f\'{e}rence, de tout dictionnaire et de
tout mat\'{e}riel \'{e}lectronique est rigoureusement interdit.}

\vfill
\eject
\subsection*{
\begin{center}
{\bf D\'{e}finitions et notations}
\end{center}}

Dans ce texte, $\C$ est identifi\'{e} \`{a} $\R^2$. Pour $x$ dans $\C$, on note $\Im x$ sa partie imaginaire.

\vskip 2mm
Pour tout $x$ dans $\C$ et tout r\'{e}el positif $r$, on note $\overline D(x, r)=\{y \in \C,\  |x-y|\leq r\}$ le disque ferm\'{e} de $\C$, de centre $x$ et de rayon $r$.

\vskip 2mm
Si $M$ est une matrice carr\'{e}e, ${\rm tr}(M)$ d\'{e}signe sa trace.

\vskip 2mm
Si $A$, $B$ et $C$ sont des parties d'un ensemble $E$, on convient d'\'{e}crire $C = A\amalg B$ lorsque $C = A\cup B$ et $A\cap B = \emptyset$.

\vskip 2mm
Pour $n=1$ ou $2$, on note $\IG_n$ le groupe des isom\'{e}tries {\sl affines} euclidiennes de $\R^n$. On note $\IG_n^+$ le sous-groupe
des isom\'{e}tries affines euclidiennes directes.

\vskip 2mm
Lorsque $E$ est un ensemble, on note $(\SG_E,\circ)$ le groupe des bijections de $E$ sur lui-m\^{e}me. $\IG_n$ est un
sous-groupe de $(\SG_{\R^n},\circ)$.

\vskip 2mm
Soit $E$ un ensemble non vide et $G$ un sous-groupe de $\SG_E${\,}; on convient de dire qu'une partie {\sl non
vide} $\ca D$ de $E$ est $G$-d\'{e}doublable s'il existe des parties $\ca D_1$ et $\ca D_2$ de $\ca D$ telles que
\begin{itemize}
  \item[(i)]$\ca D=\ca D_1\amalg \ca D_2${\,};
  \item[(ii)]il existe $g_l$ et $g_2$ dans $G$ tels que $g_l(\ca D)=\ca D_1$ et $g_2(\ca
  D)=\ca D_2$.
\end{itemize}
Autrement dit, et de fa\c{c}on imag\'{e}e, $\ca D$ est $G$-d\'{e}doublable lorsque l'on peut la d\'{e}couper en deux parties, chacune
\'{e}tant superposable \`{a} $\ca D$ sous l'action de $G$.


\vskip .5cm
\subsection*{
\begin{center}
{\bf Objectifs du probl\`{e}me}
\end{center}}


Les trois premi\`{e}res parties \'{e}tudient l'existence \'{e}ventuelle d'une partie de $\C$ (resp. de $\R$) $\IG_2$-d\'{e}doublable
(resp. $\IG_1$-d\'{e}doublable). Ces trois parties sont ind\'{e}pendantes.

\vskip 2mm
La partie {\bf IV} propose l'\'{e}tude alg\'{e}brique d'un sous-groupe de $SL_2(\Z)$ engendr\'{e} par deux matrices. Elle pr\'{e}pare aussi
la partie {\bf V} o\`{u} l'on g\'{e}n\'{e}ralise le concept d'ensemble d\'{e}doublable en celui d'ensemble paradoxal sous l'action d'un groupe.

\vskip 2mm
La partie {\bf V} est d\'{e}volue \`{a} l'\'{e}tude de deux ensembles qui se r\'{e}v\`{e}lent paradoxaux sous l'action du groupe \'{e}tudi\'{e} dans la partie
{\bf IV}.

\vskip .5cm
\subsection*{
\begin{center}
{\bf Partie I : Parties d\'{e}doublables de ${\bf C=R}^{\bf 2}$}
\end{center}}


\subsubsection*{A. \'{E}tude d'un premier exemple}

On consid\`{e}re le disque ferm\'{e} $\overline D = \{x \in \C, |x| \leq  1\}$.

\begin{itemize}
  \item[1.]On suppose l'existence de parties $A$ et $B$ de $\overline D$ telles que
$$\overline D=A\amalg B\,;\quad 0\in A\,;\quad \exists \tau\in \IG_2,\
\tau(A)=B.$$
\begin{itemize}
  \item[(a)]Montrer que si deux points $x$ et $y$ de $\overline D$ v\'{e}rifient $|x-y|=2$ alors leur
milieu est $0$.
  \item[(b)]Montrer que pour $w$ dans $\overline D$, la condition $|w-\tau(0)|>1$
entra\^{\i}ne $w\in A$ (on pourra raisonner par contraposition).
  \item[(c)]En d\'{e}duire l'existence d'un diam\`{e}tre $[u, v]$ de $\overline D$ \`{a} extr\'{e}mit\'{e}s $u,v$ dans $A$.
  \item[(d)]Relever une contradiction.
\end{itemize}
  \item[2.]En d\'{e}duire que le disque ferm\'{e} $\overline D$ de $\C$ n'est pas $\IG_2$-d\'{e}doublable.

\end{itemize}

\subsubsection*{B. Cas des parties born\'{e}es}
Plus g\'{e}n\'{e}ralement on se propose de montrer que
\begin{center}
\fbox{\hskip .2cm Aucune partie {\sl born\'{e}e} de $\C$ n'est $\IG_2$-d\'{e}doublable.\wtr 35\hskip .2cm}
\end{center}

La preuve qui suit est due \`{a} H. HABWIGER et H. DEBRUNNER [1964].

\subsubsection*{B 1. Disque enveloppant minimal}
Soit $\ca B$ une partie non vide et {\sl born\'{e}e} de $\C$. Pour $r$ dans $\R_+$ on pose
$\ca C_r=\{x \in \C,\ \ca B\subset \overline D(x,r)\}$ et $R=\{r\in \R_+,\ \ca
C_r\not= \emptyset\}$.

\begin{itemize}
  \item[1.]
\begin{itemize}
  \item[(a)]Montrer que l'ensemble $R$ admet une borne inf\'{e}rieure{\,}; on note $\rho$ cette
  borne inf\'{e}rieure.
  \item[(b)]\'{E}tablir l'\'{e}nonc\'{e} suivant :
$$\forall\,n \in \N\*,\ \exists x_n\in \C,\ \ca B\subset \overline
D\left(x_n,\rho+{1\over n}\right).$$
\end{itemize}
  \item[2.]
\begin{itemize}
  \item[(a)]Montrer que la suite $(x_n)_{n\geq 1}$ admet une sous-suite convergente.
  \item[(b)]En d\'{e}duire l'existence d'un nombre complexe a tel que $\ca B\subset \overline
  D(a,\rho)$.
  \item[(c)]D\'{e}montrer l'unicit\'{e} d'un tel a.
\end{itemize}
\end{itemize}
Autrement dit 1a partie $\ca B$ est contenue dans un {\sl unique} disque ferm\'{e} de rayon {\sl minimum}.

\subsubsection*{B 2. Conclusion}
\begin{itemize}
  \item[1.]Dresser sans d\'{e}monstration la liste des diff\'{e}rents {\sl types} de transformations
g\'{e}om\'{e}triques qui constituent le groupe $\IG_2$.
  \item[2.]On suppose l'existence d'une partie {\sl born\'{e}e} et non vide, $\ca B$, de $\C$, qui est $\IG_2$-d\'{e}doublable.
  On adopte alors les notations suivantes{\,}:
  \begin{center}
  $\ca B=\ca B_1\amalg\ca B_2$, avec $\tau_1$ et $\tau_2$ dans $\IG_2$ v\'{e}rifiant $\ca B_i=\tau_i(\ca B)$ pour $i=1,2$.
  \end{center}
  On remarquera que, pour $i=1,2$, $\tau_i(\ca B)$ est {\sl strictement} contenu dans $\ca B$.
\begin{itemize}
  \item[(a)]Montrer que les isom\'{e}tries $\tau_i$ ne peuvent \^{e}tre que des rotations diff\'{e}rentes de l'identit\'{e}.
  On note $\omega_i$ le centre de $\tau_i$ pour $i=1,2$.
  \item[(b)]En consid\'{e}rant l'unique disque $\overline D(a, \rho)$ de rayon minimum
  contenant$\ca B$ [voir la section {\bf B1}], montrer que $\omega_1=a=\omega_2$.
  \item[(c)] Montrer que $\tau_1(\tau_2(\ca B))\subset \ca B_1\cap \ca B_2$, relever une contradiction, puis conclure.
\end{itemize}
\end{itemize}
\vfill
\eject

\subsection*{
\begin{center}
Partie II: Le paradoxe de SIERPINSKI-MAZURKIEWICZ [1914]
\end{center}}
\begin{center}
\fbox{\hskip .2cm On se propose de d\'{e}crire une partie {\sl non born\'{e}e} de $\C$ et $\IG_2$-d\'{e}doublable.\wtr 35\hskip .2cm}
\end{center}

Un nombre complexe $\xi$ est dit {\sl transcendant} si 1e seul polyn\^{o}me \`{a} coefficients rationnels dont il est racine est
le polyn\^{o}me nul. On utilisera librement l'existence d'un nombre transcendant $u$ de module \'{e}gal \`{a} 1.

\vskip 2mm
On note $\ca P_{\N}$ l'ensemble des polyn\^{o}mes \`{a} coefficients dans $\N$, et l'on pose
$$\ca D=\{P(u),\ P\in \ca P_{\N}\}.$$

\vskip 2mm
Soient $t$ et $r$ les transformations du plan complexe d\'{e}finies pour $x$ dans $\C$ par $t(x)=x+1$ et $r(x)=ux$
respectivement.

\begin{itemize}
  \item[1.]En exploitant le caract\`{e}re transcendant de $u$, \'{e}tablir que $t(\ca D)\cap r(\ca D)=\emptyset$.
  \item[2.]Montrer que l'ensemble $\ca D$ est $\IG_2$-d\'{e}doublable (on pourra commencer par
  montrer que tout polyn\^{o}me $P$ de $\ca P_{\N}$ peut \^{e}tre \'{e}crit sous l'une des deux
  formes suivantes{\,}: $P=R+1$ ou $P=XS$ avec $R$ et $S$ dans $\ca P_{\N}$).
\end{itemize}

\subsection*{
\begin{center}
Partie III : Parties d\'{e}doublables de $\R$
\end{center}}

On se propose d'\'{e}tablir le r\'{e}sultat suivant [W. SIERPINSKI]{\,}:
\begin{center}
\fbox{\hskip .2cm Aucune partie de $\R$ n'est $\IG_1$-d\'{e}doublable.\wtr 35\hskip .2cm}
\end{center}

Les sections {\bf A}, {\bf B} et {\bf C} sont d\'{e}volues \`{a} la preuve de ce r\'{e}sultat.

\subsubsection*{A. La croissance d'un groupe}
Soit $G$ un groupe de loi interne not\'{e}e multiplicativement et d'\'{e}l\'{e}ment neutre not\'{e} $1$. Soit $S$ une partie finie de
$G\setminus \{1\}$, suppos\'{e}e sym\'{e}trique au sens suivant{\,}: $\forall\, x \in S,\  x^{-1}\in S$.

Le sous-groupe de $G$ engendr\'{e} par $S$ est alors l'ensemble des produits finis d'\'{e}l\'{e}ments de $S$
(on convient que le produit vide vaut 1){\,}; on le note $<\, S\, >$.

La longueur relativement \`{a} S, $\ell_S(x)$, d'un \'{e}l\'{e}ment $x$ de $<\,S\,>$ est d\'{e}finie de la mani\`{e}re suivante{\,}:
$\ell_S(1)=0$, et, pour $x\not=1$, $\ell_S(x)$ est le plus petit entier $p$ tel que l'on puisse \'{e}crire
$x=s_ls_2\dots s_p$ avec $s_k$ dans $S$ pour $1\leq k\leq p$.


Pour $n$ entier strictement positif on pose $B_S(n)=\{x\in <\,S\,>,\ \ell_S(x)\leq n\}$, $\gamma_S(x)=\Card B_S(n)$ [le cardinal
de $B_S(n))$] et $c_s(n)=(\gamma_S(n))^{1\over n}$.


\begin{itemize}
  \item[1.]\'{E}tablir l'in\'{e}galit\'{e}{\,}:
  $$\forall\,p,q\geq 1,\ \gamma_S(p+q)\leq \gamma_S(p)\gamma_S(q).$$
  \item[2.]Pour $n$ dans $\N^*$, on pose $u_n=\ln \gamma_S(n)$ et $v_n=\d{u_n\over
  n}$.
\begin{itemize}
  \item[(a)]Soient $n$ et $p$ dans $\N^*${\,}; en effectuant la division euclidienne de $n$ par $p$,
  \'{e}tablir la majoration $v_n \leq v_p+\d{p\over n}\,v_1$.
  \item[(b)]En d\'{e}duire que la suite $(v_n)_{n\geq 1}$ converge vers $\d v =\inf_{n\geq 1}
  v_n$.
\end{itemize}
  \item[3.]D\'{e}montrer la convergence de la suite $(c_S(n))_{n\geq 1}$ vers une limite $C_S$, et
  v\'{e}rifier l'in\'{e}galit\'{e} $C_S\geq 1$.
\end{itemize}

\vskip 2mm
Le groupe $G$ est dit \`{a} {\sl croissance sous-exponentielle} lorsque, pour chaque $S$, partie finie sym\'{e}trique de
$G\setminus\{1\}$, on a $C_S= 1$.

Il est dit \`{a} croissance {\sl exponentielle} dans le cas contraire.

\begin{itemize}
  \item[4.]Que dire de la croissance de $G$ s'il contient un sous-groupe \`{a} croissance exponentielle{\,}?
  \item[5.]Montrer qu'un groupe ab\'{e}lien est toujours \`{a} croissance sous-exponentielle.
\end{itemize}

\subsubsection*{B. La croissance du groupe $\IG_1$}
On consid\`{e}re une partie $S$ de $\IG_1\setminus \{Id\}$, finie et sym\'{e}trique.
\begin{itemize}
  \item[1.]Montrer que $\IG_1$ est form\'{e} des transformations $x\mapsto u+v$, avec $u=\pm 1$ et $v\in \R$.
  \item[2.]Soient $\varepsilon =\pm Id$ et $s$ dans $S${\,}; prouver l'existence et l'unicit\'{e} de
  $t$ dans $\IG_1^+$ et de $\varepsilon'=\pm Id$ tels que $\varepsilon\circ s=t\circ \varepsilon'$.
\end{itemize}

On note $T_0$ la partie {\sl finie} de $\IG_1^+$ obtenue en collectant les divers \'{e}l\'{e}ments $t$ lorsque le couple
$(\varepsilon, s)$ d\'{e}crit l'ensemble $\{\pm Id\}\times S$. On pose alors
$$T=\{\tau\in \IG_1^+,\ \tau \in T_0 \ou \tau^{-1}\in T_0\}.$$
puis on consid\`{e}re les parties $B_S(n)$ de $\IG_1$  et $B_T(n)$ de $\IG_1^+$, pour $n$ quelconque dans $\N^*$.

\begin{itemize}
  \item[3.]D\'{e}montrer que
$$\forall\,\tau\in B_S(n),\ \exists\, (\sigma,\varepsilon)\in B_T(n)\times \{\pm Id\},\
\tau=\sigma\circ \varepsilon.$$
  \item[4.]En d\'{e}duire que \fbox{\ le groupe $\IG_1$ est \`{a} croissance
  sous-exponentielle.\ \wtr 11}
\end{itemize}

\subsubsection*{C. Conclusion}
On suppose ici l'existence d'une partie $\ca D$ de $\R$, non vide et $\IG_1$-d\'{e}doublable.

On adopte alors les notations{\,}:

$\ca D=\ca D_1\amalg\ca D_2$, avec $\tau_1,\tau_2$ dans $\IG_1$ tels que $\tau_i(\ca D)=\ca D_i$
($i=1,2$).

Pour $n$ dans $\N^*$ et $s=(s_1,s_2,\dots,s_n)$ dans $\{\tau_1,\tau_2\}^n$ on pose $\gamma_s = s_1\circ s_2\circ \dots
\circ s_n$.

\begin{itemize}
  \item[1.]Montrer que, pour tout couple $(s,s')$ de $\{\tau_1,\tau_2\}^n$ tel que $s\not=s'$, on a
$\gamma_s(\ca D)\cap \gamma_{s'}(\ca D)=\emptyset$.
  \item[2.]On pose $S=\{\tau_1,\tau_1^{-1},\tau_2,\tau_2^{-1}\}$. D\'{e}duire de la
question pr\'{e}c\'{e}dente une minoration de la constante $C_S$ pour le groupe $\IG_1$.
  \item[3.]Relever une contradiction, et en d\'{e}duire qu'aucune partie de $\R$ n'est $\IG_1$-d\'{e}doublable.
\end{itemize}

\subsubsection*{D. La croissance du groupe $\IG_2$}
La croissance du groupe $\IG_2$ est-elle exponentielle ou bien sous-exponentielle{\,}? (On pourra s'inspirer de la section {\bf III.C}).

\subsection*{
\begin{center}
Partie IV : Un groupe « paradoxal »
\end{center}}
Dans cette partie on se propose d'\'{e}tudier un groupe $\Gamma$ dont les propri\'{e}t\'{e}s seront exploit\'{e}es dans la partie {\bf V}.

Soit $SL_2(\Z)$ 1e groupe des matrices carr\'{e}es d'ordre 2, \`{a} coefficients entiers et de d\'{e}terminant \'{e}gal \`{a} 1{\,};
son \'{e}l\'{e}ment neutre est $I =\pmatrix{1&0\cr 0&1\cr}$. On note $E$ l'espace des matrices colonnes r\'{e}elles
$\pmatrix{x\cr y\cr}$.

On s'int\'{e}resse au sous-groupe $\Gamma$ de $SL_2(\Z)$ engendr\'{e} par les matrices $A
=\pmatrix{1&2\cr 0&1\cr}$ et $B=\pmatrix{1&0\cr 2&1\cr}$.

\subsubsection*{A. Calculs pr\'{e}liminaires}

\begin{itemize}
  \item[1.]Calculer $A^k$ et $B^k$ pour $k$ dans $\Z$.
  \item[2.]On pose{\,}:
  $$\Gamma_1=\{A^k,\ k\in \Z\},\ \Gamma_2=\{B^k,\ k\in \Z\},\
  E_1=\left\{\pmatrix{x\cr y\cr}\in E,\ |x|>|y|\right\},\   E_2=\left\{\pmatrix{x\cr y\cr}\in E,\
  |x|<|y|\right\}$$
  D\'{e}montrer les \'{e}nonc\'{e}s suivants{\,}:

  (1) \hskip 3cm $\forall\,M\in \Gamma_1\setminus\{I\},\ \forall\,X_2\in
  E_2,\ MX_2\in E_1$

  (2) \hskip 3cm $\forall\,P\in \Gamma_2\setminus\{I\},\ \forall\,X_1\in
  E_1,\ PX_1\in E_2$
\end{itemize}

\subsubsection*{B. Les \'{e}l\'{e}ments de $\Gamma$}
Dans la suite, on convient des notations suivantes{\,}:

$\triangleright$ Les $M_i$ sont dans $\Gamma_1\setminus \{I\}$, et les $P_i$ sont dans $\Gamma_2\setminus
\{I\}$.

$\triangleright$ Pour $n$ dans $\N^*$, on note $\Pi_n$ le produit $(M_1P_1)(M_2P_2)\dots(M_nP_n)$.

\begin{itemize}
  \item[1.]Justifier qu'un \'{e}l\'{e}ment de $\Gamma$ est de l'un des types suivants{\,}:
\end{itemize}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
{\wtr 24\bf (0)}&$U_0=I$&{\bf (1)}&$U_1=P_0$&{\bf (2)}&$U_2=M_0$&{\bf
(3)}&$U_3=P_0M_0$\\
\hline
{\wtr 24\bf (4)}&$U_4=\Pi_n$, $n\geq 1$&{\bf (5)}&$U_5=P_0\Pi_r$, $r\geq
1$&{\bf (6)}&$U_6=\Pi_sM_{s+1}$, $s\geq 1$&{\bf (7)}&$U_7=P_0\Pi_tM_{t+1}$,
$t\geq
1$\\
\hline
\end{tabular}
\begin{itemize}
  \item[2.]On rappelle que les matrices $M_i$ et $P_j$ sont toutes diff\'{e}rentes de $I$.
\begin{itemize}
  \item[(a)]Montrer que $U_3\not= I$.
  \item[(b)]En consid\'{e}rant $U_6X_2$ avec $X_2$ dans $E_2$, montrer que $U_6\not= I$.
  \item[(c)]Montrer que $U_5\not= I$ (on pourra consid\'{e}rer une matrice semblable \`{a}
  $U_5$ afin de se ramener au {\bf b.}). D\'{e}montrer de m\^{e}me que $U_4\not= I$.
  \item[(d)]En d\'{e}duire que $U_7\not=I$.
\end{itemize}
  \item[3.]On consid\`{e}re le produit
  $$\Pi'_n=(M'_1P'_1)(M'_2P'_2)\dots(M'_nP'_n)$$
  o\`{u} $n\geq 1$, les $M'_i$ sont dans $\Gamma_1\setminus\{I\}$, et les $P'_i$ sont dans
  $\Gamma_2\setminus\{I\}$.
\begin{itemize}
  \item[(a)]\'{E}tablir que l'\'{e}galit\'{e} $\Pi_n=\Pi_n'$ impose $M_i=M'_i$ et $P_i=P'_i$ pour tout $i$,
  $1\leq i\leq n$ (on pourra consid\'{e}rer la matrice $\Pi_n'\Pi_n^{-1}$).
  \item[(b)]En consid\'{e}rant $S=\{A,A^{-1},B,B^{-1}\}$, en d\'{e}duire que le groupe $\Gamma$ est \`{a} croissance exponentielle.
  Quelle est la croissance du groupe $SL_2(\Z)${\,}?
\end{itemize}
\end{itemize}

\subsubsection*{C. \'{E}l\'{e}ments d'ordre fini de $\Gamma$}
On se propose de montrer que $I$ est le seul \'{e}l\'{e}ment d'ordre {\sl fini} de $\Gamma$.

Soit $(U, k)\in \Gamma\times \N^*$ tel que $U^k=I$.
\begin{itemize}
  \item[1.]Montrer que $U$ ne peut pas \^{e}tre du type $U_4$, $U_7$ ou $U_3$.
  \item[2.]On suppose que $U$ est du type $U_6$.
\begin{itemize}
  \item[(a)]En consid\'{e}rant les \'{e}l\'{e}ments $V_1=M_{s+1}U_6M_{s+1}^{-1}$,
  $V_2=P_1^{-1}V_1P_1$, montrer que l'on a, successivement, $M_{s+1}M_1=I$,
  puis $P_sP_1=I$.
  \item[(b)]Relever alors une contradiction.
\end{itemize}
  \item[3.]En d\'{e}duire que $U$ ne peut pas \^{e}tre de type $U_5$.
  \item[4.]Conclure que $U=I$.
\end{itemize}

\subsubsection*{D. Conclusion}
Gr\^{a}ce aux r\'{e}sultats du {\bf B.2.} et par des calculs analogues \`{a} ceux du {\bf B.3.} on pourrait montrer
que{\,}:

(1) Pour chacun des types rencontr\'{e}s au {\bf B.l.}, l'\'{e}criture est {\sl
unique}.

(2)Un \'{e}l\'{e}ment de $\Gamma$ ne peut \^{e}tre que d'{\sl un seul type}.

Dans la suite, le candidat pourra utiliser librement ces r\'{e}sultats.

\vskip 2mm
$\triangleright$ Lorsque $\ca M\subset \Gamma$ et $V\in \Gamma$, on pose $V\ca M=\{VU,\ U\in \ca M\}$.

\vskip 2mm
D\'{e}montrer l'existence de quatre parties $\ca Q_1$, $\ca Q_2$, $\ca R_1$, $\ca R_2$ de $\Gamma$, non vides et deux \`{a}
deux disjointes, telles que
$$\Gamma =\ca Q_1\cup A\ca Q_2\ \et \ \Gamma =\ca R_1\cup B\ca R_2.$$

\subsection*{
\begin{center}
Partie V : Ensembles G -paradoxaux
\end{center}}

\subsubsection*{Rappels}
\begin{itemize}
  \item[$\triangleright$]Une op\'{e}ration ou action d'un groupe $(G,\cdot)$, de neutre not\'{e} 1, sur un ensemble non vide $E$
  est la donn\'{e}e d'une application $\star{\,}: G\times E \rightarrow E$ telle
  que{\,}:
\begin{itemize}
  \item[(i)] $\forall\,(g',g,x)\in G\times G \times E,\ g'\star (g\star x)=(g'g)\star
  x${\,};
  \item[(ii)] $\forall\,x\in E,\ 1\star x=x$.
\end{itemize}
  \item[$\triangleright$]les $G$-orbites de $E$ sont alors les ensembles $\ca O_x=\{g\star x,\ g\in G\}$ pour $x$ dans $E$,
  elles constituent une partition de $E$.
\end{itemize}

Si le groupe $G$ op\`{e}re sur $E$ on le fait aussi op\'{e}rer de mani\`{e}re naturelle sur l'ensemble des parties de $E$ en posant
$$\forall\,g\in G,\ \forall\,X\subset E,\ g\star X = \{g\star x,\ x\in X\}.$$

\subsubsection*{D\'{e}finition}
Avec les notations pr\'{e}c\'{e}dentes, on convient de dire qu'une partie $\ca P$ de $E$ est $G$-{\sl paradoxale} lorsqu'elle
contient des parties $\ca Q$ et $\ca R$ non vides et disjointes pour lesquelles il
existe{\,}:
\begin{itemize}
  \item[1.]Des entiers $m,n\geq 1${\,};
  \item[2.]des partitions de $\ca Q$ et $\ca R$, $(\ca Q_i)_{1\leq i\leq m}$, $(\ca R_j)_{1\leq j\leq
  n}${\,};
  \item[3.]des suites finies d'\'{e}l\'{e}ments de $G$, $(g_i)_{1\leq i\leq m}$, $(h_j)_{1\leq j\leq n}$ v\'{e}rifiant
  $$\ca P=\bigcup_{1\leq i\leq m} g_i\star \ca Q_i=\bigcup_{1\leq j\leq n} h_j\star \ca
  R_j.$$
\end{itemize}
Autrement dit, et de fa\c{c}on imag\'{e}e, $\ca P$ est $G$-paradoxale lorsqu'elle contient des parties non vides et
disjointes $\ca Q$ et $\ca R$, chacune pouvant \^{e}tre d\'{e}coup\'{e}e en un nombre fini de morceaux puis r\'{e}arrang\'{e}e sous l'action de
$G$ de mani\`{e}re \`{a} reconstituer $\ca P$.

\subsubsection*{A. Exemples}
\begin{itemize}
  \item[1.]D\'{e}finir une op\'{e}ration du groupe $\Gamma$ de la partie {\bf IV.} sur l'ensemble $\Gamma$ de sorte
  que $\Gamma$ soit un ensemble $\Gamma$-paradoxal.
  \item[2.]Soit $E$ un ensemble non vide, et $G$ un
  sous-groupe de $\SG_E${\,}; montrer que toute partie $G$-d\'{e}doublable de $E$ est $G$-paradoxale pour une action de $G$
  qui est \`{a} pr\'{e}ciser.

  {\bf Commentaire{\,}:} En adaptant de fa\c{c}on mineure l'argumentation propos\'{e}e au {\bf III.} on pourrait montrer le
  r\'{e}sultat suivant [W. SIERPINSKI 1954] :
\begin{center}
\fbox{\hskip .2cm $\R$ ne contient aucune partie $\IG_1$-paradoxale.\wtr 35\hskip .2cm}
\end{center}
  \item[3.]On suppose que le groupe $\Gamma$ op\`{e}re sur un ensemble non vide $E$, et que
  l'hypoth\`{e}se suivante est v\'{e}rifi\'{e}e{\,}:
  $$\forall\,U\in \Gamma\setminus\{I\},\ \forall\,x\in E,\ U\star x\not= x.$$
  Montrer que l'ensemble $E$ est $\Gamma$-paradoxal.

  {\sl Indication{\,}:} On pourra consid\'{e}rer une partie $T$ de $E$ telle que l'intersection de $T$ avec chacune des
  $G$-orbites est un singleton, et l'on ne soul\`{e}vera pas de difficult\'{e} relative \`{a} l'existence d'une telle partie.
\end{itemize}

\subsubsection*{B. Le plan hyperbolique est $\Gamma$-paradoxal}
On note $H^2 = \{x \in \C,\ \Im (x) > 0\}$ (le demi-plan de Poincar\'{e}).
\begin{itemize}
  \item[1.]Soit $M =\pmatrix{a&b\cr c&d\cr}$ une matrice de $SL_2(\Z)${\,}; montrer que l'on d\'{e}finit une bijection
  $h_M$ de $H^2$ sur lui-m\^{e}me en posant{\,}:
  $$\forall\,x\in H^2,\ h_M(x)={ax+b\over cx+d}.$$
\end{itemize}
Dans la suite on pourra utiliser sans justification le fait que l'application $M\mapsto h_M$ d\'{e}finit un morphisme
du groupe $(SL_2(\Z),\cdot)$ vers le groupe sym\'{e}trique $(\SG_{H^2},\circ)$.
d\'{e}finit un morphisme du
\begin{itemize}
  \item[2.]
\begin{itemize}
  \item[(a)]Montrer que le noyau du morphisme cit\'{e} ci-dessus est $\{\pm I\}$.
  \item[(b)]Montrer que ce morphisme induit un isomorphisme du sous-groupe $\Gamma$ sur son image, que l'on
  notera $\overline T$.
\end{itemize}
  \item[3.]Soit $M$ dans $SL_2(\Z)$ tel que l'homographie $h_M$ fixe au moins un point de $H^2$.
\begin{itemize}
  \item[(a)]\'{E}tablir l'alternative{\,}: $(|{\rm tr}(M)|<2$ ou bien $h_M=Id)$.
  \item[(b)]Prouver que $h_M$ est d'ordre fini dans le groupe
  $(\SG_{H^2},\circ)$.
\end{itemize}
  \item[4.]D\'{e}montrer qu'aucun \'{e}l\'{e}ment de $\overline{\Gamma}\setminus \{Id\}$ n'a de point fixe dans $H^2$.
  \item[5.]Prouver que le demi-plan de Poincar\'{e} est $\Gamma$-paradoxal pour une op\'{e}ration de $\Gamma$ que l'on pr\'{e}cisera.
\end{itemize}

\subsection*{C. Une partie de $\R^2$ born\'{e}e et $\Gamma$-paradoxale}


\begin{itemize}
  \item[$\triangleright$]On note $\Delta$ la partie $[0,1[^2$ de $\R^2$. On rappelle que l'on d\'{e}finit une relation
  d'\'{e}quivalence, not\'{e}e $\sim$, en posant:
  $$\forall\,p,q\in \R^2,\ p\sim q\Longleftrightarrow p-q\in \Z^2.$$
  De plus $\Delta$ rencontre chaque classe d'\'{e}quivalence selon un singleton.

  Lorsque $p\in\R^2$, on note $\widehat p$ l'unique $q$ de $\Delta$ tel que $p\sim q$.
  \item[$\triangleright$]Pour $U =\pmatrix{a&b\cr c&d\cr}$ dans $\Gamma$ et $p=(x,y)\in
  \R^2$,on pose
  $$U\star p=(ax+by,cx+dy).$$
\end{itemize}
On admettra sans justification que l'on d\'{e}finit ainsi une op\'{e}ration du groupe $\Gamma$ sur l'ensemble $\R^2$, et que ,
si l'on note $\gamma_U$ la bijection $p\mapsto U\star p$ de $\R^2$ dans $\R^2$, l'ensemble $\Gamma_g=\{\gamma_U,\ U\in
\Gamma\}$ est un sous-groupe de $\SG_{\R^2}$, version {\sl g\'{e}om\'{e}trique} du groupe $\Gamma$

\begin{itemize}
  \item[1.]{\'E}tablir que{\,}:
  $$\forall\,\gamma \in \Gamma_g,\ \forall\,p,q\in \R^2,\ p\sim q
  \Longleftrightarrow \gamma(p)\sim\gamma(q).$$
  \item[2.]Lorsque $\gamma\in \Gamma_g$, on d\'{e}finit une application $\widehat{\gamma}$ de $\Delta$ dans $\Delta$
  en posant, pour tout $p$ de $\Delta$, $\widehat{\gamma}(p)=\widehat{\gamma(p)}$.

  Montrer que l'application  $\gamma\mapsto \widehat{\gamma}$ est un morphisme injectif du groupe
  $(\Gamma_g,\circ)$ dans le groupe $(\SG_{\Delta},\circ)$ des bijections de $\Delta$. On note $\widehat{\Gamma}_g$ son image.
  \item[3.]D\'{e}montrer que $\widehat{\Gamma}_g$ est un ensemble d\'{e}nombrable.
  \item[4.]On s'int\'{e}resse \`{a} l'ensemble $F = \{ p\in \Delta,\ \exists\,\widehat{\gamma}\in \widehat{\Gamma}_g\setminus \{Id\},\ \widehat{\gamma}(p)=p\}$.

  On note $C_0$ un cercle donn\'{e} contenu dans $\Delta$, et de rayon strictement positif. On rappelle que $\R$ n'est pas
  d\'{e}nombrable.
\begin{itemize}
  \item[(a)]Montrer que si $(\ca D_n)_{n\in \N}$ est une suite de droites affines de $\R^2$, on a
  $\d\bigcup_{n\in \N}(C_0\cap \ca D_n) \not= C_0$.
  \item[(b)]En discutant l'\'{e}quation $\widehat{\gamma}(p)=p$ selon la nature de $\gamma$ (\'{e}l\'{e}ment de
  $\widehat{\Gamma}_g\setminus \{Id\}$), montrer que $C_0\cap F\not= C_0$.
\end{itemize}
  \item[5.]En d\'{e}duire que $F$ est une partie d'int\'{e}rieur vide dans $\R^2$.
  \item[6.]Montrer que l'on peut faire op\'{e}rer le groupe $\Gamma$ sur la partie {\sl born\'{e}e} non vide $\ca P=\Delta\setminus F$
  de telle sorte que{\,}:
  \begin{center}
  \fbox{\hskip .2cm $\ca P$ soit un ensemble $\Gamma$-paradoxal.\wtr 35\hskip .2cm}
  \end{center}
\end{itemize}

\end{document}
