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

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

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 %\maketitle
 \thispagestyle{empty}
  \sujet{Fractions égyptiennes (ENS Lyon, Maths-Info)}
  \texte
   Les égyptiens, pour représenter une fraction, n'utilisaient que des sommes
   d'inverses d'entiers tous distincts. Par exemple,
   ${\displaystyle\frac{5}{6}=\frac{1}{2}+\frac{1}{3}}$.
  \unequestion
   Décomposer ${\displaystyle\frac{10}{13}}$.
   Cette décomposition est-elle unique?
  \unequestion
   Montrer que, pour ${\displaystyle r\in]0,1[\cap\Q}$, une telle écriture
   est toujours possible.
  \unequestion
   Proposer un algorithme décomposant ${\displaystyle\frac{a}{b}}$
   avec $0<a<b$.
  \unequestion
   Cas où $r\geq1$.
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
  \texte
   On propose trois méthodes de calcul d'un développement égyptien
   de $r\in]0,1[\cap\Q$.
  \cquestion
   La première méthode consiste à faire évoluer un
   \emph{développement partiel} de $r$, {\cad} une suite croissante
   $D=(x_1,\dotsc,x_m)$ d'entiers telle que
   $$r=\frac{1}{x_1}+\dotsb+\frac{1}{x_m}\text{.}$$
   Au départ, si ${\displaystyle r=\frac{a}{b}}$ où $0<a<b$, on pose
   $$D=(\underbrace{b,\dotsc,b}_{a})\text{.}$$
   Le développement $D=(x_1,\dotsc,x_m)$ est égyptien si ses éléments
   sont tous distincts.
   Tant que ce n'est pas le cas, on choisit $k$ tel que $x_k=x_{k+1}$ et
   \begin{itemize}
    \item si $x_k$ est pair, on remplace $x_k$ par
          ${\displaystyle\frac{x_k}{2}}$ et on supprime $x_{k+1}$;
    \item si $y=x_k$ est impair, on utilise l'identité
          $$\frac{2}{y}=\frac{1}{(y+1)/2}+\frac{1}{y(y+1)/2}\text{,}$$
          autrement dit, on supprime de $D$ $x_k$ et $x_{k+1}$ et
          on les remplace par $(y+1)/2$ et $y(y+1)/2$.
   \end{itemize}
   Si on munit l'ensemble des suites finies d'entiers naturels de l'ordre
   lexicographique, poids fort en tête, le développement $D$
   diminue strictement à chaque étape. Cela prouve l'arrêt de
   l'algorithme.\par
   Avec cette méthode, on obtient 
   $$\frac{10}{13}=\frac{1}{2}+\frac{1}{7}+\frac{1}{14}+
    \frac{1}{23}+\frac{1}{91}+\frac{1}{2093}\text{.}$$
  \cquestion
   La deuxième méthode de développement de ${\displaystyle r=\frac{a}{b}}$
   est un algorithme glouton dû à Fibonacci.\par
   Si $r=0$, c'est fini. Sinon, on pose 
   ${\displaystyle p=\left\lceil\frac{1}{r}\right\rceil}$, de sorte que
   ${\displaystyle\frac{1}{p}}$ est maximum vérifiant
   ${\displaystyle\frac{1}{p}\leq r}$. On continue ensuite
   avec ${\displaystyle r'=r-\frac{1}{p}}$.\par
   On montre que les dénominateurs $p$ obtenus forment une
   suite strictement croissante: Si $r'\neq0$, en notant
   ${\displaystyle p'=\left\lceil\frac{1}{r'}\right\rceil}$, il vient
   ${\displaystyle\frac{1}{p'}\leq r-\frac{1}{p}<\frac{1}{p-1}-\frac{1}{p}}$;
   d'où $p'>p(p-1)\geq p$.\par
   Pour montrer la terminaison, il suffit de remarquer que le numérateur
   de ${\displaystyle r'=\frac{ap-b}{pb}}$ est $<$ à celui de
   ${\displaystyle r=\frac{a}{b}}$, ce qui se déduit de l'inégalité
   ${\displaystyle\frac{a}{b}<\frac{1}{p-1}}$.\par
   On obtient par exemple
   $$\frac{10}{13}=\frac{1}{2}+\frac{1}{4}+\frac{1}{52}\text{.}$$
  \cquestion
   Pour la troisième méthode, si $a$ et $b$ sont premiers entre eux,
   il existe $b'\in[|0,b-1|]$ vérifiant $ab'\equiv1\mod b$ puis $a'$
   tel que $ab'=1+a'b$. Alors
   ${\displaystyle\frac{a}{b}=\frac{1}{bb'}+\frac{a'}{b'}}$ et on continue.
   \par
   Les dénominateurs $bb'$ obtenus forment une suite strictement
   décroissante car $b''<b'<b$ donc $b'b''<bb'$.\par
   Enfin la méthode termine car car $b'<b$.\par
   Par exemple
   $$\frac{10}{13}=
    \frac{1}{52}+\frac{1}{12}+\frac{1}{6}+\frac{1}{2}\text{.}$$ 
  \cquestion
   Montrons que tout $r\in\Q_+^*$ est développable en fractions égyptiennes.
   Comme la série harmonique diverge, il existe un entier $n$ vérifiant
   $$\sum_{k=2}^{n}\frac{1}{k}\leq r\text{ et }
    \sum_{k=2}^{n+1}\frac{1}{k}>r\text{.}$$
   Ainsi
   $$r=\sum_{k=2}^{n}\frac{1}{k}+r'\text{ avec }0\leq r'<\frac{1}{n+1}\text{.}$$
   Les dénominateurs d'un développement de $r'$ en fractions égyptiennes
   sont donc $>n+1$ et on obtient ainsi un développement de $r$.
\end{parenthese}\end{document}

