\documentclass[12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[a4paper, margin=2cm]{geometry}
\usepackage{amsmath}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{color}
\usepackage[hidelinks]{hyperref}
\usepackage[framemethod=TikZ]{mdframed}

\renewcommand*{\proofname}{Solution}

\newenvironment{theo}[1][]{%
\mdfsetup{%
    frametitle={%
        \tikz[baseline=(current bounding box.east),outer sep=0pt]
        \node[anchor=east,rectangle,fill=blue!20]
        {\strut Énoncé};}
    }%
\mdfsetup{%
    innertopmargin=10pt,linecolor=blue!20,%
    linewidth=2pt,topline=true,%
    frametitleaboveskip=\dimexpr-\ht\strutbox\relax%
}

\begin{mdframed}[]\relax}{%
\end{mdframed}}

\newenvironment{lemma}[1][]{%
\mdfsetup{%
    frametitle={%
        \tikz[baseline=(current bounding box.east),outer sep=0pt]
        \node[anchor=east,rectangle,fill=red!20]
        {\strut Lemme};}
    }%
\mdfsetup{%
    innertopmargin=10pt,linecolor=red!20,%
    linewidth=2pt,topline=true,%
    frametitleaboveskip=\dimexpr-\ht\strutbox\relax%
}

\begin{mdframed}[]\relax}{%
\end{mdframed}}

\newmdenv[
  topline=false,
  bottomline=false,
  rightline=false,
  skipabove=\topsep,
  skipbelow=\topsep
]{siderules}

\title{Problème 5}
\author{Théophile Cailliau}
\date{}

\begin{document}

\maketitle

\begin{theo}
    Soit $N\geq 3$ un entier et une permutation $P$ de $\llbracket 1, N\rrbracket$ choisie au hasard (chaque permutation est équiprobable). Nous relions les points
    \[
        (1, 42^{P[1]}), (2, 42^{P[2]}), \dots, (N, 42^{P[N]})
    \]
    dans cet ordre afin d'obtenir un polygone. Quelle est la probabilité que le polygone obtenu soit convexe ?
\end{theo}

\begin{proof}
    On montre le lemme suivant:
    \begin{lemma}
        Pour tout $a<b<c$ de $\mathbb N^*$, on a $42^b-42^a<42^c-42^b$.

        \renewcommand*{\proofname}{Démonstration}
        \begin{proof}
            $\qquad\qquad 42^b-42^a<42^b<42^b(42^{c-b}-1)=42^c-42^b$
        \end{proof}
    \end{lemma}
    Ce lemme montre que pour tout triplet $(a, b, c)\in\mathbb N^*^3$ avec $a<b<c$, si on note $A(k, 42^a), B(k+1, 42^b), C(k+2, 42^c)$, alors $(\overrightarrow{BC}, \overrightarrow{BA})<180^\circ$. Le contraire est aussi vrai (si on a $a>b>c$ alors l'angle est plus petit que $180^\circ$).

    Puisque la convexité est inchangée par symétrie, si une permutation génère un polygone convexe alors la permutation avec les éléments dans l'ordre inverse génère aussi un polygone convexe.

    Pour toute permutation, on peut trouver un ensemble de sous-suites dont la concaténation donne la permutation. On prend un tel ensemble tel que les sous-suites sont maximales et strictement monotone. On voit facilement que si l'on peut trouver trois telles sous-suites, alors le polygone n'est pas convexe. Par conséquent, on ne s'intéresse qu'aux permutation dont la monotonie ne change qu'une fois ou moins.

    Il y a trois cas:
    \begin{itemize}
        \item Il n'y a qu'une seule suite monotone

            Cela ne génère que $2$ configuration convexe, puisqu'on doit choisir $\binom NN$ éléments et les ordonner et on peut les ordonner de deux manière différentes (l'argument de symétrie ne s'applique pas, puisque les deux permutations obtenues sont symétriques)
        \item La première suite est croissante, la deuxième décroissante.

            On note la permutation $P=(a_1,a_2,a_3,a_4, \cdots, a_n)$. Si on a $a_1<a_2<\cdots <a_k$ et $a_k>\dots>a_n$, alors le polygone n'est pas convexe sauf pour le cas particulier $k=2$, $N=3$ pour lequel cela génère $2$ permutations convexes (c'est le seul cas pour lequel le lemme ne s'applique pas).

        \item La première suite est décroissante, la deuxième est croissante

            Soit $(a_n)_{1\leq n\leq k}$ la première suite et $(b_n)_{k+1\leq n\leq N}$ la deuxième. Alors par le lemme, la permutation est convexe ssi on a $a_k<b_{k+1}$ (on ne peut pas avoir l'égalité). Cela revient en fait à dire que l'on prend le maximum d'éléments dans la première suite. On aura forcément $a_k=1$, par définition des deux suites.
            
            Pour la première suite, on a $\binom {N-1}{k-1}$ choix (on exclus $1$) et cela détermine la deuxième. Pour ne pas traiter le premier cas deux fois, on obtient $\sum_{k=2}^{N-1}\limits \binom {N-1}{k-1}=2^{N-1}-2$

            % TODO: compter

    \end{itemize}

    \noindent Il y a donc $2^{N-1}-2+2=2^{N-1}$ permutations convexes. La probabilité recherchée est donc \[
        p=\frac{2^{N-1}}{N!}\text{ pour }N>3
    \]
    et $p=1$ pour $N=3$.

\end{proof}
\end{document}
