\chapter{Métropole-Europe-Afrique-Orient-Inde}
\olympEntete{Triangles à côtés entiers}{Premières fois}{AGADADAGA}

\begin{Enonce}[Triangles à côtés entiers]{}
  On dit qu’un triangle est un triangle entier si les longueurs de ses
  $3$ côtés sont des entiers naturels non nuls.  On rappelle la
  propriété dite de l’« inégalité triangulaire » : dans tout triangle
  non aplati la longueur de chacun des côtés est strictement
  inférieure à la somme des longueurs des deux autres.

  \begin{enumerate}
  \item
    \begin{enumerate}
    \item Parmi les triplets suivants $\coord(x,y,z)$, expliquer lequel
      désigne les longueurs des côtés d’un triangle entier non aplati,
      puis comment tracer ce triangle et avec quels outils :
      \begin{center}
        \hfill $\coord(4, 4, 5)$ \hfill $\coord(3, 6, 9)$ \hfill
        $\coord(2, 2, 6)$ \hfill ~
      \end{center}
    \item Quelles sont les valeurs possibles de l’entier $z$ si
      $\coord(15,19,z)$ désigne les longueurs des trois côtés d’un
      triangle entier non aplati rangées par ordre croissant de taille
      ?
    \item Étant donné trois entiers naturels non nuls $x$, $y$ et $z$
      tels que $x \leq y \leq z$, quelle condition faut-il ajouter
      pour que le triplet $\coord(x,y,z)$ désigne les longueurs des
      côtés d’un triangle entier non aplati ?
    \end{enumerate}
  \item Soit un $p$ entier naturel non nul. On désigne par $E_p$
    l’ensemble des triplets d’entiers naturels \emph{rangés par ordre
      croissant} $x \leq y \leq z$ et désignant les côtés d’un
    triangle entier non aplati dont le périmètre est égal à $p$.

    Ainsi obtiendrait-on
    $E_9 = \lbrace\coord(1,4,4), \coord(2,3,4), \coord(3,3,3)\rbrace$.
    \begin{enumerate}
    \item Si le triplet appartient à $E_{18}$ quelles sont les valeurs
      maximale et minimale pour $z$ ?
    \item Donner la composition de $E_{18}$ et représenter dans un
      repère orthonormé l’ensemble des couples pour lesquels il existe
      un entier naturel $z$ tel que $\coord(x,y,z) \in E_{18}$.

      Vérifier que ces couples se situent à l’intérieur ou sur les
      bords d’un triangle dont les sommets ont des coordonnées
      entières.

      
    \end{enumerate}
  \item
    \begin{enumerate}
    \item Justifier que si $\coord(x,y,z) \in E_{p}$ alors
      $\coord(x+1,y+1,z+1) \in E_{p+3}$.
    \item Soit $\coord(x,y,z) \in E_{p+3}$ . Déterminer une condition
      sur $\coord(x,y,z)$ pour que $\coord(x-1,y-1,z-1) \in E_{p}$.
    \item En déduire que si $p$ est impair alors $E_p$ et $E_{p+3}$
      ont le même nombre d’éléments.
    \end{enumerate}
  \item Étude de $E_{2019}$.
    \begin{enumerate}
    \item $E_{2019}$ contient-il un triplet $\coord(x,y,z)$
      correspondant à un triangle équilatéral ?
    \item $E_{2019}$ contient-il des triplets $\coord(x,y,z)$
      correspondant à des triangles isocèles non équilatéraux? Si oui
      combien ?
    \item Montrer que si $E_{2019}$ contient un triplet
      $\coord(x,y,z)$ correspondant à un triangle rectangle alors
      \[
        2019^2 = \num{4038}(x+y) - 2xy.
      \]
      En déduire que ne contient pas de triangle rectangle.
    \end{enumerate}
  \item Dans cette question on se propose de dénombrer $E_{2019}$.
    \begin{enumerate}
    \item Soit $\coord(x,y,z) \in E_{2022}$. On rappelle que
      $x \leq y \leq z$.  Justifier que $x + y \geq \num{1012}$ et
      $x+2y \leq \num{2022}$.
    \item Réciproquement, montrer que si $x \leq y$,
      $x + y \geq \num{1012}$ et $x+2y \leq \num{2022}$ alors
      $\coord(x,y,\num{2022} -x -y) \in E_{2022}$.
    \item Justifier que, dans un repère orthonormé, l’ensemble des
      couples d’entiers naturels $\coord(x,y)$ tels que $x \leq y$,
      $x + y \geq \num{1012}$ et $x+2y \leq \num{2022}$ constitue
      l’ensemble des points à coordonnées entières d’un triangle qui
      est rectangle. En déterminer l’aire ainsi que le nombre de
      points à coordonnées entières situés sur ses côtés.
    \item On admet le théorème de Pick :

      \begin{olympAlert}{Théorème de Pick}
        Si un polygone $P$ est tel que tous ses sommets sont à
      coordonnées entières dans un repère orthonormé alors son aire
      $A$ est donnée par la formule $A = i + \frac{j}{2} -1 $ où $i$
      désigne le nombre de points à coordonnées entières situés à
      l’intérieur de $P$ et $j$ le nombre de ceux situés sur les côtés
      de $P$
    \end{olympAlert}
    
      En déduire le nombre de triplets de $E_{2022}$ puis celui de
      $E_{2019}$.
    \end{enumerate}
  \item Une solution algorithmique

    De manière générale, concevoir un programme (à retranscrire sur sa
    copie) permettant d’énumérer et de dénombrer $E_p$. Le tester sur
    $E_{2022}$ et sur $E_{2019}$
  \end{enumerate}
  \begin{Corrige}
    \begin{enumerate}
    \item
      \begin{enumerate}
      \item $\coord(4, 4, 5)$ est le seul qui réponde à la définition.

        On trace un segment $[BC]$ de longueur $5$. Le cercle de
        centre $B$ de rayon $4$ coupe la médiatrice de $[BC]$ en deux
        points. $A$ est l'un d'eux.
      \item En appliquant la définition $19 \leq z \leq 33$.

      \item C'est l'inégalité stricte qui manque $z< x+y$ : une fois déclaré le
        plus grand, le fait que la longueur de chaque côté soit
        inférieure à la somme des longueurs des deux autres est
        acquis.
      \end{enumerate}
    \item
      \begin{enumerate}
      \item Comme $ z < x +y$, $x + y + z > 2z$. Il s'ensuit que
        $z \leq 8$. La plus petite valeur de $z$ est celle pour
        laquelle les trois côtés sont de même longueur, $6$.

      \item Pour énumérer les éléments de $E_{18}$, on tient compte du
        fait que les deux plus petits côtés ont des longueurs $x$ et
        $y$ telles que $x+y > 9$. On obtient :
        \[
          E_{18} = \lbrace
          \coord(2,8,8),\coord(3,7,8),\coord(4,6,8),\coord(5,5,8),
          \coord(4,7,7),\coord(5,6,7),\coord(6,6,6)\rbrace.
        \]
        Le triangle est représenté sur la figure \ref{fig_olymp_19A}.
        \begin{figure}[!h]
          \centering
          \begin{tikzpicture}[scale=0.5]
            \datavisualization[school book axes, x axis ={include
              value=8}, y axis ={include value=9}] ;
            \draw (2,8) --(6,6) --(5,5) --cycle ;
            \draw[lightgray] (0,0) grid (8,9) ;
            \draw[only marks] plot[mark=*, mark
            options={fill=colLogo,draw=colLogoFort},mark size=4pt]
            coordinates{(2, 8) (3, 7) (4, 6)  (4, 7) (5, 5) (5, 6) (6, 6)} ;
          \end{tikzpicture}
          \caption{Les points de $E_{18}$}
          \label{fig_olymp_19A}
        \end{figure}
      \end{enumerate}
    \item\label{q_olymp_19Aa}
      \begin{enumerate}
      \item L'inégalité est transportée lorsqu'on ajoute $1$ au plus
        petit membre et $2$ au plus grand, la somme est la bonne.

      \item Pour que le triplet $\coord(x-1,y-1,z-1)$ appartienne à
        $E_{p-3}$, il faut que $z-1 < x-1 + y-1$, c'est-à-dire
        $z < x+y - 1$ Comme on a affaire à des entiers vérifiant
        $z < x+y$, il suffit que $z \not= x+y$ et que $x \not= 1$
        d'autre part pour que le nouveau triangle en soit un.

      \item Si $p$ est impair, l'égalité $x -1 + y-1 = z-1$ est
        impossible, attendu que $x-1 + y-1 + z-1$ doit être pair.

        % Soit $\coord(x,y,z) \in E_{p+3}$, on a donc $x+y+z = p+3$
        % qui
        % est
        % pair. $\coord(x-1,y-1,z-1)$, avec $x-1+y-1 = z-1$ est-il
        % élément de $E_p$ ?
        % On a $z = x+y -1$, soit $x+y+z = x+ y + x+y -1 = p+3$, soit
        % $2x+2y = p+4$, or un pair ne peut être égal à un impair.
    
        Il n'y a pas de triplet $\coord(1,y,z)$ dans $E_{p+3}$, car
        $1+y+z = p+3$ et $z < y+1$ conduisent à $p+3 < 2y+1$, ou
        $p+2 < 2y$, ce qui fait de $y$ la plus grande longueur à
        égalité avec $z$, mais $y+z$ est impair, puisque $p+3$ est
        pair.

        Les deux ensembles ont le même nombre d'éléments
      \end{enumerate}
    \item Étude de $E_{2019}$.
      \begin{enumerate}
      \item Oui, car $\num{2019} = 3 \times 673$.

      \item Deux sortes de triangles isocèles sont \emph{a priori} possibles
        : ceux dont les côtés égaux ont la plus petite longueur et
        ceux dont les côtés égaux ont la plus grande. Les triplets
        $\coord(x,x,z)$ tels que $2x + z = \num{2019}$ et $z > x$ vérifient
        car $3x < \num{2019} < 4x$, car $z < 2x$.  On a donc
        $x \in \lbrace 505, 506, \ldots,
        672\rbrace$. % 504 n'est pas dans la liste.

        Les triplets $\coord(x,z,z)$ tels que $x+2z = \num{2019}$ vérifient
        $ 674 < z < \num{1009}$ et donc
        $z \in \lbrace 675, 676, \ldots, \num{1008}, \num{1009}
        \rbrace$.% 1009 est dans la liste

        Il y a en tout $168 + 335 = 503$ triangles isocèles non
        équilatéraux dans $E_{\num{2019}}$.
      \item Le triplet correspond à un triangle rectangle de périmètre
        $\num{2019}$ si $x^2+y^2 = z^2$ et $x + y + z = \num{2019}$.  On a donc :
        \begin{align*}
          \num{2019}^2 & = x^2 + y^2 + z^2 + 2(x+y)z+ 2xy \\
                 & = x^2+y^2+z^2 + 2(x+y)(\num{2019} -x-y) + 2xy \\
                 &= x^2+y^2+z^2 + \num{4038}(x+y) -2(x+y)^2 + 2xy  \\
                 &= x^2+y^2 +z^2 + \num{4038}(x+y) -2x^2 -4xy -2y^2 +2xy \\
                 &= \num{4038}(x+y) - 2xy
        \end{align*}
        Mais ce dernier nombre est pair. Donc le problème n'a pas de
        solution.
      \end{enumerate}
    \item
      \begin{enumerate}
      \item Ces conditions sont celles données dans la définition.

      \item La somme des trois longueurs vaut bien $\num{2022}$, les deux
        conditions imposent $\num{2022} -x -y \geq y$, donc
        $\num{2022} -x - y > 0$, et $\num{2002} > y + \num{1012}$ qui donne l'ordre.

      \item Le triangle --- appelé ici $ABC$ par commodité --- est
        reproduit sur la figure \ref{fig_olymp_19B}. L'angle droit est
        à l'intersection des droites de pentes $1$ et $-1$. Les points
        à coordonnées entières de la droite d'équation $y =x$ sont les
        points d'abscisse entière comprise entre l'abscisse de $A$
        ($506$) et celle de $B$ ($674$). Les points à coordonnées
        entières sur le côté $AC$ d'équation $ y = \num{1012}-x$ sont aussi
        ceux dont l'abscisse est entière supérieure ou égale à $2$ et
        inférieure ou égale à $506$. Les points à coordonnées entières
        sur le côté $BC$ sont aussi ceux dont l'abscisse est paire
        (l'équation de la droite est $ y = \num{1011} - \frac{x}{2}$) et
        comprise entre $2$ et $674$. L'aire du triangle rectangle est
        $\num{84 672}$ (demi-produit des longueurs des
        cathètes\footnote{Côtés de L'angle droit dans un triangle
          rectangle.}).

    \begin{figure}[!h]
      \centering
      \pgfkeys{/pgf/number format/.cd,1000 sep={\,}} %FP
      \begin{tikzpicture}[scale=0.5,every node={inner sep=Opt}]
        \datavisualization[school book axes={unit=100}, x axis =
        {grid,grid={major=style=lightgray},include value=900}, y axis
        = {grid,include value=1100}, visualize as
        line/.list={d1,d2,d3},draw = colLogoFort ]
        data[set=d1,format=function] { var x : interval [0 : 900]
          samples 2 ; func y = 1 * \value x ; }
        data[set=d2,format=function] { var x : interval [0 : 900]
          samples 2 ; func y = -1 * \value x + 1012 ; }
        data[set=d2,format=function] { var x : interval [0 : 900]
          samples 2 ; func y = -0.5 * \value x + 1011 ; };

        % \fill[colLogoTeinte,draw=colLogoFort,line width = 1pt]
        % (5.06,5.06)
        % --(6.74,6.74) --(0.02,10.10) --cycle ;
        \coordinate[label=below:$A$] (A) at (5.06,5.06) {} ;
        \coordinate[label=above:$B$] (B) at (6.74,6.74) {} ;
        \coordinate[label=above right:$C$] (C) at (0.02,10.10) {} ;
        \coordinate (up west) at (0,11.0) ; \coordinate (up east) at
        (9.00,11.0) ; \coordinate (d1 east) at (9.00,9.00) ;
        \coordinate (d2 east) at (9.00,1.12) ; \coordinate (d3 east)
        at (9.00,5.61) ; \coordinate (down west) at (0,0) ;
        \coordinate (down east) at (9.00,0) ; \fill[colLogoFort,fill
        opacity=0.20] (C) --(up west) -- (up east) -- (d2 east)
        --cycle ; \fill[colLogo,fill opacity=0.20] (down west) --(d1
        east) -- (up east) -- (up west) --cycle ;
        \fill[colLogoTeinte,fill opacity=0.20] (C) --(d3 east) --
        (down east) -- (down west) --cycle ;
      \end{tikzpicture}
      \caption{Construction du triangle $ABC$}
      \label{fig_olymp_19B}
    \end{figure}


  \item On utilise la formule de Pick pour trouver le nombre de points
    intérieurs à partir de l'aire et du nombre de points sur le
    périmètre (attention à ne pas compter $A$, $B$ et $C$ deux
    fois). Il y a $169$ points entre $A$ et $B$ ; $505$ entre $A$ et
    $C$ ; $337$ entre $B$ et $C$. Il y a donc
    $168 + 505 + 337 -3 = \num{1008}$ points sur les côtés de $ABC$.

    Il y a alors, d'après la formule de Pick,
    $\num{84 672} - \frac{\num{1008}}{2} +1 = \num{84169}$ points à
    l'intérieur de $ABC$.

    Il y a donc $ \num{84169} + \num{1008} = \num{85177}$ triplets
    dans $E_{2022}$, nombre qui est le même d'après la
    question \ref{q_olymp_19Aa} que le nombre de triplets dans $E_{2019}$.
  \end{enumerate}
\item Une solution algorithmique

  Le programme doit permettre de faire la liste des triplets d'entiers
  $x$, $y$, $z$ pour lesquels $x+y+z = p$, $x+y > p$, et
  $x \leq y \leq z$. On commencera par déterminer les valeurs extrêmes
  de $z$, ce qui nécessite d'étudier la parité et la divisibilité par
  $3$ de $p$. On distinguera 6 cas (voir le tableau
  \ref{tab_olymp_19A}).

  \begin{table}[!h]
    \centering
    \begin{tabular}{*{3}{>{$}c<{$}}}
      \toprule
      \text{\emph{Il existe un entier $q$ tel que}}
      & \text{Valeur maximale de $z$}
      & \text{Valeur minimale de $z$} \\
      \midrule
      p =  6q\hphantom{\null-1}   & 3q-1 & 2q\hphantom{\null-1}    \\
      p = 6q - 1& 3q-1 & 2q -1 \\
      p = 6q - 2& 3q-2 & 2q -1 \\
      p = 6q - 3& 3q-2 & 2q -1 \\
      p = 6q - 4& 3q-3 & 2q -2 \\
      p = 6q - 5& 3q-3 &2q -2  \\
      \bottomrule
    \end{tabular}
    \caption{Les différents cas}\label{tab_olymp_19A}
  \end{table}
  Une fois déterminés ce minimum et ce maximum, on programme une
  boucle de $z_{\text{min}}$ à $z_{\text{max}}$. Dans cette boucle, à
  chaque valeur de $z$ sont associées successivement les valeurs de
  $y$ allant de $1$ à $z$. À chacune des valeurs de correspond au
  maximum une seule valeur de $x$ telle que $x+y+z = p$. Si cette
  valeur vérifie $x \leq y \leq z$ et $x+y > z$, elle est acceptée,
  sinon on passe à $x+1$.

  \emph{Autre déroulé} : on peut aussi utiliser une boucle For sur la
  plus petite des longueurs, $x$, et à chaque tour de boucle boucler
  sur $y$.

  On donne ici deux programmes python, de la recherche du nombre
  d'éléments dans $E_{\num{2019}}$.

\begin{center}
  \captionsetup{type=figure}
  \begin{tcblisting}{top=0mm,bottom=0mm,left=0mm,right=0mm,colframe=colLogoFort,listing
      only, title=Nombres d'éléments dans $E_{\num{2019}}$,
      fonttitle=\bfseries\small,colbacktitle=colLogoFort,
      listing options={language=python,style=afdmpython}}
def searchTriplet(p):
    """ recherche les triplets entiers (x,y,z)
    tel que x+y+z = p et (x,y,z) un triangle.  Version "naive"
    """
    resultat = []
    for z in range(1,p+1):
        for y in range(1,z+1):
        x = p - y - z
        if x <= y and y <= z and z < x+y and x < z+y and y < z +x :
        resultat.append((x,y,z))
    return resultat

    
def searchTriplet2(p):
    """
    On cherche à faire plus rapide que le
    searchTriplet
    """
    if p % 6 == 0 :
         q = p // 6 zmin = 2*q zmax = 3*q-1
    if p % 6 == 5 :
         q = (p+1) // 6 zmin = 2*q-1 zmax = 3*q-1
    if p % 6 == 4 :
         q = (p+2) // 6 zmin = 2*q-2 zmax = 3*q-2
    if p % 6 == 3 :
         q = (p+3) // 6 zmin = 2*q - 2 zmax = 3*q - 2
    if p % 6 == 2 :
         q = (p+4) // 6 zmin = 2*q-2 zmax = 3*q - 3
    if p % 6 == 1 :
         q = (p+5) // 6 zmin = 2*q-2 zmax = 3*q-3
    resultat = []
    for z in range(zmin,zmax+1):
         for y in range(1,z+1):
         x = p - y - z
         # print(x,y,z,x+y,x+y+z, c1 , c2)
         if x <= y and y <= z and z < x+y :
             resultat.append((x,y,z))

    return resultat

    print("Version lente") print(len(searchTriplet(2019)))
    print("Version rapide") print(len(searchTriplet2(2019)))
  \end{tcblisting}
\end{center}

Dans les deux cas la réponse fournit est : \num{85177}
\end{enumerate}
\end{Corrige}
\end{Enonce}


\begin{Enonce}[Premières fois]
  
  On note $\N$ l’ensemble des entiers naturels. On rappelle qu’un
  nombre premier est un entier naturel qui a exactement $2$
  diviseurs entiers naturels distincts : $1$ et lui-même. Par exemple :
  $2$, $3$ et $5$ sont premiers alors que $0$, $1$ et $6$ ne le sont pas.


  \begin{olympAlert}{Décomposition en produit de facteurs premiers}

    Pour tout entier naturel $n \geq 2$ il existe un unique entier
    naturel $k$, une unique liste de nombres premiers distincts rangés
    dans l’ordre croissant $p_1$, $p_2$, $p_3$, \ldots, $p_k$ et une
    unique liste d’entiers naturels non nuls $\alpha_1$, $\alpha_2$,
    $\alpha_3$, \ldots, $\alpha_k$tels que :
    \[
      n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3}
      \times \ldots \times p_k^{\alpha_k}
    \]
  
    On écrit, par exemple, $72 = 2^3 \times 3^2$ (ici $k=2$), ou
    $32 = 2^5$ (dans ce dernier exemple, $k = 1$). La décomposition en
    produit de facteurs premiers d’un nombre premier $p$ s’écrit
    simplement $p = p^1$.
  \end{olympAlert}
  
\Partie{Une fonction agissant sur les nombres entiers naturels}

On souhaite savoir s’il est possible de considérer une fonction $
\Delta \:: \: \N \rightarrow \N $ possédant les propriétés suivantes :
\begin{description}
\item[Propriété (1) : ] $ \Delta(0) = \Delta(1) = 0 $ ;
\item[Propriété (2) : ] Pour tout entier premier $p$, $\Delta(p) = 1$ ;
\item[Propriété (3) : ] Pour tous entiers naturels $a$ et $b$ :
  $\Delta(a \times b) = \Delta(a) \times b + a \times \Delta(b)$
\end{description}
\begin{enumerate}
\item Soit $p$ un nombre premier. Les propriétés précédentes
  permettent-elles d’exprimer $\Delta(p^2)$ ? $\Delta(p^3)$? Un entier
  naturel $n$ étant donné, quelle est l’image par de $\Delta(p^n)$ ? 
\item
  \begin{enumerate}
  \item Soit $p$ et $q$ des nombres premiers distincts, $m$ et $n$ des entiers
    naturels supérieurs ou égaux à $1$. Les propriétés précédentes
    permettent-elles d’exprimer $\Delta(p^m \times q^n)$ ?
  \item Le nombre $\Delta(10^n)$ est-il un multiple de $7$ pour $n
    \geq 1$ ?
  \end{enumerate}
\item À tout nombre entier $n \geq 2$, dont la
  décomposition en produit de facteurs premiers s’écrit :
  \[
    n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3}
      \times \ldots \times p_k^{\alpha_k}
  \]
  on associe les quotients $q_1$ de $n$ par $p_1$, $q_2$ de $n$ par
  $p_2$\ldots, $q_k$ quotient de $n$ par $p_k$.
  \begin{enumerate}
  \item Montrer que si $n \geq 2$ alors,
    $\Delta(n) = \alpha_1 \times q_1 + \alpha_2 \times q_2 + \alpha_3
    \times q_3 + \cdots + \alpha_k \times q_k$.
  \item Vérifier que l’expression ainsi obtenue satisfait les
    propriétés (2) et (3) ci-dessus. 
  \end{enumerate}
\end{enumerate}

\Partie{Étude de quelques images d’entiers par la fonction $\Delta$}

\begin{enumerate}[resume]
\item
  \begin{enumerate}
  \item\label{q_olymp_19Ab} Calculer $\Delta(12)$, $\Delta(56)$, $\Delta(\num{1001})$.
  \item Quelles sont les solutions de l’équation $\Delta(x) = 0 $ ?
  \item Quelles sont les solutions de l’équation $\Delta(x) = 1$ ?
  \item Tout entier naturel $n$ a-t-il au moins un antécédent par
    $\Delta$ ?
  \item Est-il vrai que, pour tout entier naturel $n$, $\Delta(n) \leq
    n$ ?
  \end{enumerate}
\item
  \begin{enumerate}
  \item Montrer que si $p$ et $q$ sont des nombres premiers alors
    $\Delta(p \times q) = p+q$.
  \item Est-il vrai que pour tous entiers naturels $a$ et $b$ :
    $\Delta(a \times b) = a+b$ ?
  \end{enumerate}
\item
  \begin{enumerate}
  \item Est-il vrai que pour tous entiers naturels $a$ et $b$ :
    $\Delta(a+b) = \Delta(a) + \Delta(b) $  ?
  \item Soient $a$ et $b$ deux entiers naturels tels que $\Delta(a+b)
    = \Delta(a) + \Delta(b) $ et un entier naturel
    quelconque $k$. Montrer que : $\Delta(ka+kb) = \Delta(ka) + \Delta(kb) $.
  \end{enumerate}
\end{enumerate}
\Partie{Les points fixes de la fonction}
\begin{enumerate}[resume]
\item
  \begin{enumerate}
  \item Soit $p$ un nombre premier. Soit $m$ un entier naturel. On
    suppose que $m$ est un multiple de $p^p$. Montrer que dans ce cas,
    $\Delta(m)$ est aussi un multiple de $p^p$.
  \item Soit $n$ un entier naturel et $p$ un nombre premier. Soit
    $\alpha$ l’exposant de $p$ dans la décomposition en produit de
    facteurs premiers de $n$. On suppose que $\alpha \geq 1$.  Montrer
    que si $\alpha < p$, alors est $\alpha - 1$ est l'exposant de $p$
    dans la décomposition en produit de facteurs premiers de
    $\Delta(n)$.
  \end{enumerate}
\item Résoudre l’équation $\Delta(x) = x $.
\end{enumerate}
\begin{Corrige}
\Partie{Une fonction agissant sur les nombres entiers naturels}

\begin{enumerate}
\item La propriété 3 permet d'écrite $\Delta(p^2) = p\Delta(p) +
  p\Delta(p) = 2p\Delta(p) = 2p$, car $\Delta(p) = 1$ d'après la
  propriété 2.

  $\Delta(p^3) = p^2\Delta(p) + p \Delta(p^2) = p^2 + p \times 2p =
  3p^2$.

  On suppose que  $\Delta(p^n) = np ^{n+1}$, pour une certaine valeur
  de $n$.

  $\Delta(p^{n+1}) = p^n \Delta(p) + p \Delta(p^n) = p^n + p \times
  np^{n-1} = (n+1)p^n$.
\item
  \begin{enumerate}
  \item $\Delta (p^m \times q^n) = q^n \Delta(p^m) + p^m \Delta(q^n) =
    mq^n p^{m-1} + np^mq^{n-1} = p^{m-1}q^{n-1} (np+mq) $.
  \item En appliquant la question précédente avec $p=2$, $q=5$ et $n=m$, on obtient :
    $\Delta(10^n) = 2^{n-1} \times 5^{n-1} (2n + 5n) = 7n2^{n-1}
    \times 5^{n-1}$. On en déduit que $\Delta(10^n)$ est toujours un
    multiple de $7$, pour $n \geq 1$.
  \end{enumerate}
\item
  \begin{enumerate}
  \item On a $ n = p_1^{a_1} N$ avec $N = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3}
    \times \ldots \times p_k^{\alpha_k}$

    $\Delta(n) = N \Delta(p_1^{\alpha_1}) + p_1^{\alpha_1} \Delta(N) = \alpha_1p_1^{\alpha_1-1}N
    + p_1^{\alpha_1} \Delta(N) = \alpha_1q_1 + p_2 \Delta(N)$.
    On recommence avec $N$, qui possède moins de facteurs premiers. On
    en déduit que :
    \[
      n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3}
      \times \ldots \times p_k^{\alpha_k}
    \]
  \item Pour la propriété (2), on a $n = p$, donc $a_1 = 1$ et $q_1=1$
    donc $\Delta(n) = 1$.

    Pour la propriété (3), on rajoute les nombres premiers non
    présents dans $a$ et dans $b$, ce qui ne sont pas présents, auront
    des exposants nuls. On a alors $ a = p_1^{\alpha_1} \times
    p_2^{\alpha_2} \times \cdots p_k^{\alpha_k} $ et $ b = p_1^{\beta_1} \times
    p_2^{\beta_2} \times \cdots p_k^{\beta_k} $. On a alors
    $\Delta(a) = \alpha_1 q_1 + \alpha_2q_2 + \cdots + \alpha_kq_k$ et
    $\Delta(b) = \beta_1 r_1 + \beta_2r_2 + \cdots + \beta_kr_k$.

    Alors, $a \Delta(b) + b \Delta(b)$ contient des termes de la forme
    $a \alpha_iq_i + b \beta r_i$. Or $aq_i = bp_i$ car se sont deux
    manières d'exprimer le quotient de $ab$ par $p_i$. On a donc, $a
    \alpha_iq_i + b \beta r_i = (\alpha_i+ \beta_i)s_i$, avec $s_i$ le
    quotient de $ab$ par $p_i$ et $ (\alpha_i+ \beta_i)$ l'exposant de
    $p_i$ dans $ab$. La propriété (3) est donc bien vérifiée.  
  \end{enumerate}
\end{enumerate}

\Partie{Étude de quelques images d’entiers par la fonction \texorpdfstring{$\Delta$}{Delta}}

\begin{enumerate}[resume]
\item
  \begin{enumerate}
  \item
    \begin{itemize}
    \item\label{q_olymp_19Ab} $ 12 = 2^2 \times 3$, donc
      $\Delta(12) = 2 \times 6 + 1 \times 4 = 16$.
    \item $ 56 = 2^3 \times 7 $, donc $\Delta(56) = 3 \times 28 + 1
      \times 8 = 92$.
    \item $\num{1001} = 7 \times 11 \times 13 $ donc $\Delta(1001) = 1
      \times 143 + 1 \times 91 + 1 \times 77 =  311$.
    \end{itemize}
  \item Pour $n \geq 2$, $\Delta(n)$ est une somme d'entier positif,
    donc est non nulle. Les seules solutions sont donc $0$ et $1$.
  \item Tous les nombres premiers $p$ vérifient $\Delta(p)= 1$. Si $p$
    est composé, la formule qui donne $\Delta(p)$ est une somme
    d'entier positif. Pour qu'elle soit égale à $1$, il faudrait que
    tous les termes soient nuls sauf $1$, et le produit de deux
    entiers n'égal à $1$ que si les deux facteurs sont $1$, ce qui
    n'est pas possible.

    Donc, les solutions de $\Delta(x) = 1$ sont les nombres premiers.
  \item $2$ n'a pas d'antécédent par $\Delta$, car il faudrait deux
    termes égaux à $1$, ce qui n'est pas possible, ou un terme égal à
    $2$. Mais dans ce cas là, un deuxième $2$ apparaît.
  \item $\Delta(n) \leq n$ n'est pas toujours, comme le prouve la
    question \ref{q_olymp_19Ab}.
  \end{enumerate}
\item
  \begin{enumerate}
  \item  $\Delta(p \times q) = q \Delta(p) + p \Delta(q) = p+q$.
  \item $\Delta(12) = 16$, et $12 = 4 \times 3$. On a bien
    $\Delta(a \times b) != a + b$.
  \end{enumerate}
\item
  \begin{enumerate}
  \item $\Delta(56) = 92$, et $56 = 49 + 7$, or $\Delta(49) = 14$ et
    $\Delta(7) =1$. Donc $\Delta(a+b) != \Delta(a)+\Delta(b)$.
  \item On a :
    \begin{align*}
      \Delta(ka+kb) &= \Delta(k(a+b)) = \\
                    & = k \Delta(a+b) + (a+b) \Delta(k)\\
                    & = k \Delta(a) + k \Delta(b) + a \Delta(k) + b
                      \Delta(k) \\
                    &= \Delta(ka) + \Delta(kb)
    \end{align*}
  \end{enumerate}

\end{enumerate}
\Partie{Les points fixes de la fonction}
\begin{enumerate}[resume]
\item
  \begin{enumerate}
  \item $ m = kp^p$, $\Delta(m) = k \Delta(p^p) + p^p \Delta(k) = k p
    p^{p-1} + p^p \Delta(k) = p^p (k + \Delta(k))$. Donc, $\Delta(m)$
    est un multiple de $p^p$.
  \item $n$ est de la forme $ n = p^\alpha p_2^{\alpha_2} \cdots
    p_k^{\alpha_k}$.

    $\Delta(n) = \alpha q + \alpha_2 q_2 + \cdots + \alpha_k$, avec
    $q$ un multiple de $p^{\alpha-1}$ et $q_i$ un multiple de
    $p^{\alpha}$. On peut donc factoriser $\Delta(n)$ par
    $p^{\alpha-1}$. $\Delta(n) = p^{\alpha-1}\left(\alpha q' +
      \alpha_2 q'_2 + \cdots + \alpha_kq'_k\right)$. Comme $\alpha <
    p$, on ne peut pas dans le deuxième facteur mettre $p$ en
    facteur. On en déduit que $\alpha-1$ est l'exposant de $p$ dans la
    décomposition en facteur premier de $\Delta(n)$. 
  \end{enumerate}
\item $p^p$ est solution de l'équation. Maintenant, si $x$ est un
  entier, soit il existe un entier premier $p$ dans la décomposition
  de $x$ tel que $ \alpha < p$, alors la question précédente assure
  que $x$ n'est pas solution de l'équation. Maintenant si tous les
  facteurs premiers $p_i$ ont des exposants $\alpha_i$ vérifiant $p_i
  < \alpha_i$, le même argument que précédemment assure que $x$ n'est
  pas solution de l'équation.
\end{enumerate}
\end{Corrige}
\end{Enonce}


\begin{Enonce}[AGADADAGA]
\item Dans cet exercice, on appellera \emph{mot} toute suite de
  lettres formée des lettres A, D et G. Par exemple : ADD, A, AAADG
  sont des \emph{mots}.
 
Astrid possède un logiciel qui fonctionne de la manière suivante :  un
utilisateur entre un \emph{mot}  et, après un clic sur EXÉCUTER, chaque lettre
A du \emph{mot}  (s’il y en a)  est remplacée par le \emph{mot}  AGADADAGA. Ceci donne
un nouveau mot.

Par exemple, si l’utilisateur rentre le \emph{mot}  AGA, on obtient le mot
AGADADAGAGAGADADAGA. Un deuxième clic sur EXÉCUTER réitère la
transformation décrite ci-dessus au nouveau mot, et ainsi de suite. 

\begin{enumerate}
\item Quels sont les \emph{mots}  qui restent inchangés quand on clique sur
  EXÉCUTER ?
\end{enumerate}

\Partie{Traitement de texte}

Astrid rentre le \emph{mot}  A. 
\begin{enumerate}[resume]
\item Quel \emph{mot} obtient-elle après avoir cliqué deux fois sur
  EXÉCUTER ?
\item Combien de clics au minimum faut-il pour obtenir un
  \emph{mot}  contenant un milliard de A ?  
\item Après $20$ clics, combien le
  \emph{mot}  obtenu contient-il de lettres D ?
\end{enumerate}
 
\Partie{Motif}

Astrid souhaite maintenant dessiner un motif sur une feuille de papier
quadrillé, en utilisant le dernier \emph{mot}  obtenu par le logiciel. Pour
cela, elle lit de gauche à droite chaque lettre de ce \emph{mot}  et trace
une ligne brisée sans lever le stylo en suivant les consignes
suivantes :
\begin{itemize}
\item Le point de départ de la ligne est une croix située sur un nœud
  du quadrillage ;
\item si la lettre lue est A, elle trace horizontalement et de gauche
  à droite un segment de longueur un carreau ;
\item si la lettre lue est G, elle tourne la feuille d’un quart de
  tour dans le sens des aiguilles d’une montre ;
\item si la lettre lue est D, elle tourne la feuille d’un quart de
  tour dans le sens inverse des aiguilles d’une montre ;
\item quand toutes les lettres sont lues, elle remet la feuille dans
  la position initiale pour regarder le motif obtenu.
\end{itemize}
Par exemple, le motif obtenu à partir du \emph{mot}  ADAAGA est représenté
sur la figure \ref{fig_olymp_19Ad}.

\begin{figure}[!h]
\centering
% Exemple
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Les motifs sont faits avec le script python suivant :
% MAIS, on a aussi des macros LaTeX, mais beaucoup plus lente
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% from turtle import *
% def word2tikz(mot):
%     """
%     mot est une chaine de caractères comportant que les lettres ADG
%     production du code que l'on incorpore dans le code latex
%     """
%     sortie="\draw[colLogoFort,line width=1pt,turtle={home,rt,"
%     for c in mot:
%         if c == "A":
%             sortie+="fd,"
%         if c == "G" :
%             sortie+="lt,"
%         if c == "D" :
%             sortie+="rt,"
%     sortie+="}] ;"

%     return sortie ;

% def remplace(mot):
%     """
%     remplace les A par AGADADAGA 
%     """
%     sortie=""
%     for c in mot :
%         if c == "A":
%             sortie+="AGADADAGA"
%         else :
%             sortie+=c
%     return sortie

% def remplace2(mot):
%     """
%     remplace les A par ADAGAGAADADAGA
%     """
%     sortie=""
%     for c in mot :
%         if c == "A":
%             sortie+="ADAGAGAADADAGA"
%         else :
%             sortie+=c
%     return sortie
% def mot2turtle(mot):
%     """
%     Recherche de la question 7.
%     """
%     for c in mot:
%         if c == "A":
%             forward(25)
%         if c == "D":
%             right(90)
%         if c == "G":
%             left(90)
% # Exemple donné dans l'énoncé
% exemple = word2tikz("ADAAGA")
% première figure d'Astrid
% astrid = word2tikz("ADADAGA")
% # print(astrid)
% # Figure obtenue par Astrid après avoir appuyer deux fois sur EXECUTER
% # print(word2tikz(remplace(remplace("A"))))
% # Recherche de la chaine de remplacement de la question 7
% m  ="ADAGAGAADADAGA"
% #A la 1ere itération, on a remplacé les A par le motif m
% M = m+"D"+m+"G"+m+"G"+m+m+"D"+m+"D"+m+"G"+m
% #A la 2e itération, on a remplacé les A par le motif M
% #mot2turtle(M +"D"+M+"G"+M+"G"+M+M+"D"+M+"D"+M+"G"+M)
% # Production du code LaTeX 
% #print(word2tikz(remplace(remplace(remplace("ADAGAGAADADAGA")))))

% print("Itération 3")
% print(word2tikz(remplace2(remplace2(remplace2("A")))))

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MACROS LATEX pour représenter les figures
%
% COMPILATION BEAUCOUP PLUS LENTE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \def\motif(#1)(#2)
% {
% #1 est le motif à transformer
% #2 est le facteur d'échelle pour les tikzpicture
% On sauvegarde le motif dans \foo
% \def\foo{#1}
% on effectue le changement des lettres via la macro \StrSubstitute de
% xstring que l'on remet dans \foo
%   \StrSubstitute{\foo}{A}{fd,}[\foo]
%   \StrSubstitute{\foo}{D}{rt,}[\foo]
%   \StrSubstitute{\foo}{G}{lt,}[\foo]
%   on sauve le motif obtenu
%   \def\motifa{\foo}
%   On crée une macro complétement développée, mais en ne
%   développant pas \draw. 
%   \edef\foo{\noexpand\draw[turtle={home,rt,\motifa}] ;}
%   On trace la figure
%   \begin{tikzpicture}[line width=1pt,scale=#2]
%     \foo
%   \end{tikzpicture}
% }
% Exemple
%   \StrSubstitute{A}{A}{AGADADAGA}[\bar]%
% \bar
% \motif(\bar)(1)
% \StrSubstitute{\bar}{A}{AGADADAGA}[\bar]%
% \bar
% \motif(\bar)(1)
% Figure de la question 7. Figure très longue à compiler.
% \StrSubstitute{A}{A}{ADAGAGAADADAGA}[\bar]%
% \bar
% \motif(\bar)(1)

% \StrSubstitute{\bar}{A}{ADAGAGAADADAGA}[\bar]%
% \motif(\bar)(0.5)

% \StrSubstitute{\bar}{A}{ADAGAGAADADAGA}[\bar]%
% \motif(\bar)(0.1)



\begin{tikzpicture}[scale=0.5]
  \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ;
      \draw (-2pt,2pt)--(2pt,-2pt) ;}}
  \draw[lightgray] (-1,-3) grid (3,1) ;
  \draw[colLogoFort,line width=1pt,turtle={home,rt,fd,rt,fd,fd,lt,fd,}] ;
  \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
\end{tikzpicture}
\caption{Représentation de du mot ADAAGA}\label{fig_olymp_19Ad}
\end{figure}


\begin{enumerate}[resume]
\item Astrid a réalisé le motif de la figure \ref{fig_olymp_19Ae}. Quel \emph{mot} avait-elle
  obtenu ?
  % Astrid
  \begin{figure}[!h]
    \centering
    \begin{tikzpicture}[scale=0.5]
      \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
          (-2pt,2pt)--(2pt,-2pt) ;}} \draw[lightgray] (-1,-3) grid
      (3,1) ; \draw[colLogoFort,line
      width=1pt,turtle={home,rt,fd,rt,fd,rt,fd,lt,fd,}] ;
      \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
    \end{tikzpicture}
    \caption{Motif d'Astrid}
    \label{fig_olymp_19Ae}
  \end{figure}
\item Astrid entre le \emph{mot} A et clique deux fois sur
  EXÉCUTER. Dessiner le motif obtenu. 
\item Astrid reprogramme le logiciel et remplace le \emph{mot} AGADADAGA par un autre
  \emph{mot} dont elle ne se souvient plus. Elle rentre le
  \emph{mot} A et obtient le motif ci-dessous après avoir cliqué
  trois fois sur EXÉCUTER.
  \begin{figure}[!t]
    \centering
    \begin{tikzpicture}[scale=0.2]
      \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
          (-2pt,2pt)--(2pt,-2pt) ;}}
      \draw[colLogoFort,line
      width=1pt,turtle={home,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,
        rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,
        fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,rt,fd,lt,fd,
        lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,
        rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,
        fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,
        rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,
        fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,
        lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,
        rt,fd,rt,fd,lt,fd,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,
        lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,
        fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,
        lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,
        fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,
        fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,
        lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,
        fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,
        fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,
        rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,
        fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,
        fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,rt,fd,lt,fd,lt,fd,fd,
        rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,
        fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,
        lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,rt,fd,
        lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,
        fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,
        fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,
        lt,fd,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,
        fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,
        fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,
        rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,
        fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,rt,fd,lt,fd,
        lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,
        rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,
        fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,
        rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,
        fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,
        lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,
        rt,fd,rt,fd,lt,fd,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,
        lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,
        fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,
        lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,
        fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,fd,rt,
        fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,
        lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,fd,
        rt,fd,lt,fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,
        fd,lt,fd,fd,rt,fd,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,
        fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,lt,fd,lt,fd,fd,rt,fd,
        rt,fd,lt,fd,}] ;
      \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
    \end{tikzpicture}

    \caption{Motif obtenu par Astrid après avoir oublié le mot}
    \label{fig_olymp_19Af}
  \end{figure}
  Quel est le \emph{mot} oublié par Astrid ?
\item On s’intéresse dans cette question uniquement aux motifs
  obtenus à partir de \emph{mots} qui commencent par la lettre A, et
  se poursuivent en juxtaposant des séquences GA ou DA. On appelle
  largeur du motif le nombre de carreaux compris entre les points
  les plus à gauche et à droite du motif obtenu. Par exemple, la
  largeur du motif obtenu à partir du \emph{mot} ADAGAGA est 2.
  \begin{enumerate}
  \item Quelle est la largeur du motif obtenu à partir du
    \emph{mot} AGAGADA ? 
  \item Un \emph{mot} conforme à l’hypothèse du
    8. comporte dix lettres D et dix lettres G. Déterminer toutes les
    largeurs possibles du motif obtenu.
  \end{enumerate}
\end{enumerate}
\begin{Corrige}
  \begin{enumerate}
  \item Ce sont les mots qui ne contiennent pas de lettre A.
  \end{enumerate}
  
\Partie{Traitement de texte}

  \begin{enumerate}[resume]
  \item On obtient le mot : \StrSubstitute{A}{A}{AGADADAGA}[\motif]\motif,
    puis (en ajoutant des espaces qui facilitent la lecture).
    
    \StrSubstitute{\motif}{A}{ AGADADAGA }[\motif]\motif.
  \item À chaque remplacement d'un A, on a $5$ nouveau A. Le nombre de
    A est donc multiplié par $5$ à chaque exécution. On a donc une
    suite géométrique de raison $5$ et de premier terme $1$. On
    cherche donc $n$ tel que $5^n > \num{e9}$. Une recherche
    exhaustive donne donc $ n = 13$.
  \item À chaque étape, on a le double des A présents à l'étape
    précédente, plus les D présents à l'étape précédente.

    On note $d_n$ le nombre de D et $a_n$ le nombre de A à l'étape
    $n$. On a $d_1 = 0$ et $a_1 = 0$.

    Alors $d_n = 2a_{n-1} + d_{n-1} = 2a_{n-1}+2a_{n-2}+d_{n-2} =
    2a_{n-1}+2a_{n-2}+ \cdots + 2$. Il faut donc faire la somme d'une
    suite géométrique de raison $5$ et de premier terme $1$, puis
    doubler le résultat.
    \[
      d_n = 2 \frac{5^{n}-1}{5-1} = \frac{5^n-1}{2}\cdotp
    \]
    Pour $ n = 20$, cela donne \num{47683715820312} lettres D.
  \end{enumerate}
  \Partie{Motif}
  \begin{enumerate}[resume]
  \item  Le mot obtenu par Astrid était :  ADADAGA.
  \item On obtient le motif de la figure \ref{fig_olymp_19Ag}.
    \begin{figure}[!h]
      \centering
      \begin{tikzpicture}
        \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
          (-2pt,2pt)--(2pt,-2pt) ;}}
        \draw[colLogoFort,line width=1pt,turtle=
        {home,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,
          lt,fd,rt,fd,rt,fd,lt,fd,rt,fd,lt,fd,rt,
          fd,rt,fd,lt,fd,rt,fd,lt,fd,rt,fd,rt,fd,
          lt,fd,lt,fd,lt,fd,rt,fd,rt,fd,lt,fd,}] ;
        \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
      \end{tikzpicture}
      \caption{Motif obtenu en partant de A et en exécutant deux fois
        le programme.}
      \label{fig_olymp_19Ag}
    \end{figure}
  \item Elle a pris comme motif de remplacement : ADAGAGAADADAGA.
  \item
    \begin{enumerate}
    \item On obtient la figure \ref{fig_olymp_19Ah}. Elle est de
      largeur 1.
      \begin{figure}[!h]
        \centering
        \begin{tikzpicture}
        \draw[lightgray] (-1,-1) grid (2,3) ;
        \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
            (-2pt,2pt)--(2pt,-2pt) ;}}
        \draw[colLogoFort,line width=1pt,turtle={home,rt,fd,lt,fd,lt,fd,rt,fd,}] ;
        \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
      \end{tikzpicture}
        \caption{Motif obtenu à partir de AGAGADA}
        \label{fig_olymp_19Ah}
      \end{figure}
    \item La figure \ref{fig_olymp_19Ai} montre la figure de longueur
      $1$ qui est la plus petite possible, obtenue avec le mot
      AGAGAGAGAGAGAGAGAGAGADADADADADADADADADADA, et deux motifs de
      longueur maximum $11$, respectivement
      AGADADAGAGADADAGAGADADAGAGADADAGAGADADAGA et
      AGADAGADAGADAGADAGADAGADAGADAGADAGADAGADA.

      \begin{figure}[!h]
        \centering
        \begin{tikzpicture}[scale=0.5]
          \draw[lightgray] (-1,-1) grid (2,3) ;
          \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
              (-2pt,2pt)--(2pt,-2pt) ;}} \draw[colLogoFort,line
          width=1pt,turtle={home,rt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,lt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,rt,fd,}]
          ; \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
        \end{tikzpicture}
      \begin{tikzpicture}[scale=0.5]
        \draw[lightgray] (-1,-1) grid (12,2) ;
        \tikzset{cross/.pic={\draw (-2pt,-2pt) -- (2pt,2pt) ; \draw
            (-2pt,2pt)--(2pt,-2pt) ;}} \draw[colLogoFort,line
        width=1pt,turtle={home,rt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,rt,fd,lt,fd,lt,fd,rt,fd,rt,fd,lt,fd,}]
        ; \draw[colLogoFort,line width=1pt] (0,0) pic {cross} ;
      \end{tikzpicture}
      \caption{Motifs obtenus avec $10$ GA et $10$ DA}
      \label{fig_olymp_19Ai}
    \end{figure}

      Si en partant de AGADADAGAGADADAGAGADADAGAGADADAGAGADADAGA, on
      remplace les $6$ dernières lettres par GADADA, on diminue la
      longueur de $1$.

      En partant toujours du même motif, mais en remplaçant les $12$
      dernières lettres par GADADAGADADA, on obtient un motif de
      longueur $7$. En continuant, ainsi on obtiendrait les motifs de
      longueur $5$, $3$ et $1$.

      En considérant les groupes de $4$ lettres, après le premier A,
      on a GADA ou DAGA qui augmentent la longueur du motif de $1$ et
      GAGA et DADA qui diminuent la longueur de $1$. La longueur du
      motif ne peut donc pas être paire.

      On peut aussi penser à une énumération complète de tous les
      motifs (\num{184756}) et de faire calculer la longueur de chaque
      motif. Tous les  motifs ont une longueur impaire.
    \end{enumerate}
  \end{enumerate}
\end{Corrige}
\end{Enonce}

%%% Local Variables:
%%% TeX-master: "olympiades"
%%% End:
