% !-*-coding:utf-8-*-
\begin{Enonce}[Rangement optimal de boîtes dans des casiers]{}
  \def\cerclesIII
  {
    \foreach \y in {1,3,5}
    {
      \filldraw[fill=colLogo!75,draw=colLogo,thick] (1,\y) circle (1) ;
    }
  }
  \def\cerclesVI
  {
    \foreach \y in {1,3,5}
    {
      \filldraw[colLogo!75,draw=colLogo,thick] (1,\y) circle (1) ;
      \begin{scope}[yshift=1cm,xshift=1.732cm]
        \filldraw[colLogo!75,draw=colLogo,thick] (1,\y) circle (1) ;
      \end{scope}
    }
  }

  \Partie{Recherche d’une disposition efficace}

  \begin{enumerate}
  \item
    \begin{figure}[!h]
      \centering
      \begin{tikzpicture}[scale=0.5]
        % 8 rangées de cercles, donc 7\sqrt{3}+1
        \fill[colLogoTeinte!25] (0,0) rectangle (14.12436,9) ;
        \cerclesVI
        \begin{scope}[xshift=3.464cm]%3\sqrt{3}
          \cerclesIII
        \end{scope}
        \begin{scope}[xshift=10.392cm,yshift=1cm]%6\sqrt{3}
          \cerclesIII
        \end{scope}
        \begin{scope}[xshift=12.1246cm]%6\sqrt{3}
          \cerclesIII
        \end{scope}
        \node[below] at (1,-0.25) {$1$} ;
        \node[below] at (2.732,-0.25) {$2$} ;
        \node[below] at (4.464,-0.25) {$3$} ;
        \node[below] at (11.3923,-0.25) {$n-1$} ;
        \node[below] at (13.12436,-0.25) {$n\vphantom{1}$} ;
        \node at (7.928203,1.732) {$\ldots$} ;
        \draw[dashed,thick,colLogoFort] (1,1) --++(30:4) --++(-90:2)
        --++(150:4)--cycle ;
        \draw[dashed,thick,colLogoFort](4.464,1) --++(30:2)
        --++(150:2)  --cycle ;
        \draw[dashed,thick,colLogoFort](13.12436,1) --++(90:2)
        --++(-150:2)  --cycle ;
        \draw[<->,>=stealth,thick,colLogoFort] (0,8) -- (14.12436,8)
        node[midway,rectangle,fill=colLogoTeinte!25]{$L$};
        \draw[<->,>=stealth,thick,colLogoFort] (2.732,6) -- ++(0:1)
        node[midway,above]{$1$};
      \end{tikzpicture}
      \caption{ }
      \label{fig_CleLy19A_01}
    \end{figure}
    \begin{enumerate}
    \item Soit $h$ la hauteur d’un triangle équilatéral de côté $2$,
      montrer que $h$ = $\sqrt{3}$.

    \item On considère $n$ colonnes de disques tangents de rayon $1$
      dans la disposition de la figure \ref{fig_CleLy19A_01}.  Montrer
      que la longueur $L$ occupée par ces $n$ colonnes est égale à
      $2+(n-1)\sqrt{3}$.
    \end{enumerate}
    \item Application 

      Un commerçant souhaite ranger des boîtes cylindriques de rayon $1$
      dans un casier rectangulaire de longueur $26$ et de largeur $12$. En
      partant du coin supérieur gauche il dispose côte à côte, en
      lignes ou en colonnes, le plus grand nombre possible de boîtes.

      Dans la suite du problème, les boîtes sont représentées par des disques de rayon $1$.
      
      Le commerçant hésite entre les trois dispositions suivantes
      (voir la figure \ref{fig_CleLy19_02}).

      \begin{figure}[!h]
        \centering
        \begin{tikzpicture}[scale=0.25]
          \path [use as bounding box] (0,-2) rectangle (28,13) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12);
          \draw[colLogoFort,line width=0.5pt] (-1pt,-1pt) rectangle
          (26cm+1pt,12cm+1pt) ;
          \foreach \x in {1,3,5,24.3}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,11) circle (1) ;
          }
          \foreach \x in {1,3,5,24.3}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,9) circle (1) ;
          }
          \fill[fill=colLogo!75,draw=colLogo] (1,7) circle (1) ;
          \fill[fill=colLogo!75,draw=colLogo] (3,7) circle (1) ;
          \foreach \x in {1,3,24.3}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,1) circle (1) ;
          }
          \node at (13,10) {\ldots} ;
          \node at (13,1) {\ldots} ;
          \node at (2,4.5) {\ldots} ;
          \node at (25,4.5) {\ldots} ;
          \draw[line width=1pt,colLogoTeinte!25] (1,9) rectangle++(2,2) ;
          \draw[<->,>=stealth,shift={(0,-1.2)}]
          (0,0) -- (26,0) node[fill=white,rectangle,midway] {$26$} ;
          \draw[<->,>=stealth,shift={(1.4,0)}]
          (26,0) -- (26,12) node[fill=white,rectangle,midway] {$12$} ;
          \node[below] at (13,-2) {Disposition 1 en carré} ;
        \end{tikzpicture}
        \begin{tikzpicture}[scale=0.25,line width=0.8pt]
          \path [use as bounding box] (0,-2) rectangle (28,14) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12);
          \draw[colLogoFort,line width=0.5pt] (-1pt,-1pt) rectangle
          (26cm+1pt,12cm+1pt) ;
          \foreach \y in {11,9,7}
          {
            \fill[fill=colLogo!75,draw=colLogo] (1,\y) circle (1) ;
          }
          \begin{scope}[shift={(1.732,-1)}]
            \foreach \y in {11,9,7}
            {
              \fill[fill=colLogo!75,draw=colLogo] (1,\y) circle (1) ;
            }
          \end{scope}
          \begin{scope}[shift={(3.464,0)}]
            \foreach \y in {11,9,7} {
              \fill[fill=colLogo!75,draw=colLogo] (1,\y) circle (1) ;
            }
          \end{scope}
          \node at (13,11) {$\ldots$} ;
          \node at (2.732,2) {$\ldots$} ;
          \draw[colLogoTeinte!25] (1,11) --++(0,-2) --++(30:2) --cycle ;
          \node[below] at (13,-1)
          {Disposition 2 en triangles colonnes} ;
        \end{tikzpicture}
        \begin{tikzpicture}[scale=0.25,line width=0.8pt]
          \path [use as bounding box] (0,-2) rectangle (28,14) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12) ;
          \draw[colLogoFort,line width=0.5pt]
          (-1pt,-1pt) rectangle (26cm+1pt,12cm+1pt) ;
          \foreach \x in {1,3,5}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,11) circle (1) ;
          }
          \begin{scope}[shift={(1,-1.732)}]
            \foreach \x in {1,3,5} {
              \fill[fill=colLogo!75,draw=colLogo] (\x,11) circle (1) ;
            }
          \end{scope}
          \begin{scope}[shift={(0,-3.464)}]
            \foreach \x in {1,3,5} {
              \fill[fill=colLogo!75,draw=colLogo] (\x,11) circle (1) ;
            }
          \end{scope}
          \node at (13,11) {$\ldots$} ;
          \node at (2.732,2) {$\ldots$} ;
          \draw[colLogoTeinte!25]
          (1,11) --++(2,0) --++(-120:2) --cycle ;
          \node[below] at (13,-1) {Disposition 3 en  triangles lignes} ;
        \end{tikzpicture}
        \caption{Attention : Les disques situés en bout de lignes ou de colonnes ne
          touchent pas nécessairement les bords du casier.}
        \label{fig_CleLy19_02}
      \end{figure}
      Déterminer la disposition permettant de ranger le plus grand nombre de boîtes.
    \end{enumerate}
    \Partie{Estimation de la proportion de l’aire occupée par les disques}

    \begin{figure}[!h]
      \centering
      ~\hfill
      \begin{tikzpicture}[scale=0.5]
        % \path [use as bounding box] (0,-2) rectangle (28,13) ;
        \foreach \x in {1,3,...,7} { \foreach \y in {1,3,...,5} {
            \draw[colLogoFort,shift={(-1,-1)}] (\x,\y) rectangle
            ++(2,2) ; \fill[fill=colLogo!25,draw=colLogo] (\x,\y)
            circle (1) ; } }
        \node[text width = 4cm,align=center,below] at (4,0) {Pavage par des
          carrés pour la disposition 1.} ;
      \end{tikzpicture}\hfill
      \begin{tikzpicture}[scale=0.5,line width=0.8pt]
        \foreach \x in {1,3,5,7} {
          \begin{scope}[fill=colLogo!50,draw=colLogoFort,shift={(\x,1)}]
            \filldraw[rotate=30] (0:1.1547) --++(120:1.1547)
            --++(-180:1.1547) --++(-120:1.1547) --++(-60:1.1547)
            --++(0:1.1547) --cycle;
          \end{scope}
          \fill[fill=colLogo!25,draw=colLogo] (\x,1) circle (1) ; }
        \begin{scope}[shift={(1,1.732)}]
          \foreach \x in {1,3,5,7} {
            \begin{scope}[fill=colLogo!50,draw=colLogoFort,shift={(\x,1)}]
              \filldraw[rotate=30] (0:1.1547) --++(120:1.1547)
              --++(-180:1.1547) --++(-120:1.1547) --++(-60:1.1547)
              --++(0:1.1547) --cycle;
            \end{scope}
            \fill[fill=colLogo!25,draw=colLogo] (\x,1) circle (1) ; }
        \end{scope}
        \begin{scope}[shift={(0,3.464)}]
          \foreach \x in {1,3,5,7} {
            \begin{scope}[fill=colLogo!50,draw=colLogoFort,shift={(\x,1)}]
              \filldraw[rotate=30] (0:1.1547) --++(120:1.1547)
              --++(-180:1.1547) --++(-120:1.1547) --++(-60:1.1547)
              --++(0:1.1547) --cycle;
            \end{scope}
        
            \fill[fill=colLogo!25,draw=colLogo] (\x,1) circle (1) ; }
        \end{scope}
        \node[text width = 6cm,align=center,below] at (4.5,0){Pavage par
          des hexagones réguliers pour les dispositions 2 et 3.} ;
      \end{tikzpicture}
      \hfill~
      \caption{ }
      \label{fig_CleLy19_03}
    \end{figure}
    On a circonscrit les disques par des polygones (afin de paver
    l’« intérieur » du casier, voir \ref{fig_CleLy19_03})
    On admettra que, pour des casiers de « grandes dimensions », la
    proportion de l’aire totale occupée par les disques dans les
    casiers « se rapproche » de :    
    \[
      P=\frac{\text{Aire  d'un disque}}{\text{Aire d'un polygone}}.
    \]
    \begin{enumerate}
    \item  Déterminer la valeur exacte de $P$ pour la disposition 1
      puis pour les dispositions 2 et 3

    \item Donner une estimation du nombre $n$ de boîtes que
      l’on peut ranger dans de « grands » casiers en fonction de
      l’aire $S$ du casier (on envisagera les cas de la disposition 1
      puis des dispositions 2 et 3).
    \end{enumerate}

    \Partie{Une disposition plus efficace}

    On considère un casier rectangulaire de longueur $444$ et de largeur $4$.

    Trouver une nouvelle disposition permettant de ranger $445$ boîtes
    (on représentera cette nouvelle disposition par un schéma puis on
    déterminera le nombre de boites par le calcul).

    \begin{Corrige}
      \Partie{Recherche d'une disposition efficace}

      \begin{enumerate}
      \item
        \begin{enumerate}
        \item On considère $ABC$ un triangle équilatéral de côté $2$, $H$ le pied
          de la hauteur issue de $A$. $ABH$ est un triangle rectangle,
          on a alors d'après Pythagore que : $BH^2 + AH^2 =
          AB^2$. Soit $h^2  = 4 - 1 = 3$, d'où $h = \sqrt{3}$.
        \item Sur la longueur $L$, il y a $n-1$ triangles équilatéraux
          de côtés $2$ et deux rayons, soit $ 2 + (n-1)\sqrt{3}$.
        \end{enumerate}
        
      \item
        \begin{figure}[!h]
        \centering
        \begin{tikzpicture}[scale=0.25]
          \path [use as bounding box] (0,-2) rectangle (28,13) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12);
          \draw[colLogoFort,line width=0.5pt] (-1pt,-1pt) rectangle
          (26cm+1pt,12cm+1pt) ;
          \foreach \y in {11,9,...,1}
          {
            \foreach \x in {1,3,...,25}
            {
              \fill[fill=colLogo!75,draw=colLogo] (\x,\y) circle (1) ;
            }
          }
          \node[below] at (13,-2) {Disposition 1 en carré} ;
        \end{tikzpicture}
        \begin{tikzpicture}[scale=0.25,line width=0.8pt]
          \path [use as bounding box] (0,-2) rectangle (28,14) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12);
          \draw[colLogoFort,line width=0.5pt] (-1pt,-1pt) rectangle
          (26cm+1pt,12cm+1pt) ;
          \foreach \x in {1,4.464,...,25}
          {
          \foreach \y in {11,9,...,1}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,\y) circle (1) ;
          }
          \begin{scope}[shift={(1.732,-1)}]
            \foreach \y in {11,9,...,3}
            {
              \fill[fill=colLogo!75,draw=colLogo] (\x,\y) circle (1) ;
            }
          \end{scope}
          }
                    \draw[colLogoTeinte!25] (1,11) --++(0,-2) --++(30:2) --cycle ;
          \node[below] at (13,-1) {Disposition 2 en triangles colonnes} ;
        \end{tikzpicture}
        \begin{tikzpicture}[scale=0.25,line width=0.8pt]
          \path [use as bounding box] (0,-2) rectangle (28,14) ;
          \fill[colLogoTeinte!25,line width=0] (0,0) rectangle (26,12) ;
          \draw[colLogoFort,line width=0.5pt]
          (-1pt,-1pt) rectangle (26cm+1pt,12cm+1pt) ;
          \foreach \y in {11,7.5359,...,1}
          {
          \foreach \x in {1,3,...,25}
          {
            \fill[fill=colLogo!75,draw=colLogo] (\x,\y) circle (1) ;
          }
          \begin{scope}[shift={(1,-1.732)}]
            \foreach \x in {1,3,...,24} {
              \fill[fill=colLogo!75,draw=colLogo] (\x,\y) circle (1) ;
            }
          \end{scope}
          }
          \draw[colLogoTeinte!25]
          (1,11) --++(2,0) --++(-120:2) --cycle ;
          \node[below] at (13,-1) {Disposition 3 en  triangles lignes} ;
        \end{tikzpicture}
        \caption{}
        \label{fig_CleLy19_02C}
      \end{figure}

        \begin{itemize}
        \item Pour la disposition en carré. Il y a $13$ disques sur
          une largeur et $6$ sur la hauteur, soit $13 \times 6 = 78$.
        \item En largeur, $n$ doit vérifier : $2 + (n-1)\sqrt{3} =
          26$, soit $n = 8 \sqrt{3}+1 $ soit $14$ cercles.

          Verticalement, il y a $6$ disques, une colonne sur $2$
          comptant $5$ disques. Soit au total $7 (6+5) = 77$ disques.
        \item Horizontalement, il y $13$ disques sur la première ligne
          et $12$ sur la deuxième ligne. Verticalement,
          $2(n-1)\sqrt{3} = 12$, soit $n = \frac{10 \sqrt{3}+3}{3} =
          6$ disques. Au total, on a $3(13+12) = 75$.
        \end{itemize}
        La première configuration est plus remplie que les deux autres.
      \end{enumerate}

      \Partie{Proportion d'aire occupée par les disques}
      \begin{enumerate}
      \item
        \begin{itemize}
        \item Pour la configuration 1, $P =  \frac{\pi }{4} =
          \frac{\pi}{4} \approx 0,7854$.
        \item Pour les dispositions 2 et 3. On note $c$ le côté de
          l'héxagone, il vérifie, $c^2  =  1 + \frac{c^2}{2}$, soit $c
          = \frac{2}{\sqrt{3}}$. Donc, l'aire d'un hexagone est donc $
          6 \times \frac{2}{\sqrt{3}} \times \frac{1}{2} = 2
          \sqrt{3}$.
          
          $P' = \frac{\pi }{2 \sqrt{3}} = \frac{\pi \sqrt{3}}{6}
          \approx 0,9069 $.
        \end{itemize}
      \item Quand $n$ est grand on approche le rapport entre l'aire
        $a$ occupée et l'aire $A$ du casier est proche de $P$. Soit
        $P \approx \frac{a}{A}$. Comme les disques ont une aire de $\pi$, on
        en déduit que $a = n\pi$ et donc que $P \approx \frac{n\pi}{A}$ soit
        $n \approx \frac{PA}{\pi} $
        \begin{itemize}
        \item Pour la dispositon $1$, cela donne $n \approx
          \frac{A}{4} $.
        \item Pour les dispositions $2$ et $3$ cela donne $ n \approx
          \frac{A \sqrt{3}}{6}$.
        \end{itemize}
      \end{enumerate}
      
      \Partie{Une disposition plus efficace}

      On décale un bloc de $3$ triangles Verticalement. On note $z$,
      ce décalage, et $y$ la distance horizontale entre deux centres,
      qui sont séparés de $2$ (voir la figure \ref{fig_CleLy19_03C}).

      Verticalement, on a alors : $1 + z + \sqrt{3} + 1 = 4$, soit $z
      = 2 - \sqrt{3}$.
      
      Alors $y^2+z^2 = 4$, ce qui donne $y =  \sqrt{4 - z^2} =
      \sqrt{4\sqrt{3}-3}$.

      En retirant le premier disque (plein  sur la
      figure) et $7$ disques qui occupe une largeur de $2y$. Ce bloc
      ce répète, $ (2+2y)r = 442$, soit $r = \frac{442}{2+2y} \approx
      74$.

      Il y a donc $1$ disque (plein), $5$ disques complets dans un
      motif, et deux demi-disques, soit $1+74 \times 5 + 74 = 455$
      disques. 
      \begin{figure}[!h]
        \centering
        \def\troiscercles{%
          \draw (1,1) circle (1) ; \fill (1,1) circle (1pt) ; \draw
          (3,1) circle (1) ; \fill (3,1) circle (1pt) ; \draw
          (2,2.732) circle (1) ; \fill (2,2.732) circle (1pt) ; }
        \def\y{2.98197} \def\z{0.2672} \def\x{7.963939}
        \begin{tikzpicture}
          \draw[colLogoFort,line width=1pt] (-0.5pt,0) --++(0,4)
          --++(\x,0) --++ (0,-4) ;
          \begin{scope}[draw=colLogoFort]
            \troiscercles \fill[colLogo] (1,1) circle (1) ;
          \end{scope}
          \begin{scope}[draw=colLogoTeinte,shift={(\y,\z)}, rotate
            around={180:(2,1.866)}]
            \troiscercles \draw[colLogo,line width = 1pt](1,1) --
            (3,1) -- (2,2.732) --cycle ; \coordinate (a) at (2,2.732)
            {} ;
          \end{scope}
          \fill[colLogoTeinte,text=black] (3,1) -- (a)
          node[midway,above] {$2$} --++(0,-\z) node[midway,right]
          {$z$} -- cycle node [midway,below] {$y$} ;
          \begin{scope}[draw=red,shift={(2*\y,0)}]
            \troiscercles
          \end{scope}
        \end{tikzpicture}
        
        \caption{ }
        \label{fig_CleLy19_03C}
      \end{figure}
    \end{Corrige}
\end{Enonce}


\begin{Enonce}[Se suivre sans perdre un chiffre]{}
  
  Soit $k$ un entier naturel non nul. Pour tout entier $n$ non nul et
  pour tout entier naturel $a$, on dit que la suite
  $\left(a\,;\,a+1\,;\,a+2\,;\,{\dots}\,;\,a+n-1\right)$ de $n$ nombres
  entiers consécutifs est $k$-complète de longueur $n$ si,
  en écriture décimale, ces $n$ nombres ont chacun $k$
  chiffres et que chaque chiffre de 0 à 9 apparaît au moins
  une fois dans l’écriture de l’un d’eux.

  Par exemple, la suite
  $(10\,;\, 11\,;\, 12\,;\, 13\,;\, 14\,;\, 15\,;\, 16\,;\, 17\,;\,
  18\,;\, 19)$ est $2$-complète de longueur $10$, tandis que
  $(34\,;\, 35\,;\, 36\,;\, 37\,;\, 38)$ n’est pas $2$-complète car
  les chiffres 0, 1, 2 et 9 n’apparaissent dans aucun entier de cette
  suite.

  On dit qu’une suite $k$-complète est \textbf{minimale} s’il n’existe
  pas de suite $k$-complète de longueur strictement inférieure. Par
  exemple, la première suite $2$-complète donnée en exemple n’est pas
  minimale car
  $(90\,;\, 91\,;\, 92\,;\, 93\,;\, 94\,;\, 95\,;\, 96\,;\, 97\,;\,
  98)$ est elle aussi $2$-complète, de longueur $9$.

  Le but de cet exercice est de déterminer la longueur de ces suites
  $k$-complètes minimales, et de les dénombrer.

  On rappelle que l’écriture décimale d’un entier non nul ne commence
  pas par le chiffre 0.


\Partie{Longueur minimale d’une suite $k$-complète}

\begin{enumerate}
\item Dans cette question, on considère des nombres entiers à un
  chiffre.
  \begin{enumerate}
  \item Écrire toutes les suites $1$-complètes possibles. Aucune
    justification n’est attendue.

  \item En déduire le nombre de suites $1$-complètes minimales ainsi
    que leur longueur.
  \end{enumerate}
\item Soit $k \geq 10$. Proposer une suite $k$-complète minimale, et
  indiquer sa longueur.

\item Donner la longueur minimale d’une suite $9$-complète.

\item Dans cette question, $k=3$.
  \begin{enumerate}
  \item Donner un exemple de suite $3$-complète de longueur $7$.

  \item Expliquer pourquoi aucune suite de $6$ entiers consécutifs
    comportant trois chiffres ne peut être $3$-complète.
  \end{enumerate}
\item On considère dans cette question que le nombre $k$ de chiffres
  vérifie $2 \leq k \leq 8$.

  Démontrer que les suites $k$-complètes minimales sont de longueur
  $10-k$.
\end{enumerate}

\Partie{Dénombrement des suites $k$-complètes minimales}

\begin{enumerate}
\item  Combien de nombres entiers à dix chiffres peut-on écrire
  en utilisant une et une seule fois chaque chiffre de $0$ à $9$ ? (on
  pourra commencer par déterminer le nombre de possibilités pour le
  chiffre le plus à gauche). En déduire le nombre de suites
  $10$-complètes minimales.

\item Soit $n=4$. On considère une suite $4$-complète minimale
  quelconque, commençant par l’entier $a$. Cette suite est donc de
  longueur $6$.

  \begin{enumerate}
  \item  Montrer que le chiffre des dizaines ne peut pas être le
    même pour tous les nombres d’une suite $4$-complète minimale. En
    déduire les chiffres des unités possibles pour l’entier $a$.

  \item Déterminer le nombre de possibilités pour le chiffre des
    dizaines de l’entier $a$, en fonction de son chiffre des unités.

  \item Déterminer le nombre de possibilités pour les chiffres des
    centaines et des milliers de l’entier $a$, en sachant que la
    suite de $6$ entiers consécutifs commençant par $a$ est $4$-complète
    minimale.

  \item Démontrer qu’une telle construction donne bien toujours le
    premier nombre entier d’une suite $4$-complète minimale.

  \item Déterminer le nombre de suites $4$-complètes minimales.
  \end{enumerate}
\item Soit $2 \leq k \leq 8$. Démontrer que le nombre de suites
  $k$-complètes minimales est :
\[
  \left(9-k\right)\times 1\times 2\times 3\times {\cdots}\times
  \left(k-1\right).
\]
\item Montrer que le nombre de suites $9$-complètes minimales est
  \num{579600}.
\end{enumerate}
\begin{Corrige}
  \Partie{Longueur minimale d'une suite $k$-complète}
  \begin{enumerate}
  \item
    \begin{enumerate}
    \item Il n'y a qu'une suite $1$-complète, elle est de longueur
      $10$ : $\lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \rbrace$.
    \item La suite $1$-complète minimale est la seule suite
      $1$-complète précédente.
    \end{enumerate}
  \item Les suites minimales $k$-complètes sont de longueur $1$, avec
    des nombres de $k$ chiffres comportant tous les chiffres. Par
    exemple $\lbrace 1234567890\ldots0 \rbrace$, avec $k-9$ zéro.
  \item Une suite $9$-complète comporte forcément au moins deux
    nombres. La suite $\lbrace \num{123456789}, \num{123456790} \rbrace$
  \item 
    \begin{enumerate}
    \item La suite $\lbrace 234, 235, 236, 237, 238, 238, 240 \rbrace
      $ est une suite $3$-complète de longueur $7$.
    \item Avec $6$ nombres consécutifs, on ne peut pas couvrir une
      dizaine. On est au maximum sur deux dizaines consécutives.

      Avec tous le même chiffre des centaines, il y a alors
      $9 = 6 + 2 + 1$ chiffres différents.

      Si le chiffre des centaines est différent, alors un des nombres
      doit comporter deux fois le chiffre $9$ et le suivant se termine par
      $00$. Donc, on a $8$ chiffres qui apparaissent : $6 + 2$.
    \end{enumerate}
  \item Suite $8$-complète $\lbrace \num{12345679}, \num{12345680}\rbrace$, on ne
    peut pas faire mieux. Un seul nombre de $8$ chiffres ne pouvant
    contenir tous les chiffres. Toute permutation de $\num{123456}$
    permettant de faire une autre suite. Par contre les deux derniers
    chiffres sont obligatoires, car il faut être sur un changement de
    dizaine, on ne peut pas prendre un des six premiers chiffres, un
    doublement de chiffres n'étant pas rentable. Ces quatres chiffres
    étant tous distincts.

    Suite $7$-complète $\lbrace \num{2345679}, \num{2345680}, \num{23456781}\rbrace$
    Le changement de dizaine est optimal, la partie $\num{23456}$ l'est
    aussi, sinon, on double un chiffre ce qui conduit à rajouter un
    nombre.

    Suite $6$-complète $\lbrace \num{345679}, \num{345680}, \num{345681}, \num{345682}\rbrace$
    
    Suite $5$-complète $\lbrace \num{45679}, \num{45680}, \num{45681}, \num{45682}, \num{45683}\rbrace$

    Suite $4$-complète $\lbrace \num{5679}, \num{5680}, \num{5681}, \num{5682}, \num{5683}, \num{5684}\rbrace$

    Suite $4$-complète $\lbrace 679, 680, 681, 682, 683, 684, 685\rbrace$

    La suite $2$-complète $\lbrace 79, 80, 81, 82, 83, 84, 85, 86
    $ est minimale. 

    on démontre, de même que les suites précédentes sont minimum. Il
    faut un changement de dizaine, et le changer à $80$ est optimum
    car il n'y a pas de nombre avec un deux chiffres identiques. 
  \end{enumerate}

\Partie{Dénombrement des suites $k$-complètes minimales}

\begin{enumerate}
\item Pour le chiffre le plus à gauche, il y a $9$ possibilités, tous
  les chiffres non nuls ; pour le deuxième chiffre, il y a encore $9$,
  tous les chiffres non nuls, plus le zéros. Ensuite, on enlève, cela
  décroît.
 
  \FPeval\tempa{clip(9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2)}
  Donc, le nombre de suite $10$-complète est donc $ 9 \times 9! =
  \num{\tempa}$. 
\item
  \begin{enumerate}
  \item Sans changement de dizaine, une suite $4$-complète minimale,
    n'apporte que $6$ chiffres distincts pour les unités, plus le
    chiffre des dizaines, soit $7$ chiffres. Les dizaines et milliers
    étant constantes, elles n'apportent que deux chiffres, soit $9$
    chiffres. Pour qu'elle soit minimale, une suite de $4$-complète
    doit changer de dizaine. Le chiffre des unités peut donc prendre
    les valeurs $5$, $6$, $7$, $8$, $9$.
  \item Soit $u$ un chiffre compris entre $5$ et $9$. Les six nombres
    de la suite $4$-complète minimale, apporte $6$ chiffres
    distincts, entre $u$ et $u+6$. 
    \begin{description}
    \item[$5$] : $6$, $7$, $8$, $9$, $0$ ; $d$ doit être $1$, $2$,
      $3$, $4$. Mais $4$ est exclu, car alors, on retrouve $5$ au
      changement de valeur, ce qui n'apporte pas de valeurs nouvelles
    \item[$6$] : $7$, $8$, $9$, $0$, $1$ ; $d$ doit être $2$,
      $3$, $4$, $5$, sauf $5$
    \item[$7$] : $8$, $9$, $0$, $1$, $2$ ; $d$ doit être $3$, $4$,
      $5$, $6$ sauf $6$.
    \item[$8$] : $9$, $0$, $1$, $2$, $3$ ; $d$ doit être $4$,
      $5$, $6$, $7$. sauf $7$.
    \item[$9$] : $0$, $1$, $2$, $3$, $4$ ; $d$ doit être $5$, $6$,
      $7$, $8$., sauf $8$.
    \end{description}
    Au final, si on choisit $u$, le chiffre des unités est $u-4$, ou
    $u-3$ ou $u-2$
  \item Il reste à choisir les deux premiers chiffres, parmi les
    chiffres qui reste, qui ne sont que deux. Donc, un seul choix et
    deux possibilités par permutation. 
  \end{enumerate}

\end{enumerate}
\end{Corrige}
\end{Enonce}

\begin{Enonce}[Triangles en somme]{}
  On construit des triangles de la façon suivante : 
  \begin{itemize}
  \item  $n$ étant un entier naturel non nul, on écrit
  \item sur la première ligne les entiers naturels consécutifs de $1$ à
    $n$.
  \item À partir de la deuxième ligne, on place les entiers obtenus en 
    faisant la somme des deux entiers situés au-dessus.
  \item On s’intéresse au nombre isolé qui sera situé à la dernière
    ligne du triangle. On désigne par $S_n$ ce dernier nombre.
  \end{itemize}

  L’objectif du problème est de calculer $S_{2019}$. 


  \begin{enumerate}
  \item Étude sur quelques exemples

  Voici les premiers triangles obtenus pour  $n=2$, $n=3$, $n=4$.

  \begin{center}
    ~\hfill
    \begin{tikzpicture}[baseline]
      \node[above] at (0.5,0.5) {$n=2$} ;
      \node at (0,0) {1} ;
      \node at (1,0) {2} ;
      \node at (0.5,-1) {3} ;
    \end{tikzpicture}
  \hfill
  \begin{tikzpicture}[baseline]
    \node[above] at (1,0.5) {$n=3$} ;
    \node at (0  , 0) {1} ;
    \node at (1  , 0) {2} ;
    \node at (2  , 0) {3} ;
    \node at (0.5,-1) {3} ;
    \node at (1.5,-1) {5} ;
    \node at (1  ,-2) {8} ;
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}[baseline]
    \node[above] at (1.5,0.5) {$n=4$} ;
    \node at (0  , 0) {1} ;
    \node at (1  , 0) {2} ;
    \node at (2  , 0) {3} ;
    \node at (3  , 0) {4} ;
    \node at (0.5,-1) {3} ;
    \node at (1.5,-1) {5} ;
    \node at (2.5,-1) {7} ;
    \node at (1  ,-2) {8} ;
    \node at (2  ,-2) {12} ;
    \node at (1.5,-3) {20} ;
  \end{tikzpicture}
  \hfill~
\end{center}


%\Sn{20}
% \begin{tikzpicture}
%   \node at (0,0) {1} ;
%   \node at (1,0) {2} ;
%   \node at (2,0) {3} ;
%   \node at (3,0) {4} ;
%   \node at (4,0) {5} ;
%   \node at (0.5,-1) {3} ;
%   \node at (1.5,-1) {5} ;
%   \node at (2.5,-1) {7} ;
%   \node at (3.5,-1) {9} ;
%   \node at (1,-2) {8} ;
%   \node at (2, -2) {12} ;
%   \node at (3, -2) {16} ;
%   \node at (1.5,-3) {20} ;
%   \node at (2.5,-3) {28} ;
%   \node at (2,-4) {48} ;
% \end{tikzpicture}


\begin{enumerate}
\item  Donner pour chacun d’eux le nombre $S_n$ correspondant.

\item Construire les triangles obtenus pour $n=5$ puis $n=6$. Donner
  leur nombre de lignes ainsi que les valeurs de $S_5$ et $S_6.$
\end{enumerate}


\item Construction des lignes

La première ligne d’un triangle est construite de la façon suivante :

\begin{itemize*}[itemjoin=\hfill;\hfill,label={}]
\item 1
\item 2
\item 3
\item {\dots}
\item $p-1$
\item $p$
\item $p+1$
\item {\dots}
\item {\dots}
\item $n-1$
\item $n$
\end{itemize*}

où  $p-1$,  $p$, $p+1$ désignent trois entiers naturels consécutifs. 

\begin{enumerate}
\item  Justifier que dans la deuxième ligne du triangle, la
  différence entre deux entiers placés côte à côte est égale à $2$.

\item Justifier que dans la troisième ligne du triangle, la différence
  entre deux entiers consécutifs placés côte à côte est égale à $4$.

\item Expliquer que, dans ligne numéro $p$ du triangle, la différence
  entre deux entiers placés côte à côte est égale à $2^{p-1}$.

\item On remarquera que chaque ligne possède un nombre en moins que la
  ligne placée au-dessus, et que chaque ligne numéro $p$ commence par
  $S_p$. (On ne demande pas de démontrer ce résultat).

  On suppose que la ligne numéro 1 possède $n$ nombres
  entiers. Combien de nombres contient la ligne numéro $p$ .
  Justifier.

\item En déduire que sur ligne numéro $p$ du triangle, on trouve de
  gauche à droite les nombres :
  
\begin{itemize*}[itemjoin=\hfill;\hfill,label={}]
\item $S_p$
\item $S_p+2^{p-1}$
\item $S_p+2\times 2^{p-1}$
\item {\dots}
\item $S_p+(n-p)\times 2^{p-1}$
\end{itemize*}
\end{enumerate}


\item Algorithme permettant d’obtenir  $S_n$.
  \begin{enumerate}
  \item  Déterminer une relation exprimant $S_n$ en fonction de
    $S_{n-1}$.

  \item Compléter l’algorithme ci-dessous pour qu’il affiche en sortie
    le nombre $S_n$.
    \begin{algorithm}[!h]
      Saisir une valeur pour $N$

     $S\leftarrow $ \ldots

     \For{ $k$ allant \ldots à \ldots}
     {
        $S\leftarrow $ \ldots
      }
      
      Afficher $S$ 
    \end{algorithm}

\end{enumerate}

\item Utiliser votre calculatrice pour calculer  $S_{20}$. 


\end{enumerate}

\item  Calcul de $S_{2019}$. 

  \begin{enumerate}
  \item À l’aide de la relation obtenue à la question
    \textbf{3. a.} démontrer que pour tout
    $n{\geq}2$, $S_n$ est divisible par $2^{n-2}$.

  \item Déterminer une relation exprimant $S_n$ en fonction de $n$.
    Qu’obtient-on pour $S_6$ et $S_{20}$ ?
  \item En déduire la valeur exacte de $S_{2019}$.
  \end{enumerate}
  \begin{Corrige}
    \newcommand\Sn[1]{%
\xdef\Diff{1}
\xdef\Deb{1}
\def\depart{#1}
\FPeval\depart{\depart-1}
\FPeval\suivant{\depart-1}
\foreach \x in {\depart,\suivant,...,1}
{
  \xdef\nb{\Deb}
  \foreach \y in {0,1,...,\x}
  {
    \FPeval\tempc{clip(\Deb+\y*\Diff)}
    \xdef\nb{\tempc}
    \nb,
    \ifnum\y=0
    \xdef\nba{\nb}
    \fi
    \ifnum\y=1
    \FPeval\tempb{clip(\nba+\nb)}
    \xdef\nbb{\tempb}
    \fi
  }
  \FPeval\tempb{clip(\Deb+\Deb*\Diff)}
  \xdef\Deb{\nbb}
  \FPeval\tempa{clip(\Diff*2)}
  \xdef\Diff{\tempa}
  \par
}
\Deb}

    \begin{enumerate}
    \item
      \begin{enumerate}
      \item $S_2 =3$, $S_3 = 8$ et $S_4=20$.
      \item On obtient :
        \begin{multicols}{2}
          \Sn{5}
          
          \columnbreak
          \Sn{6}
        \end{multicols}
        $S_5 = 48$ et $S_6=112$
      \end{enumerate}
    \item
      \begin{enumerate}
      \item On considère trois nombres consécutifs sur la première
        ligne : $p-1$, $p$ et $p+1$. Alors les deux nombres sur la
        deuxième ligne sont $2p-1$ et $2p+1$ dont la différence est
        $2$.
      \item Trois nombres consécutifs sur la deuxième ligne, $2k-1$,
        $2k+1$ et $2k+3$. Les nombres sur la troisième ligne sont :
        $4k$ et $4k+4$. La différence est donc de $4$.
      \item Sur la 4\ieme{} ligne, la différence sera de $8 = 2^3$ ;
        sur la 5\ieme{} ligne, la différence sera de $16 = 2^4$ ; sur
        la $p$\ieme{}, la différence sera de $2^{p-1}$.
      \item La première possède $n$ nombres, la 2\ieme{} possède
        $n-1$, la 3\ieme{} $n-2$ ; la $p$\ieme{} possède $n-p + 1$.
      \item Sur la $p$\ieme{} ligne commence par $S_n$, le 2\ieme{}
        est augmenté de $2^{p-1}$, le 3\ieme{} de $2 \times 2^{p-1}$,
        le dernier sera augmenté de $(n-p)\times 2^{p-1}$. Il y a bien
        $n-p+1$ nombres sur cette ligne. 
      \end{enumerate}
    \item
      \begin{enumerate}
      \item $S_n$ est la somme des deux nombres sur la précédente
        ligne, soit $S_{n-1}$ et $S_{n-1}+2^{p-2}$, d'après la
        question précédente.

        On a donc $S_n = 2S_n+2^{p-2}$.
      \item On obtient
        \begin{algorithm}[!h]
      Saisir une valeur pour $N$

     $S\leftarrow 0$ 

     \For{ $k$ allant $1$ à $N-1$}
     {
        $S\leftarrow 2*S + 2^{k-1}$ 
      }
      
      Afficher $S$ 
    \end{algorithm}
  \item On obtient \num{5505024}.
      \end{enumerate}
    \item
      \begin{align*}
        S_n &=  2S_{n-1} + 2^{n-2}  \\
            & =2^2S_{n-2} + 2^{n-2}+2^{n-2} = 2^2S_{n-2} + 2 \times
              2^{n-2} \\
            &= 2^3S_{n-3} + 3 \times 2^{n-2}\\
            & = \ldots\\
            & = 2^{n-2} S_{2} + (n-2) \times 2^{n-2}
      \end{align*}
      On en déduit que $S_n$ est divisible par $2^{n-2}$.
    \item On a donc $S_n = 2^{n-2}(3 + n-2) = 2^{n-2}(n+1)$.

      Soit $S_6 = 2^4 \times 7 = 112$ et $S_{20} = 2^{18} \times 21 =
      \num{5505024}$.
    \item On en déduit la valeur de $S_{2019} = 2^{2017} \times 2020$.
    \end{enumerate}
  \end{Corrige}
\end{Enonce}


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

