\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
\usepackage{ifpdf}
\usepackage{makeidx}
\usepackage{graphicx}
%\ifpdf
 %\usepackage[pdftex,colorlinks]{hyperref}
%\else
 %\usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
 %\fi
\newtheorem{rem}{Remark}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\atan}{{\mbox{atan}}}
%\input{giac.tex}
%\giacmathjax
\title{Le concours des crapauds et un exemple d'une suite fractale nommée "suite des batracions"}
\author{Ren\'ee De Graeve}
\date{2020}
\begin{document}
\maketitle
\newpage
%gregre.xws
%greconv.xws et grenouille4.xws
%grecomb16.xws
%greconcour.xws
%greGmil.xws
\section*{Avant-propos}
Le point de d\'epart de ce document est de r\'esoudre le {\bf "Probl\`eme 40"} 
intitul\'e : {\bf  Cartes grenouilles et suites fractales} du livre 
{\bf "Oh, encore des nombres !"}  de Clifford A. Pickover chez Dunod.\\
Les batracions sont des suites qui font penser au  parcours de crapauds qui 
vont d'un nénuphar à l'autre...\\
{\bf La premi\`ere partie} est constitu\'ee d'exercices de programmation d\'estin\'es
\`a des \'el\`eves.\\
Elle est destin\'ee aussi \`a faciliter la compr\'ehension de la deuxi\`eme 
partie.\\
{\bf La deuxi\`eme partie} est ind\'ependante et elle consiste \`a \'edutier la suite r\'ecursive d\'efinie par :\\
{\tt  b(1)=b(2)=1} et pour {\tt n>2} par {\tt  b(n)=b(b(n-1))+b(n-b(n-1))}.\\
{\bf La troisi\`eme partie} consiste \`a rappeler diff\'erentes propriétés des 
combinaisons utilis\'ees dans la deuxi\`eme partie.\\
{\bf Notations utilisées en deuxi\`eme partie}\\
On notera :
\begin{itemize}
\item  {\tt B} la liste constituée par {\tt b(n), pour n }$\in \N$,
\item  {\tt GB} est le graphe des segments reliant les points de coordonn\'ees
{\tt n,b(n)}, pour {\tt n }$\in \N$,
\item  {\tt B(p)} la liste :\\
{\tt [b(2\verb|^|p+k)\$(k=0..2\verb|^|p)]=[b(2\verb|^|p+1)....b(2\verb|^|(p+1))]}, pour $p\in \N$,
\item pour $p\in \N$ :\\
{\tt xm\_p=3*2\verb|^|(p-1)} qui est l'indice du milieu de {\tt B(p)},\\
{\tt ym\_p)=b(3*2\verb|^|(p-1))=b(xm\_p)}, \\
{\tt pm\_p)=ym\_p)/ xm\_p)=b(3*2\verb|^|(p-1))/(3*2\verb|^|(p-1))} qui est la 
pente du graphe {\tt GB} au point milieu de {\tt B(p)}.\\
La suite {\tt pm\_k } sera appel\'ee la suite "pentemilieu".\\
On \'etudiera la suite des pentes des milieux {\tt pm\_k)} pour $k\in \N$ et
on montrera que cette suite tend vers 
$\displaystyle\frac{1}{2}$ quand $p$ tend vers $+\infty$,
\item pour $p\in \N$:\\
{\tt pM\_p:=max([(b(n)/n)\$(n=2\verb|^|p..2\verb|^|(p+1))])}\\
{\tt pM\_p} sera appell\'ee la suite "pentemaximum".\\
On \'edutiera aussi la suite des pentes des maximums {\tt pM\_k)} pour $k\in \N$et on montrera que cette suite tend aussi vers $\displaystyle\frac{1}{2}$ quand $p$ tend vers $+\infty$. 
\end{itemize}

\newpage
\part*{Partie I}
On suppose ici que :
\begin{itemize}
\item la distance entre 2 nénuphars est de 1 unit\'e de longueur,
\item un saut de crapaud met 1 unit\'e de temps,
\item un crapaud peut enchaîner plusieurs sauts, mais pour cela, il doit faire 
des pauses. Chaque pause dure 1 unité de temps, il peut aussi faire plusieurs
 pauses \`a la suite.
%On notera la dur\'ee du parcours sera l'entier {\tt x=n} et la distance 
%parcourue sera l'entier {\tt y=m}.

\end{itemize}
\section{Les consignes du concours de sauts}
Un  concours d'endurance de sauts est organis\'e. Pour cela, les crapauds 
doivent observer les consignes suivantes :
\begin{itemize}
\item au d\'epart i.e. au temps $0$, le crapaud doit faire un saut puis il 
doit faire une  pause, (apr\`es cela le temps vaut $2$ unit\'es de temps),
\item ensuite, pour tout entier $p\geq 1$, durant le lapps  de temps allant de 
$2^p$ \`a $2^{p+1}$, le crapaud doit faire $2^{p-1}$ sauts : il doit donc durant
 cette p\'eriode sauter $2^{p-1}$ fois et se reposer pendant $2^{p-1}$ fois.
\item faire un saut au temps $2^p$ pour tout $p\geq 1$,
\item se reposer durant la p\'eriode allant de $2^{p+1}-1$ \`a $2^{p+1}$ pour
 tout $p\geq 1$,
\item avant le  départ chaque candidat devra expliquer son parcours ou donner 
sa position en fonction du temps. Seuls les candidats 
ayant un parcours r\'epondant aux consignes seront s\'electionn\'es. 
\end{itemize}
\subsection{Les explications donn\'ees par les 4 candidats s\'electionn\'es}
\begin{itemize}
\item Le candidat 1 dit : "je fais un saut puis je me repose 1 fois etc...",
\item Le candidat 2 dit : "je saute durant tout le temps imposé puis, je 
me repose le reste du temps" i.e. "pour tout $p\geq 1$, entre $n=2^p$ et 
$n=3*2^{p-1}$, je fais $2^{p-1}$ sauts puis, entre $n=3*2^{p-1}$ et $n=2^{p+1}$ je 
me repose $2^{p-1}$ fois",
\item Le candidat 3 dit : "pour tout $p\geq 1$, entre $n=2^p$ et $n=2^{p+1}$, je
fais $2^{p-1}-1$ sauts puis, je me repose $2^{p-2}$ fois, ensuite je fais 1 saut 
puis, je me repose $2^{p-2}$ fois",
\item Le candidat 4 qui est mathématicien dit : "mon parcours est plus complexe,
aussi je vous donne ma position $b(n)$ en fonction du temps $n$.\\
Mon d\'eplacement d\'ebute selon la consigne par $b(0)=0,b(1)=1,b(2)=1$ puis, 
j'utilise la formule $b(n)=b(b(n-1))+b(n-b(n-1))$ pour $n>2$.\\
C'est \`a vous de v\'erifier que cette formule d\'efinit un parcours qui
respecte bien les consignes. 
\end{itemize}
Le jury v\'erifie facilement que les consignes des 3 premiers candidats sont 
respect\'ees. Pour le candidat 4, le jury, ne comptant aucun math\'ematicien, 
est perplexe aussi, il se contente de tester le d\'ebut du parcours en calculant
les premiers termes de la suite $b(n)$, puis il s\'electionne le candidat 4.\\
On invite le jury \`a lire la 2i\`eme partie pour comprendre l'\'evolution du 
parcours du candidat 4 ; cette 2i\`eme partie est l'\'etude de la suite
d\'efinie par :\\
$b(0)=0$, $b(1)=b(2)=1$, $b(n)=b(b(n-1))+b(n-b(n-1))$ pour $n>2$\\
{\bf Remarque}\\
 La valeur $b(0)=0$ n'est pas utile pour la d\'efinition de la suite {\tt b(n)}.\\
%La suite $c(0)=0, c(1)=1$ et $c(n)=c(c(n-1))+c(n-c(n-1))$ pour $c>1$ est la suite constante $c(n)=n$\
On pourra se r\'ef\'erer \`a la partie II pour avoir la d\'emonstration qui
montre que la suite {\tt b(n)} est bien d\'efinie.

\subsection{Les parcours de ces 4 candidats pour $n=0..16$}
L'entier $n$ d\'esigne le temps \'ecoul\'e depuis le d\'epart et\\
$U1(n)$ (resp $U2(n),U3(n),U4(n)=b(n)$) d\'esigne la 
position du candidat 1 (resp 2,3,4) en fonction du temps $n$.\\
{\bf Exercice}\\
Donner le d\'ebut du parcours des quatre candidats durant le lapps de temps $0,16$ (ou $0..32$ pour les courageux)\\
{\bf Correction}\\
Voici le d\'ebut du parcours durant le lapps de temps $0,16$ des quatre
premiers candidats\\
\newenvironment{tab}[1]
{\begin{tabular}{|#1|}\hline}
{\hline\end{tabular}}
\begin{tab}{cccccccccccccccccc}
n  & 0  &1  &2  &3  &4  &5  &6  &7  &8 &9 & 10 & 11 & 12  & 13 &14  &15 &16\\
\hline
U1 & 0  &1  &1  &2  &2  &3  &3  &4  &4 &5 & 5  & 6  &  6  & 7  & 7  & 8 & 8\\
U2 & 0  &1  &1  &2  &2  &3  &4  &4  &4 &5 & 6  & 7  &  8  & 8  & 8  & 8 & 8\\
U3 & 0  &1  &1  &2  &2  &3  &3  &4  &4 &5 & 6  & 7  &  7  & 7  & 8  & 8 & 8\\ 
U4 & 0  &1  &1  &2  &2  &3  &4  &4  &4 &5 & 6  & 7  &  7  & 8  & 8  & 8 & 8\\  
\end{tab}
On remarquera que pour $n$ entre 0 et 5 le parcours est impos\'e par les 
consignes mais ensuite il n'est pas le m\^eme pour tout le monde.
\section{Exercices}
\subsection{Exercice 1}
\'Ecrire les programmes qui donne la liste des positions $U_1(n)$
(resp $U_2(n),U_3(n),U_4(n)$) du candidat 1 (resp 2,3,4)
en fonction du temps $n$.
Il faudra se r\'ef\'erer \`a la {\tt Partie II} pour v\'erifier que le 
candidat 4 respecte bien toutes les consignes. 
\subsection{Correction de l'exercice 1}
\begin{itemize}
\item La position $U_1(n)$ du parcours du candidat 1 est :\\
$U_1(0)=0$, $U_1(2n-1)=n,U_1(2n)=n$ pour $n>=1$\\
On tape :\\
{\tt eval([0,(k,k)\$(k=1..8)])}\\
On obtient :\\
{\tt [0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8]}\\
On tape le programme {\tt LU1(p)} qui donne la suite des valeurs de $U1(n)$ 
pour $n$ allant de 0 jusque $2^p$ :
\begin{verbatim}
 LU1(p):={
  local L,k;
  L:=0,1,1;
  pour k de 2 jusque 2^(p-1) faire 
      L.append(k,k);
  fpour;
  return eval(L);
  }:;
\end{verbatim} 
On tape :\\ 
{\tt LU1(4)}\\
On obtient les 16+1 premiers termes de {\tt LU1} :\\
{\tt (0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8)}\\
 On tape :\\ 
{\tt LU1(5)}\\
On obtient  32+1 premiers termes de {\tt LU1} :\\
{\tt (0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,\\
9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16)}
\item La position $U2(n)$ du parcours du candidat 2 est :\\
$U2(0)=0$ et  pour $p>0$ :\\
$U2(2^p+k)=2^{p-1}+k$ pour $k=0..3*2^{p-1}$ et\\
$U2(2^p+k)=2^{p+1}$ pour $k=3*2^{p-1}+1..2^{p+1}$\\
On remarquera que $3*2^{p-1}=(2^p+2^{p+1})/2$ et donc $3*2^{p-1}$ se trouve au milieu de l'intervalle $[2^p,2^{p+1}]$ et que $2^{p-1}+3*2^{p-1}=2^{p+1}$.\\
On tape le programme {\tt L2U(n)} qui donne la suite des valeurs de $U2(n)$ 
pour $n$ allant de 0 jusque $2^p$ :
\begin{verbatim}
LU2(p):={
  local L,k,j;
  L:=0,1,1;
  pour j de 1 jusque p-1 faire
    pour k de 1 jusque 2^(j-1) faire 
      L:=L,2^(j-1)+k;
   fpour;
    pour k de 2^(j-1)+1 jusque 2^(j) faire 
      L.append(2^(j));
      fpour;
   fpour;
  return eval(L);
  }:;
\end{verbatim} 
On tape :\\ 
{\tt LU2(4)}\\
On obtient les 16+1 premiers termes de {\tt LU2} :\\
{\tt (0,1,1,2,2,3,4,4,4,5,6,7,8,8,8,8,8)}\\
On tape :\\ 
{\tt LU2(5)}\\
On obtient  32+1 premiers termes de {\tt LU2} :\\
{\tt (0,1,1,2,2,3,4,4,4,5,6,7,8,8,8,8,8,\\
9,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16)}
\item La position $U3(n)$ du parcours du candidat 3 est :\\
$U3(0)=0$,  pour $p>=0$ sur $2^p.. 2^{p+1}$ on a :\\
$U3(2^p+k)=2^{p-1}+k$ pour $k=0..2^{p-1}-1$ et\\
$U3(2^p+2^{p-1}+k)=2^{p}-1$ pour $k=0..2^{p-2}$\\ 
$U3(2^p+3*2^{p-2})=U3(7*2^{p-2})=2^p$ \\
$U3(2^p+3*2^{p-2}+k)=U3(7*2^{p-2}+k)=2^p$ pour $k=0..2^{p-2}$\\ 
On tape pour $p=3$ :\\
{\tt (2\verb|^|2+k)\$(k=0..3),(2\verb|^|2+3)\$(k=4..5),2\verb|^|3,2\verb|^|3\$(k=7..8)}\\
On obtient :\\
{\tt (4,5,6,7,7,7,8,8,8)}\\
On tape le programme {\tt LU3(n)} qui donne la liste des valeurs de $U3(n)$ 
pour $n$ allant de 0 jusque $2^p$ :
\begin{verbatim}
LU3(p):={
  local L,k,j;
  L:=0,1,1,2;
  pour j de 2 jusque p faire
    pour k de 1 jusque 2^(j-2)-1 faire 
      L.append(2^(j-2)+k);
    fpour;
    pour k de 2^(j-2) jusque 3*2^(j-3)-1 faire 
      L.append(2^(j-1)-1);
    fpour;
    L.append(2^(j-1));
    pour k de 3*2^(j-3)+1 jusque 2^(j-1) faire 
      L.append(2^(j-1)) ;
    fpour;
  fpour;
  return eval(L);
  }:;
\end{verbatim} 
 On tape :\\ 
{\tt LU3(4)}\\
On obtient 16+1 premiers termes de {\tt L3} :\\
{\tt (0,1,1,2,2,3,3,4,4,5,6,7,7,7,8,8,8)}\\
 On tape :\\ 
{\tt LU3(5)}\\
On obtient les  32 premiers termes de {\tt L3} :\\
{\tt (0,1,1,2,2,3,3,4,4,5,6,7,7,7,8,8,8,\\
9,10,11,12,13,14,15,15,15,15,15,16,16,16,16,16)}
\item On calcule   les valeurs de la suite $U4(n)=b(n)$.\\
On a :\\
{\tt b(1)=1}\\
{\tt b(2)=1}\\
{\tt b(3)=b(b(2))+b(3-b(2))=b(1)+b(2)=2}\\
{\tt b(4)=b(b(3))+b(4-b(3))=b(2)+b(2)=2}\\
{\tt b(5)=b(b(4))+b(5-b(4))=b(2)+b(1)=3}\\
{\tt b(6)=b(b(5))+b(6-b(5))=b(3)+b(3)=4}\\
{\tt b(7)=b(b(6))+b(7-b(6))=b(4)+b(3)=4}\\
{\tt b(8)=b(b(7))+b(8-b(7))=b(4)+b(4)=4}\\
{\tt b(9)=b(b(8))+b(9-b(8))=b(4)+b(5)=5}\\
{\tt b(10)=b(b(9))+b(10-b(9))=b(5)+b(5)=6}\\
{\tt b(11)=b(b(10))+b(11-b(10))=b(6)+b(5)=7}\\
{\tt b(12)=b(b(11))+b(12-b(11))=b(7)+b(5)=7}\\
{\tt b(13)=b(b(12))+b(13-b(12))=b(7)+b(7)=8}\\
{\tt b(14)=b(b(13))+b(14-b(13))=b(8)+b(6)=8}\\
{\tt b(15)=b(b(14))+b(15-b(14))=b(8)+b(7)=8}\\
{\tt b(16)=b(b(15))+b(16-b(15))=b(8)+b(8)=8}\\
On remarque que la d\'efinition de cette suite est r\'ecursive.\\
Mais le  programme donnant la liste $LU4(p)$ sera it\'eratif pour que son 
\'ex\'ecution soit plus rapide.\\
On tape :
\begin{verbatim}
LU4(p):={
 local k,u1,uk,L;
  L:=0,1,1;
  pour k de 3 jusque 2^p faire 
    u1:=L[k-1];
    uk:=L[u1]+L[k-u1];
    L.append(uk);
  fpour;
retourne eval(L);
  }:;
\end{verbatim} 
On remarquera que l'on a mis {\tt L.append(uk)} au lieu de {\tt L:=append(L,uk)}
car l'\'ex\'ecution de {\tt L.append(uk)} est plus rapide puisqu'elle \'evite 
la recopie de {\tt L}.\\
 On tape :\\ 
{\tt LU4(4)}\\
On obtient les 16+1 premiers termes de {\tt L4} :\\
{\tt (0,1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8)}\\
 On tape :\\ 
{\tt LU4(5)}\\
On obtient les 32+1 premiers terme de {\tt L4} :\\
{\tt (0,1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,\\
9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16)}
\end{itemize}
\subsection{Exercice 2}
\begin{itemize}
\item \'Enonc\'e :\\
Utiliser les programmes pr\'ec\'edents pour avoir les 
valeurs des suites {\tt LU1(n)}, (resp {\tt LU2(n), LU3(n), LU4(n)}) pour 
$2^p\leq n \leq 2^{p+1}+1$.
\item Correction :\\
On d\'efinit la fonction {\tt L1(p)} qui renvoie {\tt LU1(n)}
pour $n\in [2^p, 2^{p+1}+1]$ :
\begin{verbatim}
 L1(p):={
  local L,k;
  L:=LU1(p+1);
  return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
  }:;
\end{verbatim}
On d\'efinit la fonction {\tt L2(p)} qui renvoie {\tt LU2(n)}
pour $n\in [2^p, 2^{p+1}+1]$ :
\begin{verbatim}
 L2(p):={
  local L,k;
  L:=LU2(p+1);
  return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
  }:;
\end{verbatim} 
On d\'efinit la fonction {\tt L3(p)} qui renvoie {\tt LU3(n)} 
pour $n\in [2^p, 2^{p+1}+1]$ :
\begin{verbatim}
L3(p):={
  local L,k;
  L:=LU3(p+1);
  return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;;
  }:;
\end{verbatim}
On d\'efinit la fonction {\tt L4(p)} qui renvoie {\tt LU4(n)}
pour $n\in [2^p, 2^{p+1}+1]$ :
\begin{verbatim}
L4(p):={
 local Lk;
  L:=LU4(p+1);
  return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
  }:;
\end{verbatim} 
\end{itemize}
\subsection{Exercice 3}
\begin{itemize}
\item \'Enonc\'e :\\
Utiliser les programmes pr\'ec\'edents pour tracer les arches graphiques 
{\tt AG1(p)} (resp {\tt AG2(p)}, {\tt AG3(p)}, {\tt AG(p)}) repprésentant 
 {\tt LU1(n)/n} (resp {\tt LU2(n)/n}, {\tt LU3(n)/n}, {\tt LU4(n)/n}) pour $2\leq n \leq 2^{p}$.\\
Faire sur un m\^eme graphe {\tt AG1(p)},(resp {\tt AG2(p)}, {\tt AG3(p)}, {\tt  AG(p)}), pour $p=1..8$
\item Correction :\\
On tape :
\begin{verbatim}
AG1(p):={
local G,L,s,k,Pt,Pts;
G:=NULL;L:=LU1(p);
s:=size(L)-1;
Pt:=point(L[1]);
pour k de 2 jusque s faire 
  Pts:=point(k,L[k]/k);
  G:=G,segment(Pt,Pts);
  Pt:=Pts;
fpour;
return G;
}:;
\end{verbatim}
On tape :\\
{\tt AG1(8)}\\
On tape :\\
{\tt AG2(8)}\\
On tape :\\
{\tt AG3(8)}\\
On tape :\\
{\tt AG4(5)}\\
ou on rajoute le  param\`etre {\tt L} pour repr\'esenter {\tt LU1} ou 
{\tt LU2} ou {\tt LU3} ou {\tt LU4} :
\begin{verbatim}
AG(L,p):={
local G,s,k,Pt,Pts;
G:=NULL;
s:=size(L)-1;
Pt:=point(L[1]);
pour k de 2 jusque s faire 
  Pts:=point(k,L[k]/k);
  G:=G,segment(Pt,Pts);
  Pt:=Pts;
fpour;
return G;
}:;
\end{verbatim}
On tape :\\
{\tt AG(LU1(8),8)}\\
On tape :\\
{\tt AG(LU2(8),8)}\\
On tape :\\
{\tt AG(LU3(8),8)}\\
On tape :\\
{\tt AG(LU4(8),8)}
\end{itemize}
\subsection{Exercice 4}
\begin{itemize}
\item \'Enonc\'e :\\
\'Ecrire un programme qui renvoie le milieu de la suite :\\
{\tt (LU1(p)[k]/k)\$(k=2\verb|^|(n-1)..2\verb|^|n)} pour 
{\tt n=2..p}.\\
c'est a dire la suite :\\
{\tt LU1(p)[3*2\verb|^|k]/(3*2\verb|^|k)} pour {\tt k=0..(p-2)}.\\
Utiliser les programmes pr\'ec\'edents pour tracer la ligne polygonale reliant
les points  milieux des arches pr\'ec\'edentes pour {\tt LU1} 
(resp {\tt LU2,LU3,LU4})\\
{\bf Attention}\\
La suite {\tt LU1(p)} est la suite des valeurs {\tt U1[n]} pour $n=0..2^p$.\\
Pour $n=2..2^p$ on a $p-1$ arches $[2^1,2^2],[2^2,2^3]..[2^{p-1},2^p]$.\\
La suite des milieux des arches de {\tt LU1(p)} est donc de longueur {\tt p-1}.\\
Il y a donc {\tt p-2} segments reliant ces points.
\item Correction :\\
On tape :
\begin{verbatim}
milieuL(L,p):={
  local k,Lm,m,ms,km;
  m:=L[3]/3;km:=0;
  Lm:=[3,L[3]/3];
  pour k de 1 jusque p faire
  ms:=L[3*2^k]/(3*2^k);
  Lm:=Lm,[3*2^k,ms];
  fpour;
  return [Lm];
  }:;
\end{verbatim}
Ou bien on tape :
\begin{verbatim}
GmiL1(p):={
local L,Gm,s,k,Pt,Pts;
L:=LU1(p);
s:=size(L)-1;
Gm:=NULL;
Pt:=point(3,L[3]/3);
pour k de 2 jusque (p-2) faire 
//Gm:=Gm,L[3*2^k]/(3*2^k);
Pts:=point(3*2^(k-1),L[3*2^(k)]/(3*2^(k)));
Gm:=Gm,segment(Pt,Pts);
Pt:=Pts;
fpour;
return Gm;
}:;
\end{verbatim}
Ou bien on tape :
\begin{verbatim}
Gmil(L,p):={
local Gm,k,Pt,Pts;
Gm:=NULL;
Pt:=point(3,L[3]/3);
pour k de 1 jusque p-2 faire 
Pts:=point(3*2^k,L[3*2^k]/(3*2^k));
Gm:=Gm,segment(Pt,Pts);
Pt:=Pts;
fpour;
return Gm;
}:;
\end{verbatim}
On tape pour avoir l'affichage des milieux en rouge :\\
{\tt L:=LU4(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1)}\\
Ou on tape :\\
{\tt AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)}\\
Ou on tape :\\
{\tt AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)}\\
Ou bien on tape plus simplement :\\
{\tt affichage(plotlist([[L[3*2\verb|^|j]/(3*2\verb|^|k),3*2\verb|^|k]\$(j=0..12)]),1)}\\

On tape :\\
{\tt AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)}\\
{\tt AG(LU2(8),8),affichage(Gmil(LU2(8),8),1)}\\
{\tt AG(LU3(8),8),affichage(Gmil(LU3(8),8),1)}\\
{\tt AG(LU4(8),8),affichage(Gmil(LU4(8),8),1)}
\end{itemize})
\subsection{Exercice 5}
\begin{itemize}
\item \'Enonc\'e :\\
\'Ecrire un programme qui renvoie les coordon\'ees du  maximum  de l'arche 
$2^{k-1}..2^k$, i.e. les coordon\'ees de :\\
{\tt max(LU1(p)[n]/n\$(n=2\verb|^|{k-1}..2\verb|^|k))}.\\
Puis, utiliser les programmes pr\'ec\'edents pour tracer la suite des maximum
des arches pr\'ec\'edentes pour {\tt LU1(p)} (resp {\tt LU2(p), LU3(p), LU4(p)})\\
{\bf Attention}\\
La suite {\tt LU1(p)} est la suite des valeurs {\tt U1[n]} pour $n=0..2^p$
Pour $n=2..2^p$ on a $p-1$ arches ($[2^1,2^2],[2^2,2^3]..[2^{p-1},2^p]$).\\
La suite des maximum des arches pour {\tt LU1(p)} est donc de longueur {\tt p-1}. \\)
Il y a donc {\tt p-2} segments reliant ces points.
\item Correction :\\
On tape :
\begin{verbatim}
MaxL(L,n):={
  local k,M,Ms,kM;
  M:=L[2^(n-1)]/ 2^(n-1);kM:=2^(n-1);
  pour k de 2^(n-1)+1 jusque 2^n faire
  Ms:=L[k]/k;
  si Ms>M alors M:=Ms;kM:=k; fsi;
  fpour;
  return [kM,M];
  }:;
\end{verbatim}
On tape :\\
{\tt MaxL(LU1(8),j)\$(j=2..8)}\\
{\tt MaxL(LU2(8),j)\$(j=2..8)}\\
{\tt MaxL(LU3(8),j)\$(j=2..8)}\\
{\tt MaxL(LU4(8),j)\$(j=2..8)}\\
\end{itemize}
{\bf Les graphes}\\
On tape :\\
{\tt L:=LU1(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU2(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU3(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU4(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
Ou bien on tape :\\
{\tt L:=LU1(12):;AG(L,12),affichage(Gmil(L,12),1),\\
   affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU2(12):;AG(L,12),affichage(Gmil(L,12),1),\\
  affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU3(12):;AG(L,12),affichage(Gmil(L,12),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}\\
{\tt L:=LU4(12):;AG(L,12),affichage(Gmil(L,12),1),\\
affichage(plotlist([Max(L,j)\$(j=2..12)]),2)}
\subsection{Exercice 6}
\begin{itemize}
\item \'Enonc\'e :\\
Trouver l'expression de :\\
{\tt milieuL(L,n)} en fonction de {\tt n>0} pour {\tt L=L1(n)} 
(resp {\tt L2(n)}, {\tt L3(n)})\\
Trouver l'expression de :\\
{\tt MaxL(L,n)} en fonction de {\tt n} pour {\tt L=L1(n)} 
(resp {\tt L2(n)}, {\tt L3(n)}).
\item Correction :\\
On a :\\
pour {\tt L=L1(n)}\\
pour {\tt n=1} {\tt milieuL(L1(1),1)=[3,2/3]} \\
pour {\tt n>1}{\tt milieuL(L1(n),1)=[3*2\verb|^|(n-1),1/2]} \\
pour {\tt L=L2(n)}\\
pour {\tt n>=1} {\tt milieuL(L1(n),1)=[3*2\verb|^|(n-1),2/3]} \\
pour {\tt L=L3(n)}\\
pour {\tt n=1} {\tt milieuL(L1(1),1)=[3,2/3]} \\
pour {\tt n>=2}{\tt milieuL(L1(n),1)=[3*2\verb|^|(n-1),(2\verb|^|n-1)/3*2\verb|^|(n-1)]} \\
On v\'erifie pour {\tt LU3(10)}, pour cela on tape :\\
{\tt L:=LU3(8):;milieuL(L,6)}\\
On obtient :\\
{\tt [[3,2/3],[6,1/2],[12,7/12],[24,5/8],[48,31/48],}\\
{\tt [96,21/32],[192,127/192]]}\\
On tape :\\
{\tt [(3*2\verb|^|(n-1),(2\verb|^|n-1)/3*2\verb|^|(n-1))]\$(n=2..7)}\\
On obtient :\\
{\tt [[6,1/2],[12,7/12],[24,5/8],[48,31/48],[96,21/32],}\\
{\tt [192,127/192]]}
\end{itemize}
{\bf Remarque}\\
Pour le candidat 4, trouver la suite des milieux et la suite du maximum est 
plus difficile. C'est ce que l'on se propose de faire dans ce qui suit.

\section{Autre repr\'sentation des parcours}
Sur chaque intervalle $[2^p+1,2^{p+1}]$, on d\'ecide de repr\'esenter les 
diff\'erents parcours {\tt L1(p)} (resp {\tt L2(p),L3(p),L4(p)})  par la 
suite :\\
{\tt T1(p)} (resp {\tt T2(p),T3(p),T4(p)})\\
Pour {\tt T1(p)} on commence par  {\tt T1(p)[0]} qui est la 
valeur de {\tt U1(2\verb|^|p)}, puis on note successivement le nombre de sauts 
et le nombre de pauses du candidat 1 (resp 2,3,4).\\
Par exemple :
\begin{itemize}
\item pour $p=3$, $U3$ est représenté pour $n=2^3..2^4+1$ par la suite :\\
{\tt (4,5,6,7,7,8,8,8,8,9)}, mais on peut aussi la repr\'esenter :\\
pour $n=2^3+1..12^4$  par la suite {\tt T3(3)=(4,3,2,1,2)}.\\
En effet {\tt T3[0]} vaut $U3(8)=4$ qui est la valeur de la distance \`a partir
de laquelle le premier saut est r\'ealis\'e, puis on fait 3 sauts et on fait 2 
pauses, puis on fait 1 saut et on fait 2 pauses.\\
pour $p=4$, $U3$ peut \^etre représenté pour $n=2^4..2^5+1$ par la suite :\\
{\tt T3(4)=(8,7,4,1,4)},
\item pour $p=3$, $U4$ pour $n=17=16+1..32$  par la liste  :\\ 
{\tt T4(3)=[4,3,1,1,3]}, \\
pour $p=4$, $U4$ pour $n=33=12+1..64$  par la liste :\\
{\tt T4(4)=[8,4,1,2,1,1,2,1,4]}. 
\end{itemize}
Il faut bien voir que :
\begin{itemize}
\item lorsqu'on compte le nombre de sauts, on compte le nombre d'intervalles qui
 s\'epare 2 valeurs diff\'erentes de la distance, 
\item lorsqu'on compte le nombre de pauses, on compte le nombre d'intervalles 
qui s\'epare 2  valeurs identiques de la distance (par exemple $(6,7,7,8,8,8,8)$
 signifie que le nombre de sauts augmente de 1 pour le passage de 6 \`a 7, puis 
le nombre de pauses est de 1, puis le nombre de sauts augmente de 1, puis le 
nombre de pauses est de 3),
\item pour que la repr\'esentation sur l'intervalle $[n_1,n_2]$ soit correcte 
il faut que :\\
$u(n_1)=u(n_1-1)+1$ (i.e. $u(n_1)$ est obtenu apr\`es un saut)\\
et que $u(n_2+1)=u(n_2)+1$ (i.e. $u(n_2+1)$ est obtenu apr\`es un saut),\\
ce qui est le cas sur les intervalles $[n_1=2^p+1,n_2=2^{p+1}]$ puisque les 
candidats respectent les consignes.\\
Pour reconstituer les valeurs de $u(n)$ avec cette nouvelle repr\'esentation il 
faudra aussi conna\^itre les valeurs de $u(n_1-1)$ et de $u(n_2+1)$ ce qui est 
le cas  sur les intervalles $[2^p+1,2^{p+1}]$ puisque les consignes imposent que 
$u(2^p)=2^{p-1}$, $u(2^p+1)=2^{p-1}+1$ et $u(2^{p+1}+1)=2^{p}+1$.
\end{itemize}
Voici les diff\'erentes suites {\tt Lp} et {\tt Tp} selon les candidats 
pour $n=2^4...2^5$ ($p=4$):
\begin{itemize}
\item le candidat 1 peut repr\'esenter son parcours par la suite {\tt L1(4)} :\\
{\tt L1(4)=(8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17)}\\
ou bien par la liste {\tt T1(4)} (qui sera une suite de 1) :\\
{\tt T1=[8,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]}
\item le candidat 2 peut repr\'esenter son parcours par la suite {\tt L2(4)} :\\
{\tt L2(4)=(8,9,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16,17)}\\
ou bien par la liste {\tt T2=[8,8,8]}
\item le candidat 3 peut repr\'esenter son parcours par la suite {\tt L3(4)} :\\
{\tt L3(4)=(8,9,10,11,12,13,14,15,15,15,15,15,16,16,16,16,16,17)}\\
par la liste {\tt T3=[8,7,4,1,4]}
\item le candidat 4 peut repr\'esenter son parcours par la suite {\tt L4(4)} :\\
{\tt L4(4)=(8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17)}\\
ou bien par la liste {\tt T4=[8,4,1,2,1,1,2,1,4]}\\
Pour avoir la liste {\tt Tn]} se r\'ef\'erer \`a la {\bf partie II}
\end{itemize}
\subsection{Comment savoir o\`u se trouve le crapaud au temps $n$ ?}
\`A l'instant $n$ ($n\in \N$), pour chacune des représentations, on veut 
savoir \`a quelle distance $d$ du d\'epart se trouve le crapaud.\\
Par exemple on sait que selon les consignes on doit avoir pour:\\
$n=2^m-1$, $d=2^{m-1}$,\\
$n=2^m$, $d=2^{m-1}$\\
$n=2^m+1$, $d=2^{m-1}+1$\\
Pour la repr\'esentation {\tt L(p)} si $0\leq n \leq 2^{p+1}$, 
la distance {\tt d} est \'egale \`a {\tt L(p)[n]}\\
Pour $n=12$, on a puisque $2^3<12<16=2^4$ :\\
Pour le candidat 1, on tape :\\:\\
{\tt L1:=[0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,\\
13,13,14,14,15,15,16,16]:;L1[12],L1[24]}\\ 
On obtient {\tt (6,12)}\\
Pour le candidat 2, on tape :\\
{\tt L2:=[0,1,1,2,2,3,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,\\
13,14,15,16,16,16,16,16,16,16,16,16):;L2[12],L2[24]}\\
On obtient {\tt (8,16)}\\
Pour le candidat 3, on tape :\\
{\tt L3:=[0,1,1,2,2,3,3,4,4,5,6,7,7,7,8,8,8,9,10,11,12,\\
13,14,15,15,15,15,15,16,16,16,16,16):;L3[12];L3[24]}\\
On obtient {\tt (7,15)}\\
Pour le candidat 4, on tape :\\
{\tt L4:=[0,1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,9,10,11,12,12,\\
13,14,14,15,15,15,16,16,16,16,16):;L4[12],L4[24]}\\
On obtient {\tt (7,14)}\\
Pour la repr\'esentation {\tt T} :\\
Si le temps \'ecoul\'e est \'egal \`a l'indice {\tt n} d'un \'el\'ement de 
{\tt L} alors {\tt n} est \'egal \`a la somme des termes jusqu'\`a {\tt n}, i.e.
{\tt sum([T[k]],k=0..n)}
et la distance se mesure par la somme des termes impairs jusqu'\`a {\tt n}, i.e.{\tt sum1([L[k]],k=0..n)}
\\
$d=L(n)$.\\ 
On d\'efinit deux sommes :
\begin{itemize}
\item  {\tt sum0(L)} qui renvoie la somme 
des termes de {\tt L} d'indices pairs :
\item {\tt sum1(L)} qui renvoie la somme 
des termes de {\tt L} d'indices impairs,
\end{itemize}
\begin{verbatim}
sum0(L):={
local S,k,s;
s:=size(L)-1;
S:=0;
pour k de 0 jusque s pas 2 faire 
S:=S+L[k];
fpour;
return S;
}:;
sum1(L):={
local S,k,s;
s:=size(L)-1;
S:=0;
pour k de 1 jusque s pas 2 faire 
S:=S+L[k];
fpour;
return S;
}:;
S(L,s):=sum(L[k],k,0,s);S1(L,s):=sum(L[k],k,1,s,2)
\end{verbatim}
On tape :\\
{\tt T1:=[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];}\\
{\tt [sum(T1[k],k=1..s),sum(T1[12])],[sum1(T1[24]),sum(T1[24])]}\\ 
On obtient {\tt (6,12)}\\
On tape :\\
{\tt T2:=[0,1,1,1,1,2,2,4,4,8,8];}\\
{\tt [sum1(T2[12]),sum(T2[12])],[sum1(T2[24]),sum(T2[24])]}\\
On obtient {\tt (8,16)}\\
On tape :\\
{\tt T3:=[0,1,1,1,1,1,1,1,1,3,2,1,2,7,1,4,1,4];}
{\tt [sum1(T3[12]),sum(T3[12])],[sum1(T3[24]),sum(T3[24])]}\\
On obtient {\tt (7,15)}\\
On tape :\\
{\tt T4:=[0,1,1,1,1,2,2,3,1,4,5,1,2,1,4];}\\
{\tt [sum1(T4[12]),sum(T4[2]12)],[sum(T4[24]),sum(T4[24])]}\\
On obtient {\tt (7,14)}\\
On v\'erifie, pour $n=12$ ou $n=24$, on tape :\\
{\tt L1u(12),L1u(24)} renvoie {\tt 6,12}\\
{\tt L2u(12),L2u(24)} renvoie {\tt 8,16}\\
{\tt L3u(12),L3u(24)} renvoie {\tt 7,15}\\
{\tt L4u(12),L4u(24)} renvoie {\tt 7,14}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\part*{Partie II}
\section{D\'efinition}
Les batracions sont des suites fractales ayant une structure auto-similaire 
quand on les examine \`a diff\'erentes \'echelles.\\
Voici un exemple de batracion, c'est la suite {\tt b(n)} d\'efinie par :\\
{\tt b(1)=1}\\
{\tt b(2)=1}\\
{\tt b(n)=b(b(n-1))+b(n-b(n-1))} pour {\tt n>2}

\section{Pourquoi la suite {\tt b(n)} est-elle définie ?}
%La suite b(n) a tous ses termes positifs donc b(n) est croissante.\\
%Si {\tt n>=3} alors {\tt n-1>=2} donc  {\tt b(n-1)} est d\'efinie et 
%{\tt b(n-1)>=b(2)=1} donc {\tt b(b(n-1))} est d\'efinie.\\
Pour que {\tt b(n)} soit d\'efinie il faut et il suffit que la d\'efinition de 
{\tt b(n-1)} entraine la d\'efinition de {\tt b(n)}.
Donc, il faut et il suffit de montrer que {\tt 1<=b(n-1)<=n-1}  puisque 
{\tt 1<=n-b(n-1)<=n-1} est \'equivalent \`a {\tt 1<=b(n-1)<=n-1}.\\
Donc si {\tt b(n-1)} est d\'efinie et si {\tt 1<=b(n-1)<=n-1} alors {\tt b(n)} est d\'efinie.\\
Montrons par r\'ecurrence que pour tout {\tt n>=1} on a {\tt 1<=b(n)<=n}.\\
Soit {\tt P(n)} la propri'et\'e {\tt 1<=b(n)<=n}.\\
On a  :\\
{\tt 1<=b(1)=1<=1}\\
{\tt 1<=b(2)=1<=2}\\
{\tt 1<=b(3)=2<=3}\\
Donc les propri'et\'es {\tt P(1),P(2),P(3)} sont vraies.\\
Supposons que pour tout {\tt k<=n} la propri'et\'e {\tt P(k)} est vraie i.e. 
que l'on a :\\
{\tt 1<=b(k)<=k} pour tout {\tt 1<=k<=n}\\
Est ce que cela entraine que {\tt P(n+1)} est vraie ?\\
On a {\tt b(n+1)=b(b(n))+b(n+1-b(n))}\\
Puisque {\tt P(n)} est vraie on a  {\tt 1<=b(n)<=n} \\
Soit {\tt k=b(n)} on a {\tt  1<=b(k)<=k=b(n)<=n} puisque {\tt P(k)} est vraie.\\
Puisque  {\tt 1<=b(b(n))=b(k)<=n}, la propri'et\'e {\tt P(b(k))=P(b(b(n)))} est vraie donc :
\begin{center}{\tt 1<=b(k)=b(b(n))<=k=b(n)}\end{center}.
Posons {\tt j=n+1-b(n)}\\
{\tt P(n)} est vraie i.e. {\tt 1<=b(n)<=n} donc :\\
{\tt 1<=j=n+1-b(n)<=n} donc \\
{\tt P(j)} est vraie i.e. {\tt 1<=b(j)=b(n+1-b(n))<=j=n+1-b(n)} donc :
\begin{center}{\tt 1<=b(n+1-b(n))<=n+1-b(n)}\end{center}.
On a donc montrer que si pour tout {\tt 1<=k<=n} la propri'et\'e {\tt P(k)} est
vraie alors on a :\\
 {\tt 1<=b(b(n))<=b(n)} et {\tt 1<=b(n+1-b(n))<=n+1-b(n)}\\
ce qui est \'equivalent \`a :\\
{\tt 1+1<=b(n+1)=b(b(n))+b(n+1-b(n))<=b(n)+n+1-b(n)=n+1}
\section{Exercice}
{\bf \'Enonc\'e}\\
Montrer par r\'ecurrence que  pour tout {\tt n>=2} on a :\\
{\tt b(n)=b(n-1)} ou {\tt b(n)=b(n-1)+1}.\\
{\bf Correction}\\
Soit {\tt Q(n)} la propri\'et\'e :\\
pour tout {\tt n>=2} on a {\tt b(n)=b(n-1)} ou {\tt b(n)=b(n-1)+1}.\\
Ce qui signifie que lorsque {\tt n} augmente de 1, soit le "crapaud" se repose 
soit il  effectue un saut.\\
 Supposons que pour tout {\tt k<=n}, la propri\'et\'e {\tt Q(k)} est vraie et
 montrons qu'alors {\tt Q(n+1)} est vraie.\\
Par d\'efinition on a :\\
{\tt b(n+1)=b(b(n))+b(n+1-b(n))}\\
{\tt Q(n)}  est vraie (hypoth\`ese de r\'ecurrence) donc on a :\\
{\tt b(n)=b(n-1)} ou bien {\tt b(n)=b(n-1)+1}\\
\'Etudions chacune de ces 2 possibilit\'es :
\begin{enumerate}
\item Supposons que {\tt b(n)=b(n-1)} on a alors :\\
{\tt b(n+1)=b(b(n))+b(n+1-b(n))}  et \\
{\tt b(n)=b(b(n))+b(n-b(n))} (puisque on a supposé que {\tt b(n)=b(n-1)})
Comparons {\tt b(n-b(n))} et {\tt b(n+1-b(n)}).\\
Soit {\tt j=n+1-b(n)}
On a vu pr\'ec\'edemment que  pour tout {\tt n>=1} on a {\tt 1<=b(n)<=n}
et {\tt 1<=j=n+1-b(n)<=n} donc {\tt Q(j)} est vraie c'est \`a dire
{\tt b(j-1)=b(j)} ou {\tt b(j-1)+1=b(j)} donc \\
{\tt b(n-b(n))=b(n+1-b(n))} ou bien  {\tt b(n-b(n))+1=b(n+1-b(n))}\\
 ce qui signifie que  {\tt Q(n+1)}  est vraie.\\
\item Supposons que {\tt b(n)=b(n-1)+1} et montrons qu'alors 
{\tt Q(n+1)} est vraie.\\
On a alors {\tt b(n-1)=b(n)-1} donc :\\
{\tt b(n+1)=b(b(n))+b(n+1-b(n))}  et \\
{\tt b(n)=b(b(n)-1)+b(n+1-b(n))} (puisque on a supposé que {\tt b(n)=b(n-1)+1})
Comparons {\tt b(b(n))} et {\tt b(b(n)-1)}.\\
Soit {\tt j=b(n)}. On a vu pr\'ec\'edemment que  pour tout {\tt n>=1} on a
{\tt 1<=j=b(n)<=n}  donc {\tt Q(j)} est vraie donc 
{\tt b(j)=b(j-1)} ou {\tt b(j)=b(j-1)+1}\\
{\tt b(b(n))=b(b(n)-1)} ou {\tt b(b(n))=b(b(n)-1)+1}\\
donc on a :\\
{\tt b(b(n))=b(b(n)-1)} ou {\tt b(b(n))= b(b(n)-1)+1} \\ 
 ce qui signifie que {\tt b(n+1)=b(n)} ou bien {\tt b(n+1)=b(n)+1}\\
donc dans ce cas aussi {\tt Q(n+1)}  est vraie.\\
Donc on a montr\'e que :\\
pour tout {\tt n>=2} on a {\tt b(n)=b(n-1)} ou {\tt b(n)=b(n-1)+1}
\end{enumerate}
\section{Exercice}
\begin{enumerate}
\item Calculer les valeurs de {\tt b(k)} pour {\tt k=0..8}.
\item \'Ecrire un programme {\tt batracion(n)} qui calcule {\tt b(n)}
\item \'Ecrire un programme {\tt batrarc(n)} qui affiche le graphe de
{\tt b(n)/n} en fonction de {\tt n} pour {\tt 2<=n<=1000}
\item Modifier le programme pr\'ec\'edent pour tracer le graphe de
{\tt b(n)/n} en fonction de {\tt n} pour {\tt 1000<=n<=5000}
\end{enumerate}
\section{Solution}
1. Les 9 premi\`eres valeurs de {\tt b} sont :\\
{\tt b(0)=0;b(1)=1; b(2)=1,}\\
{\tt b(3)=b(b(2))+b(3-b(2))=b(1)+b(2)=2}\\
{\tt b(4)=b(b(3))+b(4-b(3))=b(2)+b(2)=2}\\
{\tt b(5)=b(b(4))+b(5-b(4))=b(2)+b(3)=3}\\
{\tt b(6)=b(b(5))+b(6-b(5))=b(3)+b(3)=4}\\
{\tt b(7)=b(b(6))+b(7-b(6))=b(4)+b(3)=4}\\
{\tt b(8)=b(b(7))+b(8-b(7))=b(4)+b(4)=4}\\
Ou bien on tape pour avoir les valeurs de {\tt b(k)} pour {\tt k=0..16} :\\
{\tt b:=0,1,1:;pour k de 3 jusque 16 faire b:=b,b[b[k-1]]+b[k-b[k-1]]; fpour;}
ou encore en \'evitant des recopies de {\tt b}, on modifie {\tt b} en place :\\
{\tt b:=0,1,1:;pour k de 3 jusque 16 faire b.append(b[b[k-1]]+b[k-b[k-1]]);fpour;}\\

2. On \'ecrit les programmes :\\
 {\tt Lb(n)} qui renvoie la suite {\tt (b(1),...b(n))} et \\
 {\tt batracion(n1,n2)} qui renvoie la suite {\tt (b(n1),...b(n2))} et \\
 {\tt b(n)} qui calcule la valeur de {\tt b(n)} \\
On tape :
\begin{verbatim}
Lb(n):={
  local k,bk,B,b1;
  B:=0,1,1;
  pour k de 3 jusque n faire 
    b1:=B[k-1];
    bk:=B[b1]+B[k-b1];
    B.append(bk);
  fpour;
retourne B;
  }:;
\end{verbatim}
\begin{verbatim}
batracion(n1,n2):={
  local k,b,B1,b1,B2;
  B1:=0,1,1;
  pour k de 3 jusque n1-1 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
  fpour;
  B2:=NULL;
  pour k de n1 jusque n2 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
    B2.append(b);
  fpour;
retourne B2;
  }:;
\end{verbatim}
\begin{verbatim}
b(n):={
  local k,b,B,b1;
 B:=0,1,1;
  pour k de 3 jusque n faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    B.append(b);
  fpour;
retourne B[n];
  }:; 
\end{verbatim}

On \'ecrit le programme {\tt batrarc(p)} qui renvoie 2 listes :\\
{\tt B} qui est la liste {\tt b(k)} pour {\tt k=1..2\verb|^|p)}\\
et \\
{\tt A} qui est la liste {\tt b(k)/k} pour {\tt k=1..2\verb|^|p} :
\begin{verbatim}
batrarc(p):={
 local k,b,b1,a,A,B;
  B:=0,1,1;
  A:=0,1,1/2;
  pour k de 3 jusque 2^p faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    a:=b/k;
    B.append(b);
    A.append(a);
  fpour;
  retourne [B],[A];
}:;
\end{verbatim}
On \'ecrit le programme {\tt batramax(p)} qui renvoie la liste :\\
{\tt DM} qui est la liste du  maximum des arches  $2^{n-1}..2^n$ \`a savoir :\\
{\tt [n-1,b(jm)/(jm} pour {\tt n=2..p-1)}\\
\begin{verbatim}
batramax(p):={
  local DM,k,j,A,a,m,jm;
  DM:=NULL;
  A:=batrarc(p)[1];
  pour k de 1 jusque p-1 faire
    m:=1/2; jm:=1;
    pour j de 2^k+1 jusque 3*2^(k-1) faire
      a:=A[j];
      si a>m alors jm:=j;m:=a; fsi;
    fpour;
  DM.append([jm-2^k,m]);
  fpour;
retourne [DM];
}:;
\end{verbatim}
On tape :\\
{\tt batramax(14)}\\
On obtient les maximum des arches $2^p..2^{p+1}$ pour {\tt p=1..13} :
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],
[114,207/370],[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],
[3459,6320/11651]]
\end{verbatim}
On tape :\\
{\tt batramax(24)}\\
On obtient (temps 89.73) le maximum des arches $2^p..2^{p+1}$ pour {\tt p=1..23}:\\
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],[114,207/370],
[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],[3459,6320/11651],
[5839,12002/22223],[12315,24290/45083],[23980,24037/44758],[50313,97226/181385],
[91539,189095/353683],[198301,385703/722589],[374502,758041/1423078],
[806412,1544473/2903564],[1502272,3024959/5696576],[3246708,6170687/11635316]]
\end{verbatim}
{\tt batramax(23)}\\
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],[114,207/370],
[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],[3459,6320/11651],
[5839,12002/22223],[12315,24290/45083],[23980,24037/44758],[50313,97226/181385],
[91539,189095/353683],[198301,385703/722589],[374502,758041/1423078],
[806412,1544473/2903564],[1502272,3024959/5696576],[3246708,6170687/11635316]]
\end{verbatim}
On a par exemple pour {\tt p=21}  les \'egalités :\\
{\tt 3*2\verb|^|20-e13,3*2\verb|^|20-242164,2\verb|^|21+806412,2903564}
\subsection{Des remarques}
On remarque que m11<M13<m10 en tapant :\\
{\tt 1662/3072<6320/11651<838/1536}\\
On obtient :\\
{\tt vrai}\\
On remarque que m13<M14<m12 en tapant :\\
{\tt 6606/12288<12002/22223<1662/3072}
On obtient :\\
{\tt vrai}\\
On remarque que m14<M15<m11 en tapant :\\
{\tt 6606/12288<24290/45083<1662/3072}\\
On obtient :\\
{\tt vrai}\\
On remarque que m17<M16<m13 en tapant :\\
{\tt 104739/196608<48074/89516<6606/12288}\\
On obtient :\\
{\tt vrai}
On remarque que m16<M17<m14 en tapant :\\
{\tt 52584/98304<97226/181385<13212/24576}\\
On obtient :\\
{\tt vrai}\\
On remarque que m18<M18<m16 en tapant :\\
{\tt 209478/393216<189095/353683<52584/983044}\\
On obtient :\\
{\tt vrai}\\
On remarque que m19<M19<m16 en tapant :\\
{\tt 417526/786432<385703/722589<52584/98304}\\
On obtient :\\
{\tt vrai}\\
On remarque que m20<M20<m15 en tapant :\\
{\tt 835052/1572864<758041/1423078<209478/393216}\\
On obtient :\\
{\tt vrai}\\
On remarque que m19<M21<m18 en tapant :\\
{\tt 835052/1572864<1544473/2903564<835052/1572864}\\
On obtient :\\
{\tt vrai}
On remarque que m19<M22<m18 en tapant :\\
{\tt 835052/1572864<3024959/5696576<209478/393216}\\
On obtient :\\
{\tt vrai}
On remarque que m21<M23<m20 en tapant :\\
{\tt 1665242/3145728<6170687/11635316<835052/1572864}
On obtient :\\
{\tt vrai}
%%%
\section{Comment transformer la liste {\tt L} en la liste {\tt T} ?}
Pour comprendre l'\'evolution de {\tt b(n)} en fonction de {\tt n} i.e. le 
parcours du candidat 4 (cf partie I), on va \'ecrire le 
programme {\tt LtoT(L)} qui tranforme liste {\tt L} des valeurs 
des distances au temps  {\tt n=2\verb|^|p..2\verb|^|(p+1)} en la liste {\tt T}
constitu\'ee successivement par le nombre de sauts et le nombre de pauses.\\
La fonction {\tt LtoT(L)} renvoie une liste de premier terme {\tt L[0]}
suivie de {\tt T} qui est la suite constitu\'ee successivement par le nombre de
 sauts et le nombre de pauses.
\subsection{Le programme effectuant cette transformation}
\begin{verbatim}
LtoT(L):={
//L est la liste b(2^p)....b(2^(p+1)+1) et LtoT(L) renvoie
//la liste (L[0],transf de b(2^p+1)....b(2^(p+1))
//n0 est le nbre de sauts et n1 le nbre de pauses
  local k,u0,u1,v0,v1,Rep,n0,n1,s;
  s:=size(L);
  Rep:=NULL;
  k:=1;
  tantque k<s-2 faire
  u0:=L[k];u1:=L[k+1];
  n0:=1;n1:=0;
  //afficher(k,u0,u1,n0,n1);
  tantque u0!=u1 and k<s-2 faire
    n0:=n0+1;
    k:=k+1;
    u0:=u1;
    u1:=L[k+1];
    //afficher(u0,u1,n0,n1);
 ftantque; 
  Rep:=Rep,n0;
 tantque u0==u1 and k<s-2 faire
    n1:=n1+1;
    k:=k+1;
    u0:=u1;u1:=L[k+1];
 // afficher(u0,u1,n0,n1);
ftantque; 
Rep:=Rep,n1;
k:=k+1;
ftantque;
return [L[0],Rep];
}:;
\end{verbatim}
{\tt V\'erification du programme {\tt LtoT(L)}}\\
On v\'erifie le r\'esultat sur le parcours du candidat 4 et on tape pour 
$n=2^3..2^4$ :\\
{\tt L(4):=[4,5,6,7,7,8,8,8,8]:;)}
{\tt T:=LtoT(L(4)}\\
On obtient : {\tt [3,1,1,3]}
En effet pour passer de 4 \`a 5, puis de 5 \`a 6, puis de 5 \`a 7, le crapaud 
fait 3 sauts, puis il se repose 1 fois, ensuite il saute 1 fois et passe de 7 
\`a 8 puis il fait 3 pauses. 
{\bf Bien voir} qu'il y a 1 saut si 2 nombres cons\'ecutifs sont diff\'erents 
et  il y a 1 pause si 2 nombres cons\'ecutifs sont \'egaux.
\subsection{On transforme le parcours du candidat 4}
On cherche maintenant \`a comprendre l'\'evolution du parcours du candidat 4.\\
On appelle {\tt B(p)} la liste {\tt L(p)} i.e la suite du candidat 4.\\
{\tt B(5)} est donc la suite des valeurs de $b(n)$ lorsque $n=0..2^5$ :\\
On tape :\\
{\tt B5:=B(5)}\\
On obtient :\\
{\tt (0,1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8,\\
9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16,17)}\\
On tape :\\
{\tt TB5:=LtoT(B5)}\\
On obtient :\\
{\tt [0,1,1,1,1,2,2,3,1,1,3,4,1,2,1,1,2,1,4]}\\
On a donc :\\
entre $2^0+1$ et $2^1]$ on a {\tt TB1=(1,1)}\\
entre $2^1+1$ et $2^2]$ on a {\tt TB2= (1,1)}\\
entre $2^2+1$ et $2^3]$ on a {\tt TB3=(2,2)}\\
entre $2^3+1$ et $2^4]$ on a {\tt TB4=(3,1,1,3)}\\
entre $2^4+1$ et $2^5]$ on a {\tt TB5=(4,1,2,1,1,2,1,4)}\\
On remarquera que ces listes sont :
\begin{itemize}
\item sym\'etriques (on a : {\tt revlist(4,1,2,1)=(1,2,1,4)}, 
\item elles sont de longueur $2^3$ lorsque $n\in [2^4+1..2^{5}]$,
\item elle d\'ebute par $p$ lorsque $n\in [2^p+1..2^{p+1}]$
\end{itemize}
On tape :\\
{\tt L(5)}\\
On obtient :\\
{\tt 16,17,18,19,20,21,21,22,23,24,24,25,26,26,27,27,27,28,\\29,29,30,30,30,31,31,31,31,32,32,32,32,32,32,33}\\
On tape :\\
{\tt T5:=LtoT(L(5))}\\
On obtient une liste commen\c{c}ant par $16=2^4$ qui est la valeur de $b(2^5)$ 
suivi par une suite sym\'etrique de longueur $2^4$ commen\c{c}ant par 
{\tt 5,1,3,1...} i.e. :\\
{\tt [16,5,1,3,1,2,1,1,2,2,1,1,2,1,3,1,5]}\\
On tape :\\
{\tt B6:=L(6)}\\
On obtient :\\
{\tt 32,33,34,35,36,37,38,38,39,40,41,42,42,43,44,45,45,46,47,47,48,48,48,\\
49,50,51,51,52,53,53,54,54,54,55,56,56,57,57,57,58,58,58,58,59,60,60,\\
61,61,61,62,62,62,62,63,63,63,63,63,64,64,64,64,64,64,64,65}\\
On tape :\\
{\tt T6:=LtoT(B6)}\\
On obtient une liste de longueur $32=2^5$ commen\c{c}ant par 
{\tt L6(2\verb|^|6)=2\verb|^|5=32}, puis par la suite commen\c{c}ant par 
{\tt 6,1,4,1,3,1,3,1,2,1,1,2}, puis par sa suite sym\'etrique. 
\begin{verbatim}
[32,6,1,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,1,6]
\end{verbatim}
On tape :\\
{\tt T7:=LtoT(L(7))}\\
On obtient une liste  commen\c{c}ant par $2^6=64$ puis par la suite :\\
{\tt 7,1,5,1,4,1,3,1,3,1,2,1,1,2,,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3} \\
puis par sa suite sym\'etrique :\\ 
{\tt  3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,2,1,1,2,1,3,1,4,1,5,1,7}\\
c'est \`a dire :
\begin{verbatim}
[64,7,1,5,1,4,1,3,1,3,1,2,1,1,2,,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,
1,3, 3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,2,1,1,2,1,3,1,4,1,5,1,7
\end{verbatim}
On tape :\\
{\tt T8:=LtoT(L(8))}\\
On obtient ne liste  commen\c{c}ant par $2^7=128$ puis par la liste :
\begin{verbatim}
[128,8,1,6,1,5,1,4,1,3,1,2,1,1,2,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2,
                         2,1,1,2,1,3,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2,
                         2,1,1,2,1,3,
\end{verbatim}
puis par sa liste sym\'etrique : 
\begin{verbatim}
3,1,2,1,1,2,
    2,1,1,2,1,3,
    2,1,1,2,1,3,1,4,
3,1,2,1,1,2,
    2,1,1,2,1,3,
    2,1,1,2,1,3,1,4,
    2,1,1,2,1,3,1,4,1,5,
    2,1,1,2,1,3,1,4,1,5,1,6,1,8]
\end{verbatim}
{\bf Attention}\\
 Pour \'eviter, d'avoir une premi\`ere ligne et une derni\`ere 
ligne diff\'erentes des autres lignes (le {\tt 6,1} suit le {\tt 8,1}), on 
remplace {\tt 8,1} par {\tt (1,0,7,1)} et {\tt 1,8} par {\tt (1,7,0,1)}.\\
On obtient : 
\begin{verbatim}
[1,0,
   7,1,
     6,1,5,1,4,1,3,1,2,1,1,2,
         5,1,4,1,3,1,2,1,1,2,
           4,1,3,1,2,1,1,2,
             3,1,2,1,1,2,
               2,1,1,2,1,3,
           4,1,3,1,2,1,1,2,
             3,1,2,1,1,2,
               2,1,1,2,1,3,
\end{verbatim}
suivi par sa liste sym\'etrique : 
\begin{verbatim}
  3,1,2,1,1,2,
    2,1,1,2,1,3,
  2,1,1,2,1,3,1,4,
  3,1,2,1,1,2,
    2,1,1,2,1,3,
  2,1,1,2,1,3,1,4,
2,1,1,2,1,3,1,4,1,5,
2,1,1,2,1,3,1,4,1,5,1,6,
                      1,7
                        0,1]
\end{verbatim}
On changera donc pour la suite des batracions la proc\'edure {\tt LtoT(L)} en 
{\tt BtoT(L)} en rajoutant \`a la fin les instructions ad\'equates :
\begin{verbatim}
BtoT(L):={
//L est la liste b(2^p)....b(2^(p+1)+1) et LtoT(L) renvoie
//la liste (L[0],transf de b(2^p+1)....b(2^(p+1))
  local k,u0,u1,v0,v1,Rep,n0,n1,s,sRep;
  s:=size(L);
  Rep:=NULL;
  k:=1;
  tantque k<s-2 faire
     u0:=L[k];u1:=L[k+1];
     n0:=1;n1:=0;
     tantque u0!=u1 and k<s-2 faire
       n0:=n0+1;
       k:=k+1;
       u0:=u1;
       u1:=L[k+1];
     ftantque; 
     Rep:=Rep,n0;
     tantque u0==u1 and k<s-2 faire
       n1:=n1+1;
       k:=k+1;
       u0:=u1;u1:=L[k+1];
     ftantque; 
     Rep:=Rep,n1;
     k:=k+1;
  ftantque;
  sRep:=size(Rep)-1;
  Rep[0]:=Rep[0]-1;
  Rep[sRep-1]:=Rep[sRep-1]-1;
  Rep:=1,0,Rep,0,1;
return [L[0],Rep];
}:;
\end{verbatim}
On appelle {\tt B(p)} la liste {\tt L4(p)} i.e la suite du candidat 4 :
\begin{verbatim}
B(p):={
 local k,uk,L,u1;
  L:=0,1,1;
  pour k de 3 jusque 2^(p+1)+1 faire 
    u1:=L[k-1];
    uk:=L[u1]+L[k-u1];
    L.append(uk);
  fpour;
retourne  eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
  }:;
\end{verbatim}
Pour obtenir le parcours du candidat 4 de $n=2^9$ \`a $2^{10}$, on tape :\\
{\tt B(9)}\\
On obtient le parcours du candidat 4 de $n=2^9$ \`a $2^{10}$ un r\'esultat qui 
est difficile \`a analyser :
\begin{verbatim}
256,257,258,259,260,261,262,263,264,265,265,266,267,268,269,270,271,272,272,273,
274,275,276,277,278,278,279,280,281,282,283,283,284,285,286,287,287,288,289,290,
290,291,292,292,293,293,293,294,295,296,297,298,299,299,300,301,302,303,304,304,
305,306,307,308,308,309,310,311,311,312,313,313,314,314,314,315,316,317,318,319,
319,320,321,322,323,323,324,325,326,326,327,328,328,329,329,329,330,331,332,333,
333,334,335,336,336,337,338,338,339,339,339,340,341,342,342,343,344,344,345,345,
345,346,347,347,348,348,348,349,349,349,349,350,351,352,353,354,354,355,356,357,
358,358,359,360,361,361,362,363,363,364,364,364,365,366,367,368,368,369,370,371,
371,372,373,373,374,374,374,375,376,377,377,378,379,379,380,380,380,381,382,382,
383,383,383,384,384,384,384,385,386,387,388,388,389,390,391,391,392,393,393,394,
394,394,395,396,397,397,398,399,399,400,400,400,401,402,402,403,403,403,404,404,
404,404,405,406,407,407,408,409,409,410,410,410,411,412,412,413,413,413,414,414,
414,414,415,416,416,417,417,417,418,418,418,418,419,419,419,419,419,420,421,422,
423,423,424,425,426,426,427,428,428,429,429,429,430,431,432,432,433,434,434,435,
435,435,436,437,437,438,438,438,439,439,439,439,440,441,442,442,443,444,444,445,
445,445,446,447,447,448,448,448,449,449,449,449,450,451,451,452,452,452,453,453,
453,453,454,454,454,454,454,455,456,457,457,458,459,459,460,460,460,461,462,462,
463,463,463,464,464,464,464,465,466,466,467,467,467,468,468,468,468,469,469,469,
469,469,470,471,471,472,472,472,473,473,473,473,474,474,474,474,474,475,475,475,
475,475,475,476,477,478,478,479,480,480,481,481,481,482,483,483,484,484,484,485,
485,485,485,486,487,487,488,488,488,489,489,489,489,490,490,490,490,490,491,492,
492,493,493,493,494,494,494,494,495,495,495,495,495,496,496,496,496,496,496,497,
498,498,499,499,499,500,500,500,500,501,501,501,501,501,502,502,502,502,502,502,
503,503,503,503,503,503,503,504,505,505,506,506,506,507,507,507,507,508,508,508,
508,508,509,509,509,509,509,509,510,510,510,510,510,510,510,511,511,511,511,511,
511,511,511,512,512,512,512,512,512,512,512,512,512,513,8}
\end{verbatim}
On tape :\\
{\tt T9:=BtoT(B(9))}\\
On obtient en ne tenant pas compte du terme $256=2^8$ d'indice 0 :
\begin{verbatim}
 1,0,
   8,1, 
     7,1,6,1,5,1,4,1,3,1,2,1,1,2,
         6,1,5,1,4,1,3,1,2,1,1,2,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2, 
                         2,1,1,2,1,3,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2,
                         2,1,1,2,1,3,
             4,1,3,1,2,1,1,2,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                     2,1,1,2,1,3,1,4,
\end{verbatim}
suivi par sa suite sym\'etrique :
\begin{verbatim}
4,1,3,1,2,1,1,2,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5, 
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5,
        2,1,1,2,1,3,1,4,1,5,1,6,
        2,1,1,2,1,3,1,4,1,5,1,6,1,7,
                                  1,8,
                                    0,1
\end{verbatim}
On peut voir des blocs se former, pour les d\'ecrire on va d\'efinir la suite 
{\tt Lc(n,k)} pour {\tt n>=k} et   on d\'efinit
{\tt Lc(n,k)} pour {\tt n<k} par {\tt Lc(n,k)=revlist(Lc(k,kn))}:\\
\begin{itemize}
\item pour $n\geq 1$ et $k=0 $, {\tt Lc(n,0)=(1,0)},
\item pour $n\geq 1$ et $k=1$, {\tt Lc(n,1)=(n,1)},
\item pour $n\geq 1$ et $k=2$, {\tt Lc(n,2)= (n,1,n-1,1...2,1,1,2)},
i.e. {\tt Lc(1,2)=(1,2)} et pour $n\geq 1$ {\tt Lc(n,2)=(n,1,Lc(n-1,2))}
\item pour $n\geq 2$ et $k=3$, {\tt Lc(n,3)= Lc(n,2),Lc(n-1,2)...,Lc(3,2),Lc(2,3)},
i.e. {\tt Lc(2,3)=(2,1,1,2,1,3)=revlist(3,1,2,1,1,2)} 

\end{itemize}
On a ainsi :\\
{\tt Lc(n,0)} la s\'equence {\tt (1,0)} ,\\
{\tt Lc(n,1)} la s\'equence {\tt (n,1)=(Lc(n,0),Lc(n-1,1))},\\
{\tt Lc(n,2)} la s\'equence {\tt (n,1,(n-1),1,....3,1,2,1,1,2)} i.e.\\
{\tt Lc(n,2)=(Lc(n,1),Lc(n-1,1)...Lc(3,1),Lc(2,1),1,2)}\\
{\tt Lc(n,3)} par {\tt (Lc(n,2),Lc(n-1,2),....Lc(3,2),Lc(2,2),1,3)}\\
{\tt Lc(n,4)} par {\tt Lc(n,3),Lc(n-1,3),....Lc(3,3),Lc(2,3),1,4}\\
......\\
{\tt Lc(n,k)} par {\tt Lc(n,k-1),Lc(n-1,k-1),....Lc(3,k-1),Lc(2,k-1),Lc(1,k)}\\
On a alors :\\ 
{\tt Lc(2,0)=(1,0)}, 
{\tt Lc(2,1)=(2,1)}\\
{\tt Lc(2,2)=(2,1,1,2)}\\
{\tt Lc(2,3)=2,1,1,2,1,3}\\
{\tt Lc(2,4)=2,1,1,2,1,3,1,4=revlist(Lc(4,2))}\\
{\tt Lc(3,3)=3,1,2,1,1,2,2,1,1,2,1,3}  \\
{\tt Lc(3,4)=3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4=revlist(Lc(4,3))}\\
{\tt Lc(4,2)=4,1,3,1,2,1,1,2}\\
{\tt Lc(4,3)=4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3} et \\
{\tt Lc(4,4)=Lc(4,3),Lc(3,4)}\\
On voit alors que  {\tt B(9)} est \'egal \`a :\\
{\tt (Lc(9,0),Lc(8,1),Lc(7,2),Lc(6,3),Lc(5,4),\\
Lc(4,5),Lc(3,6),Lc(2,7),Lc(1,8),Lc(0,9))}={\tt (Lc(9-k,k)\$(k=0..9))}\\
On a alors :\\
le premi\`ere ligne :\\
{\tt 1,0,8,1,} i.e.{\tt Lc(9,0),Lc(8,1),}\\
le deuxi\`eme bloc par :\\
{\tt  7,1,6,1,5,1,4,1,3,1,2,1,1,2,} i.e.{\tt Lc(7,2)}\\
le troisi\`eme bloc par :\\
{\tt 6,1,5,1,4,1,3,1,2,1,1,2,\\
5,1,4,1,3,1,2,1,1,2,\\
4,1,3,1,2,1,1,2,\\
3,1,2,1,1,2,\\
2,1,1,2,1,3,} i.e.{\tt Lc(6,3)=Lc(6,2),Lc(5,2),Lc(4,2),Lc(3,2),Lc(2,2),1,3}\\
le quatri\`eme bloc par :\\
{\tt 5,1,4,1,3,1,2,1,1,2,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3,\\
4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3,\\
3,1,2,1,1,2,2,1,1,2,1,3,\\
2,1,1,2,1,3,1,4,} i.e. {\tt Lc(5,4)=Lc(5,3),Lc(4,3),Lc(2,3),1,4}\\
Ainsi, on peut d\'ecrire {\tt B9}  par :\\
{\tt (Lc(9,0),Lc(8,1),Lc(7,2),Lc(6,3),Lc(5,4),Lc(4,5),Lc(3,6),Lc(2,7),Lc(1,8),Lc(0,9))}
\subsection{D\'efinition de {\tt Lc(n,k)}}
On a vu pr\'ec\'edemment que la suite des batracions entre $2^9$ et $2^{10}$ 
pouvait se traduire par :
\begin{verbatim}
 1,0,8,1, (i.e. 9,1)
     7,1,6,1,5,1,4,1,3,1,2,1,1,2,
         6,1,5,1,4,1,3,1,2,1,1,2,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2, 
                         2,1,1,2,1,3,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2,
                         2,1,1,2,1,3,
             4,1,3,1,2,1,1,2,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                     2,1,1,2,1,3,1,4,
\end{verbatim}
suivi par sa suite sym\'etrique :
\begin{verbatim}
4,1,3,1,2,1,1,2,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5, 
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5,
        2,1,1,2,1,3,1,4,1,5,1,6,
        2,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,0,1
\end{verbatim}
que l'on va traduire avec les d\'efinitions qui vont suivre par :\\
{\tt Lc(9,0),Lc(8,1),Lc(7,2),Lc(6,3),Lc(5,4),Lc(4,5),Lc(3,6),Lc(2,4),Lc(1,8),Lc(0,9)}\\
On remarquera que lorsque $p=9$, la somme des param\`etres vaut :\\
$p=9+0=8+2=7+3=...=9$.\\ 
{\bf Les d\'efinitions des suites} {\tt Lc(n,k)} :
\begin{itemize}
\item Pour tout {\tt n}, {\tt Lc(n,0)=(1,0)}  et\\
 {\tt Lc(0,n)=(0,1)}
\item Pour tout {\tt n>=1}, {\tt Lc(n,1)=(n,1)} et {\tt Lc(1,n)=(1,n)} 
On a alors : {\tt Lc(n,1)=(Lc(1,0),Lc((n-1),1))},
\item Pour {\tt n>=2}, on d\'efinit  :\\
{\tt Lc(n,2)}  par {\tt Lc(n,2)=(n,1,(n-1),1,....3,1,2,1,1,2)} et \\
et {\tt Lc(n,2)} par :{\tt Lc(2,n)= revlist(Lc(n,2))}.\\
ou encore \\
{\tt Lc(n,2)=(Lc(n,1),Lc((n-1),1),....Lc(3,1),Lc(2,1),1,2)}\\
On a alors :\\
{\tt Lc(2,2)} est \'egale \`a {\tt 2,1,1,2},\\
{\tt Lc(3,2)} est \'egale \`a {\tt 3,1,2,1,1,2} et\\
{\tt Lc(2,3)} est \'egale \`a {\tt 2,1,1,2,1,3}.\\
On a :\\
{\tt Lc(3,2)=Lc(3,1),Lc(2,2)==Lc(3,1),Lc(2,1),Lc(1,2)}
\item Pour {\tt n>=3}, on d\'efinit {\tt Lc(n,3)}  par  :\\
{\tt Lc(n,3)=(Lc(n,2),Lc(n-1,2),....Lc(3,2),Lc(2,2),Lc(1,3))}\\
et {\tt Lc(3,n)} par {\tt Lc(3,n)=revlist(Lc(n,3)} i.e. par :\\
{\tt Lc(1,3)=(1,3)}, {\tt Lc(2,3)=(2,1,1,2,1,3)}
On a alors :\\
{\tt Lc(2,3)} est \'egale \`a {\tt 2,1,1,2,1,3} et\\
{\tt Lc(3,3)} est \'egale \`a {\tt Lc(3,2),Lc(2,3)= 3,1,2,1,1,2,2,1,1,2,1,3},
\item Pour {\tt n>=4}, on d\'efinit {\tt Lc(n,4)} par :\\
{\tt Lc(n,4)=(Lc(n,3),Lc(n-1,3),....Lc(3,3),Lc(2,3),Lc(1,4))}\\
et {\tt Lc(4,n)} par {\tt Lc(4,n)=revlist(Lc(n,4)}\\
On a alors :\\
{\tt Lc(1,4)=(1,4)} , {\tt Lc(2,4)=(2,1,1,2,1,3,1,4)}
{\tt Lc(3,4)} est \'egale \`a {\tt (3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4)}
\item ......
\item Pour {\tt n>=k>=2}, on d\'efinit {\tt Lc(n,k)} par :\\
{\tt Lc(n,k)=(Lc(n,k-1),Lc(n-1,k-1),....Lc(3,k-1),Lc(2,k-1),Lc(1,k))} et\\
{\tt Lc(k,n)} par {\tt Lc(k,n)=revlist(Lc(n,k)}\\
On a alors :\\
{\tt Lc(2,k)} est \'egale \`a {\tt (2,1,1,2,1,3,1,4...1,k)}\\
{\tt Lc(3,k)} est \'egale \`a :
\begin{verbatim}
(3,1,2,1,1,2,
     2,1,1,2,1,3,
     2,1,1,2,1,3,1,4
    .....
     2,1,1,2,1,3,1,4...1,k-1,
     2,1,1,2,1,3,1,4...1,k-1,1,k)
\end{verbatim}
\end{itemize}

\subsection{Le programme des suites {\tt Lc(n,k)}}
\begin{verbatim}
Lc(p,m):={
  local k,L,Lf;
  L:=NULL; Lf:=NULL;
  si m>p alors return revlist(Lc(m,p)); fsi;
  si m==0 alors return (1,0) fsi;
  si m==1 alors return (p,1) fsi;
  pour k de p jusque 2 pas -1 faire 
    L:=L,Lc(k,m-1);
  fpour;
  L:=L,1,m;
  return L;
  }:;
\end{verbatim}
%%%%%
\section{Comment transformer la liste {\tt T} en la liste {\tt L} ?}
\'Ecrire un programme qui tranforme une liste {\tt T} qui a comme premier terme
la valeur de la distance de d\'epart en la liste {\tt L}.\\
Par exemple si {\tt T1} est la liste de longueur {\tt s} constitu\'ee 
successivement par le nombre de sauts et le nombre de pauses \`a partir du 
temps $t=T[0]=2^p$ jusqu'au temps $t=T[s-1]=2^{p+1}$, {\tt T=2\verb|p|,T1}:\\
{\tt T[0]=2\verb|^|p} et {\tt T[1]..T[s-1]} est la liste constitu\'ee 
successivement par le nombre de sauts et le nombre de pauses \`a partir du 
temps $t=T[0]=2^p$ jusqu'au temps $t=T[s-1]=2^{p+1}$.\\
On tape :
\begin{verbatim}
TtoL(T):={
local u0,uj,S,S1,j,k,L,s;
u0:=T[0];
j:=1;
L:=u0;j:=0;
s:=size(T)-2;
tantque j<=s faire
k:=1;
uj:=T[j]
tantque k<=uj faire
L:=L,u0+k;
k:=k+1;
ftantque;
u0:=u0+uj;
j:=j+1;
uj:=T[j];
k:=1;
tantque k<=uj faire
L:=L,u0;
k:=k+1;
ftantque;
j:=j+1;
ftantque;
return L;
}:;
\end{verbatim}
On tape :\\
{\tt L4(4)}\\
On obtient :\\
{\tt 8,9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16,17}\\
On tape :\\
{\tt T4:= LtoT(L4(4))}\\
On obtient :\\
{\tt [8,4,1,2,1,1,2,1,4]}\\
On tape :\\
{\tt TtoL(T4)}\\
On obtient :\\
{\tt 8,9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16}

\section{\'Etude fe la suite des pentemilieu}
\subsection{Coordonn\`ees des milieux de l'intervalle $[2^p,2^{p+1}]$}
Traitons tout d'abord 2 exemples : {\tt p=13} puis {\tt p=14}.
\begin{itemize}
\item {\tt p=13}\\
{\tt B13=(Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6),\\
Lc(6,7),Lc(5,8),Lc(4,9),Lc(3,10),Lc(2,11),Lc(1,12),Lc(0,13))}\\
L'indice {\tt n} du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|13+2\verb|^|12=3*2\verb|^|12}\\
puisque le milieu de l'intervalle $[2^{13},2^{14}]$ vaut 
$(2^{13}+2^{14})/2=(3*2^{13})/2=3*2^{12}$ 
Puisque le d\'eveloppement de $(1+1)^{13}$ est une somme ayant un nombre 
pair de termes, on a :\\
{\tt sum(comb(13,k) ,k=0..13)=2\verb|^|(13)|} et on a donc :\\
{\tt sum(comb(13,k),k=0..6)=2\verb|^|(12)} donc on a \\
 {\tt 3*2\verb|^|12=2\verb|^|13+sum(comb(13,k),k=0..6)} \\
La valeur {\tt b(n)} du milieu de B13 est donc \'egale \`a :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)}\\
Puisque {\tt comb(12,k)=comb(11,k)+comb(11,k-1)=comb(11,k)+comb(11,12-k)} on a:\\
{\tt 2\verb|^|11=sum(comb(11,k),k=0..11)=sum(comb(12,k),k=0..5)+comb(11,5)}\\
 la valeur {\tt b(n)} du milieu de B13 est donc \'egale \`a :\\
{\tt 3*2\verb|^|11+comb(11,5)}
\item {\tt p=14} \\
{\tt B14=(Lc(14,0),Lc(13,1),Lc(12,2),Lc(11,3),Lc(10,4),Lc(9,5),Lc(8,6),Lc(7,6)\\
Lc(6,7),Lc(6,8),Lc(5,9),Lc(4,10),Lc(3,11),Lc(2,12),Lc(1,13),Lc(0,14))}\\
Puisque le d\'eveloppement de $(1+1)^{14}$ est une somme ayant un nombre 
impair de termes,l'indice du milieu de B14 est \'egal \`a :\\
{\tt 2\verb|^|14+2\verb|^|13=2\verb|^|14+sum(comb(14,k),k=0..6)+comb(14,7)/2}\\
c'est aussi le milieu de l'intervalle $[2^{14},2^{15}]$ i.e. $2^{14}+2^{13}=3*2^{13}$.\\
La valeur du milieu de B14 est \'egal \`a :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)+comb(13,6)/2=3*2\verb|^|12+comb(12,6)}\\
c'est aussi  {\tt 3*2\verb|^|12+comb(12,6)}
\end{itemize}
{\bf Remarque}:
Pour $p=13$ et pour $p=14$ on a \'egalit\'e des pentes au milieu en effet :\\
puisque {\tt comb(12,6)=2*comb(11,5)}, on a :\\
{\tt 3*2\verb|^|12+comb(12,6)=2*(3*2\verb|^|11+comb(11,5))}\\
Cela se g\'en\'eralise puisque on a toujours :\\
{\tt comb(2n,n)=2*comb(2n-1,n-1)}\\
On tape (sans tenir compte de la remarque) :
\begin{verbatim}
vmilieu(p):={
  local v,m;
  v:=3*2^(p-2);
  m:=3*2^(p-1);
  si est_pair(p) alors 
    v:=v+comb(p-2,(p-2)/2);
  sinon
    v:=v+comb(p-2,(p-3)/2); 
     fsi;
  retourne [v,m,v/m];
  }:;
pentevn0(p):={
  local v,n,j,vd,nd,p0,p1,p2;
  vd:=2^(p-1);
  nd:=2*vd;
  p0:=1/2;p1:=1/2;
  p2:=(vd+p-1)/(nd+p);
  j:=1;
  tantque p2>p1 faire 
    j:=j+1;
    p0:=p1;p1:=p2;
    p2:=(vd+comb(p,j))/(nd+comb(p+1,j));
  ftantque;
  return [j-1,p1,p0,p2];
 }:;
pentevn(p):={
  local v,n,j,vd,nd,d0,d1,d2,f0,f1,f2,p0,p1,p2;
  vd:=2^(p-1);
  nd:=2*vd;
  p0:=1/2;p1:=1/2;
  p2:=(vd+p-1)/(nd+p);
  j:=1;
  tantque p2>p1 faire 
    j:=j+1;
    p0:=p1;p1:=p2;
    p2:=(vd+comb(p,j))/(nd+comb(p+1,j));
  ftantque;
  f0:=p-d0;f1:=p-d1;f2:=p-d2;
  return [j-1,d1,f1,d0,f0,d2,f2];
 }:;
Lcmax0(v0,n0,d,f):={
  local v1,n1,j,vd,nd,p0,p1,p2;
  vd:=v0;v1:=v0+comb(d+f-2,f-1);
  nd:=n0;n1:=n0+comb(d+f-1,f-1);
  p0:=v0/n0;p1:=v1/n1;
  j:=1;f:=f-1;
  tantque d>3 et p1>p0 faire 
    j:=j+1;d:=d-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v0+comb(d+f-2,f);
    n1:=n0+comb(d+f-1,f);
    p1:=v1/n1;
  ftantque;
  si d==2 alors f:=f+1;fsi;
  return [d,f,j-1,p1,p0];
 }:;
\end{verbatim}
\subsection{Limite de la suite des pentemilieu}
On tape :\\
\begin{verbatim}
pmil(p):={
return (3*2^(p-2)+comb(p-2,iquo(p-2,2)))/(3*2^(p-1));
}:;
ou bien
pmilieu(p):={
si est_pair(p) alors 
  return (3*2^(p-2)+comb(p-2,(p-2)/2))/(3*2^(p-1));
sinon 
  return (3*2^(p-2)+comb(p-2,(p-3)/2))/(3*2^(p-1));
 fsi;
}:;
\end{verbatim}
On tape :\\
{\tt pmil(17),pmil(18),pmil(19),pmil(20),pmil(21),pmil1(22)}\\
On obtient :\\
{\tt 34913/65536,34913/65536,208763/393216,208763/393216,832621/1572864,832621/1572864}
On remarque que {\tt pmil(2*p-1)=pmil(2*p)} ce qu'on d\'emontre 
facilement puisque :\\
lorsque {\tt p=2*n-1} les coordonn\`ees du milieu sont :\\
{\tt 3*2\verb|^|(2*n-2),3*2\verb|^|(2n-3)+comb(2n-3,n-2)} et 
lorsque  {\tt p=2*n} les coordonn\`ees du milieu sont :\\
{\tt 3*2\verb|^|(2*n-1),3*2\verb|^|(2n-2)+comb(2n-2,n-1)}.\\
On a :\\
{\tt 3*2\verb|^|(2*n-1)=2*(3*2\verb|^|(2*n-2))} et \\
puisque {\tt comb(2n-2,n-1)=comb(2n-3,n-1)+comb(2n-3,n-2)=2*comb(2n-3,n-1)}, on a :
{\tt 3*2\verb|^|(2n-2)+comb(2n-2,n-1)=2*(3*2\verb|^|(2n-3)+comb(2n-3,n-2))} \\
On tape pour {\tt p=2*n} :\\
{\tt limit((3*2\verb|^|(2*n-2)+comb(2*n-2,n-1))/(3*2\verb|^|(2*n-1)),n=+infinity)}\\
On obtient :\\
{\tt 1/2}\\
On tape pour {\tt p=2*n+1} :\\
{\tt limit((3*2\verb|^|(2*n-1)+comb(2*n-1,n-1))/(3*2\verb|^|(2*n)),n=+infinity)}\\
On obtient :\\
{\tt 1/2}\\
Donc la suite des milieux tend vers {\tt 1/2}.\\
Pour le montrer on se sert de l'\'equivalent de {\tt n!} au voisinage  de 
l'infini, \'equivalent obtenu gr\^ace \`a la fonction {\tt Gamma} (cf la d\'emonstration dans la partie III.

\section{Coordonn\'ees du maximum de b(n)/n pour $n\in[2^p...2^{p+1}]$}
%greLc.xws
\subsection{Prenons comme exemple p=13 puis p=14}
Si {\tt p=13} 
{\tt B13=(Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6),\\
Lc(6,17),Lc(5,8),Lc(4,9),Lc(3,10),Lc(2,11),Lc(1,12),Lc(0,1))}\\
l'indice du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)}\\
c'est aussi le milieu de l'intervalle $[2^{13},2^{14}]$ i.e. $3*2^{12}$\\
la valeur du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)}\\
c'est aussi  {\tt 3*2\verb|^|11+comb(11,5)}
\begin{verbatim}
Lcmax(p):={
  local v0,n0,mp,v1,n1,vd,nd,p0,p1,p2,d,f;
  si est_impair(p) alors v0:=3*2^(p-2)+comb(p-2,(p-3)/2);n0:=3*2^(p-1);
  d:=(p+1)/2;f:=(p-1)/2;
   v1:=v0-comb(p-1,f);n1:=n0-comb(p,f)
   p0:=v0/n0;p1:=v1/n1;
   tantque f>3 et p1>p0 faire 
    f:=f-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v1-comb(p,f);
    n1:=n1-comb(p-1,f);
    p1:=v1/n1;
  ftantque;
 return [p-f,f,p0];
 fsi;
 v0:=3*2^(p-2)+comb(p-2,(p-3)/2);n0:=3*2^(p-1);
  d:=p/2;f:=p/2-1; 
  v1:=v0-comb(p-2,f);n1:=n0-comb(p,f)
   p0:=v0/n0;p1:=v1/n1;
   tantque f>3 et p1>p0 faire 
    f:=f-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v0-comb(p,f);
    n1:=n0-comb(p-1,f);
    p1:=v1/n1;
  ftantque;
return [p-f,f,p0];
}:;
\end{verbatim}
On a :
\begin{verbatim}
nM(p):=nm(p)-comb(,);
bM(p):=bm(p)-comb(,);
\end{verbatim}
On tape :\\
{\tt nM(14),bM(14)}\\
On obtient :\\
{\tt 24576,13212}\\
On tape :\\
{\tt nM(15),bm(15)}\\
On obtient :\\
{\tt 49152,26292}\\
On v\'erifie, on tape :\\
{\tt b(89516),b(48074)}\\
On obtient :\\
{\tt 13212,26292}\\
On tape :\\
{\tt nm(14),bm(14)}\\
On obtient :\\
{\tt }

\begin{verbatim}
//Lc(a,b) est la liste Lc avant le milieu et vd,nd sont la valeur et l'indlce 
//avant Lc((a,b)
vn(a,b,vd,nd):={
  local L,v,n,j,s,k;
  L:=Lc(a,b);
  s:=size(L)-1;
  return [vd+sum(L[j],j,0,k,2),nd+sum(L[j],j,0,k)];
  }:;
Max(a,b,vd,nd):={
   local L,s,VN,k,j;
   L:=Lc(a,b);
   s:=size(L)-1;
   VN:=NULL;
   pour k de 0 jusque s faire 
   VN:=VN,[vd+sum(L[j],j,0,k,2),nd+sum(L[j],j,0,k)]
   fpour;
   //return VN;
   return max([(VN[k,0]/VN[k,1])$(k=0..s)]);
   }:;
\end{verbatim}
On tape :\\
{\tt Max(4,3,3*2\verb|^|5-comb(5,3),3*2\verb|^|6-comb(7,3))}\\
On obtient :\\
{\tt 101/178}\\
On tape :\\
{\tt Max(5,4,3*2\verb|^|7-comb(7,3),3*2\verb|^|8-comb(9,4))}\\
On obtient :\\
{\tt 399/719}\\
On tape :\\
{\tt Max(6,5,3*2\verb|^|9-comb(9,4),3*2\verb|^|10-comb(11,5))}\\
On obtient :\\
{\tt 1586/2897}\\
On tape :\\
{\tt Max(7,6,3*2\verb|^|11-comb(11,5),3*2\verb|^|12-comb(13,6))}\\
On obtient :\\
{\tt 6320/11651}\\
On tape :\\
{\tt Max(8,7,3*2\verb|^|13-comb(13,6),3*2\verb|^|14-comb(15,7))}\\
On obtient :\\
{\tt 24290/45083}\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }
\subsection{Une tentative pour trouver le maximum de l'arche}
On \'ecrit le progpamme qui renvoie la liste {\tt Lc(a,b)}.\\
On tape :
\begin{verbatim}
Lc(a,b):={
  local k,L,Lf;
  L:=NULL; Lf:=NULL;
  si a<0 ou b<0 alors return NULL; fsi;
  si b>a alors return revlist(Lc(b,a)); fsi;
  si b==0 alors return (1,0) fsi;
  si b==1 alors return (a,1) fsi;
  pour k de a jusque 2 pas -1 faire 
    L:=L,Lc(k,b-1);
  fpour;
  L:=L,1,b;
  return L;
  }:;
\end{verbatim}
Puis on cherche le maximum de {\tt Lc(a,b)} lorsque l'indice de d\'epart vaut 
{\tt xd} et la valeur de d\'epart vaut {\tt yd}
On suppose dans un premier temps que {\tt a} est impair.\\
On tape 
\begin{verbatim}
TrajetLc(a,b,xd,yd):={
  //a+b=2n+1
  local k,L,s,Rep,xn,yn,pn;
    L:=Lc(a,b);
    //afficher(L);
    Rep:=NULL;
    s:=(size(L)-1);
    xn:=xd;yn:=yd;pn:=yn/xn;
        pour k de 0 jusque s pas 2 faire 
    yn:=yn+L[k];xn:=xn+L[k];pn:=yn/xn; 
        Rep:=Rep,pn;
    xn:=xn+L[k+1];
      fpour;
   return max([Rep]);
    }:;  
      
\end{verbatim}
On tape pour {\tt p=3} :\\
{\tt TrajetLc(2,1,9,5)}\\
On obtient :\\
{\tt 7/11}\\
On tape pour {\tt p=5}  :\\
{\tt TrajetLc(3,2,38,21)}\\
On obtient :\\
{\tt 13/22}\\
On tape pour {\tt p=7} :\\
{\tt TrajetLc(4,3,3*2\verb|^|6-comb(7,3),3*2\verb|^|5+comb(5,2)-comb(6,3))}\\
On obtient :\\
{\tt 101/178}\\
On tape {\tt p=9} :\\
{\tt TrajetLc(5,4,3*2\verb|^|8-comb(9,4),3*2\verb|^|7+comb(7,3)-comb(8,4))}\\
On obtient :\\
{\tt 399/719}\\
On tape pour {\tt p=11} :\\
{\tt TrajetLc(6,5,3*2\verb|^|10-comb(11,5),3*2\verb|^|9+comb(9,4)-comb(10,5))}\\
On obtient :\\
{\tt 1586/2897}\\
On tape pour {\tt p=13} :\\
{\tt TrajetLc(7,6,3*2\verb|^|12-comb(13,6),3*2\verb|^|11+comb(11,5)-comb(12,6))}\\
On obtient :\\
{\tt 6320/11651}\\
On tape {\tt p=15} :\\
{\tt TrajetLc(8,7,3*2\verb|^|14-comb(15,7),3*2\verb|^|13+comb(13,6)-comb(14,7))}\\
On obtient :\\
{\tt 24290/45083}\\
On tape pour {\tt p=17} :\\
{\tt TrajetLc(9,8,3*2\verb|^|16-comb(17,8),3*2\verb|^|15+comb(15,7)-comb(16,8))}\\
On obtient :\\
{\tt 97226/181385}\\
On tape pour {\tt p=19} :\\
{\tt TrajetLc(10,8,3*2\verb|^|18-comb(19,9),3*2\verb|^|17+comb(17,8)-comb(18,9))}\\
On obtient :\\
{\tt 385703/722589}\\
On tape pour {\tt p=21} :\\
{\tt TrajetLc(11,9,3*2\verb|^|20-comb(21,10),3*2\verb|^|19+comb(19,9)-comb(20,10))T}\\
On obtient  temps de l'\'evaluation 78.04:\\
{\tt 1544473/2903564}\\
Le temps \'etant trop long il faut am\'eliorer le programme !
\subsection{Combien de Lc(6,6) dans Lc(n,q) pour n>q?}
\begin{itemize}
\item si $q<6$ il y a 0 {\tt Lc(6,6)}\\
\item si $q=6+0$ il y a 1={\tt comb(n-6,0)} {\tt Lc(6,6)}\\
\item si $q=7=6+1$ on a {\tt Lc(n,7)=(n,6),(n-1,6)...(8,6),(7,6),(6,6),(5,7)}\\
Puisque $6=n-(n-6)$, dans {\tt Lc(n,7)} il y a $n-5$={\tt comb(n-5),1)} {\tt Lc(6,6)}\\
\item si $q=8=6+2$ on a {\tt Lc(n,8)=(n,7),(n-1,7)...(8,7),(7,7),(6,7),(5,7)}\\
Donc il y a : $(n-5)+(n-6)+...+(n-(n-1))=\frac{(n-4)*(n-5)}{2}$={\tt comb(n-4),2)}\\
\item si $q=9=6+3$ on a {\tt Lc(n,9)=(n,8),(n-1,8)...(8,8),(7,8),(6,8),(5,8)}\\
Donc il y a :\\
$\frac{(n-4)*(n-5)}{2}+\frac{(n-5)*(n-6)}{2}+...+\frac{2*1}{2}$\={\tt comb(n-3),3)}\\
\item par récurrence on a donc pour $q=q-6+6$ :\\
si {\tt n>q}, dans {\tt Lc(n,q)} il y a {\tt comb(n+q-12, q-6)} {\tt Lc(6,6)}
\end{itemize}
{\bf Remarque} Si {\tt q<n)} on en d\'eduit par sym\'etrie que le nombre de 
{\tt Lc(6,6)} dans {\tt Lc(q,n)} et le m\^eme que dans {\tt Lc(n,q)} i.e. 
{\tt comb(n+q-12, q-6)}.\\
Si {\tt n==q)} on en d\'eduit que le nombre de 
{\tt Lc(6,6)} dans {\tt Lc(n,n)} est 2* fois celui de {\tt Lc(n,n-1)} i.e.
{\tt 2*comb(n+n-13,n-7)}
On tape :
\begin{verbatim}
nb66(n,q):={
si n>q alors return comb(n+q-12,q-6);fsi;
si n==q alors 
  si q==6 alors return 1; sinon 
     return 2*comb(2*n-13,n-7);
  fsi;
fsi;
si n<q alors return comb(n+q-12,q-6);fsi;
}:;
\end{verbatim}

\subsection{O\`u se trouve le maximum de l'arche $2^p..2^{p+1}$ ?}
On sait que la suite du nombre de  sauts $s(n)$ et du nombre de pauses $r(n)$ 
sont sym\'etriques par rapport \`a $n=xm=3*2^{p-1}$ qui est le 
milieu de l'intervalle $2^p..2^{p+1}$  et on sait que 
pour tout $n$ $s(n)>p(n)$. Donc le maximum de l'arche se trouve losque $n$ se 
trouve dans la premi\`ere moiti\'e de l'arche. 
En effet, cherchons o\`u trouve le maximum pour diff\'erentes valeurs de $p$.\\
\begin{itemize}
\item Pour $p=13$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6)}\\
En d\'ecomposant {\tt Lc(7,6)} on a :\\
{\tt Lc(7,6)=Lc(7,5),Lc(6,5),Lc(6,6)}\\
En d\'ecomposant {\tt Lc(6,6)} on a :\\
{\tt Lc(6,6)=Lc((6,5),(5,4),(4,3),(3,2),(2,1),(1,2),(2,3),(3,4),(4,5),(5,6))}\\
En effet on a :\\
{\tt Lc((3,2),(2,1),(1,2),(2,3))=Lc((3,2),(2,2),(2,3))=Lc((3,3))} etc..\\
Le milieu de l'arche a comme coordonn\`ees :\\
$xm13=3*2^{13-1}=12288$ et $ym13=3*2^{13-2}+comb(13-2,(13-3)/2)=6606$\\
Avec le programme {\tt batramax}, on a trouvé que le point de pente maximum a 
pour coordonn\`ees   :\\
$xM13=11651$ et $yM13=6320$\\
On note :\\
{\tt xe13=xm13-xM13=637} et {\tt ye13=xm13-yM13=286}\\
On a :\\
{\tt comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(3,1)+1=comb(14,4)-comb(14,3)=comb(13,4)-comb(13,2)=637}\\
et que \\
{\tt comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(2,0)=comb(13,3)=286}\\
On a d\'ecompose le premier {\tt Lc(6,6)} rencontr\'e.\\
On a :\\
{\tt Lc(6,6)=(6,5),(5,4),(4,3),(3,2),}{\bf [(2,1)]},{\tt (1,2),(2,3),(3,4),(4,5),(5,6))}\\
Donc le maximum est atteint \`a la fin du deuxi\`eme saut de {\tt Lc(2,1)}. 

\item Pour $p=14$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(14,0),Lc(13,1),Lc(12,2),Lc(11,3),Lc(10,4),Lc(9,5),Lc(8,6),Lc(7,6)}\\
En d\'ecomposant {\tt Lc(8,6)} on a :\\
{\tt (8,6),(7,6)=(8,5),(7,6),(7,6))=(8,5),(7,5),}{\bf [(6,6)]},{\tt (7,6)}\\
En d\'ecomposant {\tt Lc(6,6)} comme pr\'ec\'edament on a :\\
{\tt  (8,6),(7,6)=(8,5),(7,5),(6,5),(5,4),(4,3),(3,2),}{\bf [(2,1)]},{\tt (1,2),(2,3),(3,4),(4,5),(5,6))(7,6)}.\\
On a d\'ecompos\'e le deuxi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=14$, le point de 
pente maximum a pour coordonn\`ees $xM14=22223$ et $yM14=12002$.\\
On note :\\
{\tt xe14=xm14-xM14=2353} et {\tt ye14=xm14-yM14=1210}\\
On a :\\
{\tt comb(13,6)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=432+636=2353}\\
et \\
{\tt comb(12,6)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=924+286=1210}\\
Donc le maximum est atteint \`a la fin du deuxi\`eme saut de {\tt Lc(2,1)}. 

\item Pour $p=15$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(15,0),Lc(14,1),...,Lc(9,6),Lc(8,7)}\\
En d\'ecomposant {\tt Lc(8,7)} on a :\\
{\tt (8,7)=(8,6),(7,7)=(8,5),(7,6),(7,7))=(8,5),(7,5),}{\bf [(6,6)]},{\tt (7,7)}\\
On d\'ecompose {\tt Lc(6,6)} comme pour $p=13$ et on a :\\
{\tt  (8,7))=(8,5),(7,5),(6,5),(5,4),(4,3),(3,2),}{\bf [(2,1)]},{\tt (1,2),(2,3),(3,4),(4,5),(5,6))(7,6),(7,7)}\\
On a d\'ecompos\'e le troisi\`eme {\tt Lc(6,6)} rencontr\'e.\\
 Avec le programme {\tt batramax} on a trouv\'e que pour $p=15$, le point de 
pente maximum a pour coordonn\`ees $xM15=45083$ et $yM15=24290$.\\
On note :\\
{\tt xe15=xm15-xM15=4069} et {\tt ye15=xm15-yM15=2002}\\
On a :\\
{\tt comb(14,7)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=3432+637=4069}\\
et \\
{\tt comb(13,6)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=1716+286=2002}\\
Donc {\tt xe15=comb(14,7)+637} et {\tt ye15=comb(13,6)+286}

\item Pour $p=16$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(16,0),Lc(15,1),...,Lc(10,6),Lc(9,7),Lc(8,7)}\\
En d\'ecomposant {\tt Lc(9,7)} on a :\\
{\tt (9,7),(8,7)=(9,6),(8,6)},{\bf(7,7)},{\tt (8,7)= (9,6),(8,6),(7,5)},{\bf(6,6)},{\tt (6,7),(8,7)}\\
On a utilis\'e le quatri\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=16$, le point de 
pente maximum a pour coordonn\`ees $xM16=89516$ et $yM16=48074$.\\
Donc :\\
{\tt xe16=xm16-xM16=8788} et {\tt ye16=xm16-yM16=4510}\\
On a :\\
{\tt comb(15,7)+comb(13,6)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=8151+637=8788}\\
et \\
{\tt comb(14,7)+comb(12,5)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=4224+286=4510}

\item Pour $p=17$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(17,0),Lc(16,1),...,Lc(11,6),Lc(10,7),Lc(9,8)}\\
On d\'ecompose {\tt Lc(9,8)} on a :\\
{\tt (9,8)=[(9,7)],(8,8)=(9,6),(8,6),(7,5),}{\bf[(6,6)]},{\tt (6,7),(8,8)}\\
On a utilis\'e le septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=17$, le point de 
pente maximum a pour coordonn\`ees $xM17=181385$ et $yM17=97226$.\\
Donc :\\
{\tt {\tt xe17=xm17-xM17=15223} et {\tt ye17=xm17-yM17=7513}
On a :\\
{\tt comb(16,8)+comb(13,6)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=14586+637=15223}\\
et \\
{\tt comb(15,8)+comb(12,5)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=7227+286=7513}

\item Pour $p=18$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(18,0),Lc(17,1),...,Lc(11,7),Lc(10,8),Lc(9,8)}\\
On d\'ecompose {\tt Lc(10,8)} on a :\\
{\bf [(10,8)},{\tt (9,8)=(10,7)},{\bf[(9,7)]},{\tt (8,8),(9,8)}=\\
{\tt (10,7),(9,6),{\bf[(8,7)]},{\tt (8,8),(9,8)}=\\
{\tt (10,7),(9,6),(8,6),(7,5)},{\bf[(6,6)]},{\tt (6,7),(8,8),(9,8)}\\
On a utilis\'e le dix septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=18$, le point de 
pente maximum a pour coordonn\`ees $xM18=353683$ et $yM18=189695$.\\
Donc :\\
{\tt xe18=xm18-xM18=39533} et {\tt ye18=xm18-yM18=20383}\\
On a :\\
{\tt comb(17,8)+comb(16,8)+comb(13,6)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=38896+637=39533}\\
et \\
{\tt comb(16,8)+comb(15,8)+comb(12,5)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=20097+286=20383}

\item Pour $p=19$.\\
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(19,0),Lc(18,1),...,Lc(11,8),Lc(10,9)}\\
On d\'ecompose {\tt Lc(10,9)} on a :\\
{\tt (10,9)={\bf [(10,8)]},{\tt (9,9)=(10,7)},{\bf[(9,7)]},{\tt (8,8),(9,9)}=\\
{\tt (10,7),(9,6),(8,6),(7,5)},{\bf[(6,6)]},{\tt (6,7),(8,8),(9,9)}\\
On a utilis\'e le vingt septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=19$, le point de 
pente maximum a pour coordonn\`ees $xM19=353683$ et $yM19=189695$.\\
Donc :\\
{\tt xe19=xm19-xM19=39533} et {\tt ye19=xm19-yM19=20383}\\
On a :\\
{\tt comb(18,9)+comb(16,8)+comb(13,6)+637=63843}\\
{\tt comb(17,9)+comb(15,7)+comb(12,5)+286=31823}

\item Pour $p=20$.\\}
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(20,0),Lc(19,1),...,Lc(11,9),Lc(10,9)}\\
On d\'ecompose {\tt Lc(11,9)} on a :\\
{\bf [(11,9)]},{\tt (10,9)=(11,8)},(10,7)},({\bf[(9,8)]},{\tt (9,9),(10,9)}=\\
{\tt (11,8)},(10,7),(9,7),{\bf[(8,7)]},{\tt (7,8),(9,9),(10,9)}=\\
{\tt(11,8)},(10,7),(9,7),(8,6),(7,5),{\bf[(6,6)]},{\tt(6,7),(7,8),(9,9),(10,9)}\\
On a utilis\'e le vingt septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=20$, le point de 
pente maximum a pour coordonn\`ees $xM20=1423078$ et $yM20=758041$.\\
Donc :\\
{\tt xe20=xm20-xM20=149786} et {\tt ye20=xm20-yM20=77011}\\
On a :\\
{\tt comb(19,9)+comb(18,9)+comb(15,7)+comb(13,6)+637=149786}\\
{\tt comb(17,9)+comb(15,7)+comb(12,5)+286=77011}

\item Pour $p=21$.\\}
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(21,0),Lc(20,1),...,Lc(12,9),Lc(11,10)}\\
On d\'ecompose {\tt Lc(11,10)} on a :\\
{\tt (11,10)=(11,9),(10,9)},{\bf[(9,9)]},{\tt (8,10)}=\\
{\tt (11,8)},(10,7),(9,7),{\bf[(8,6)]},{\tt (6,7),(7,8),(9,9),(10,9)}=\\
{\tt(11,8),(10,7),(9,7),(8,5),(7,5)},{\bf[(6,6)]},{\tt(6,7),(7,8),(9,9),(10,10)}\\
{\tt(11,10)=(11,9),(10,10)=(11,8),(10,7),(9,7),(8,6),(7,7),(7,8),(9,9),(10,10)}=\\
{\tt (11,8),(10,7),(9,7),(8,6),(7,5)},{\bf[(6,6)]},{\tt(6,7),(7,8),(9,9),(10,10)
On a utilis\'e le vingt septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=20$, le point de 
pente maximum a pour coordonn\`ees $xM20=1423078$ et $yM20=758041$.\\
Donc :\\
{\tt xe21=xm21-xM21=242164} et {\tt ye21=xm21-yM21=120769}\\
On a :\\
{\tt comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637=242164}\\
{\tt comb(19,9)+comb(17,8)+comb(14,6)+comb(12,5)+286=120769}
On a aussi :\\
{\tt xe21=xe16+comb(20,10)+comb(18,9)}\\
{\tt ye21=ye16+comb(19,9)+comb(17,8)-comb(13,4)+comb(13,3)=ye16+comb(19,9)+comb(17,8)-comb(12,4)+comb(12,2)}

\item Pour $p=22$.\\}
La premi\`ere moiti\'e de l'arche est d\'ecrite par les listes :\\
{\tt Lc(22,0),Lc(21,1),...,Lc(13,9),Lc(12,10),Lc(11,10)}\\
On d\'ecompose {\tt Lc(12,10)} on a :\\
{\tt (12,10),(11,10)=(12,9),(11,10),(11,10)=}\\
{\tt (12,9),(11,8)},{\bf [(10,9)]},{\tt (10,10),(11,10)}=\\
{\tt(12,9),(11,8),[(10,8),(9,7)},{\bf[(8,7)]},{\tt(7,8),(8,9)],(10,10),(11,10)}\\
{\bf[(8,7)]},{\tt(7,8),(8,9)],(10,10),(11,10)}={\tt (8,6),(7,6)},{\bf[(6,6)]},
{\tt (6,7),(7,8),(9,9),(10,10),(11,10)}
\\
On a utilis\'e le vingt septi\`eme {\tt Lc(6,6)} rencontr\'e.\\
Avec le programme {\tt batramax} on a trouv\'e que pour $p=20$, le point de 
pente maximum a pour coordonn\`ees $xM20=5696576$ et $yM20=3024959$.\\
Donc :\\
{\tt xe22=xm22-xM22=594880} et {\tt ye22=xm22-yM22=305525}\\
On tape :\\
{\tt comb(21,10)+comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637}\\
On obtient :\\
{\tt 594880}\\
On tape :\\
{\tt comb(20,10)+comb(19,9)+comb(17,9)+comb(14,6)+comb(12,5)+286}
On obtient :\\
{\tt 305525}\\

\item Pour $p=23$.\\
On tape :\\
{\tt comb(22,11)+comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637}\\
On obtient :\\
{\tt 947596}\\
On tape :\\
{\tt comb(21,10)+comb(19,9)+comb(17,8)+comb(14,6)+comb(12,5)+286}\\
On obtient :\\
{\tt 473485}\\
{\tt (12,11)=(12,10),(11,11)=(12,9),(11,9),(10,10),(11,11)}\\
{\tt (12,11)=(12,9),(11,10)},{\bf [(10,9)]},{\tt(10,10),(11,11)}

\item Pour $p=24$.\\
On tape :\\
{\tt comb(22,11)+comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)=+637comb(21,10)+comb(19,9)+comb(17,8)+comb(14,6)+comb(12,5)+286}\\
On obtient :\\
{\tt }\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
{\tt  (13,11),(12,11)=(13,11)=(12,9),(11,9),(10,10),(11,11)}\\
{\tt (12,11)=(12,9),(11,10),[(10,9)],(10,10),(11,11)}\\
{\tt comb(23,11)+comb(22,11)}\\
{\tt //p=24 (13,11),(12,11)=(13,10),(12,11),(12,11)=(13,10),(12,10),(11,10),(10,11),(11,11),(12,11)}
{\tt //p=23 (13,10),(12,10),(11,10),(10,10),(9,9),(8,10),(8,9),(7,10),(6,11),(11,11),(12,11)}\\
835052/1572864,(3*2\verb|^|18+comb(18,9))/(3*2\verb|^|19),(3*2\verb|^|22+comb(22,11))/(3*2\verb|^|23)
0.530911763509,0.530911763509,0.528031349182
comb(23,11)+947896,comb(22,11)+305525,(3*2\verb|^|22+comb(22,11)-comb(22,11)-305525)/(3*2\verb|^|23-comb(23,11)-947896)
2299974,1010957,0.536931144042
\item Pour $p=25$.\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
\item Pour $p=26$.\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
\item Pour $p=27$.\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\

\end{itemize}
\section{La suite des pentemaximum}
On peut trouver cette suite en utilisant les programmes pr\'ec\'edents 
rappel\'es ici) et les programmes {\tt batramax1(p)} (resp {\tt batramax2(p)},
{\tt batramax3(p)}, {\tt batramaxn(p,n)}) qui donne la pentemaximum de l'arche 
$[2^p,2^{p+1}]$ (resp la pentemaximum des arches $[2^p,2^{p+1}]$ et $[2^p,2^{p+2}]$ 
la pentemaximum des arches $2^p..2^{p+1}$, $2^p..2^{p+2}$ et $2^p..2^{p+3}$,la 
pentemaximum des arches $[2^p..2^{p+1}],... [2^{p+n-1}..2^{p+n}]$).\\
On tape :\\
\begin{verbatim}
Lc(p,m):={
  local k,L,Lf;
  L:=NULL; Lf:=NULL;
  si m>p alors return revlist(Lc(m,p)); fsi;
  si m==0 alors return (1,0) fsi;
  si m==1 alors return (p,1) fsi;
  pour k de p jusque 2 pas -1 faire 
    L:=L,Lc(k,m-1);
  fpour;
  L:=L,1,m;
  return L;
  }:;
batracion(n1,n2):={
  local k,b,B1,b1,B2;
  B1:=0,1,1;
  pour k de 3 jusque n1-1 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
  fpour;
  B2:=NULL;
  pour k de n1 jusque n2 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
    B2.append(b);
  fpour;
retourne B2;
  }:;
b(n):={
  local k,b,B,b1;
 B:=0,1,1;
  pour k de 3 jusque n faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    B.append(b);
  fpour;
retourne B[n];
  }:; 
batrarc(p):={
 local k,b,b1,a,A,B;
  B:=0,1,1;
  A:=0,1,1/2;
  pour k de 3 jusque 2^p faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    a:=b/k;
    B.append(b);
    A.append(a);
  fpour;
  retourne [B],[A];
}:;
batramax(p):={
  local DM,k,j,A,a,m,jm;
  DM:=NULL;
  A:=batrarc(p)[1];
  pour k de 1 jusque p-1 faire
    m:=1/2; jm:=1;
    pour j de 2^k+1 jusque 3*2^(k-1) faire
      a:=A[j];
      si a>m alors jm:=j;m:=a; fsi;
    fpour;
  DM.append([jm-2^k,m]);
  fpour;
retourne [DM];
}:;
batramax1(p):={
 local k,a,A,B;
  B:=batracion(2^p,2^(p+1));
  A:=[1/2];
  pour k de 1 jusque 2^p faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
  retourne max([A]);
}:;
batramax2(p):={
 local j,k,a,A,B,Max;
 Max:=NULL;
  B:=batracion(2^p,2^(p+2));
  A:=[1/2];
  pour k de 1 jusque 2^(p) faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
 Max:=Max,max([A]);
 A:=[1/2];
 pour k de 2^p+1 jusque 2^(p+1) faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
Max:=Max,max([A]);
retourne Max;
}:;
batramax3(p):={
 local j,k,a,A,B,Max;
 Max:=NULL;
  B:=batracion(2^p,2^(p+3));
  A:=[1/2];
  pour k de 1 jusque 2^p faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
 Max:=Max,max([A]);
 A:=[1/2];
 pour k de 2^p+1 jusque 2^(p+2)-2^p faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
Max:=Max,max([A]);
A:=[1/2];
 pour k de 2^(p+2)-2^p+1 jusque 2^(p+3)-2^p faire 
      a:=B[k]/(2^(p)+k);
    A.append(a);
  fpour;
Max:=Max,max([A]);
retourne Max;
}:;
batramaxn(p,n):={
 local j,k,a,A,B,Max;
 Max:=NULL;
  B:=batracion(2^p,2^(p+n));
  pour j de 0 jusque n-1 faire 
    A:=[1/2];
   pour k de 2^(p+j)-2^p+1 jusque 2^(p+1+j)-2^p faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
  Max:=Max,max([A]);
 fpour;
retourne Max;
}:;
batramaxpn(p,n):={
 local j,k,a,A,B,Max;
 Max:=NULL;
  B:=batracion(2^p,2^(p+n));
  pour j de 0 jusque n-1 faire 
    A:=[1/2];
   pour k de 2^(p+j)-2^p+1 jusque 2^p*(3*2^(j-1)-1) faire 
    a:=B[k]/(2^p+k);
    A.append(a);
  fpour;
  Max:=Max,max([A]);
 fpour;
retourne Max;
}:;
\end{verbatim}
On tape pour avoir la pentemaximum des arches $[2^3,2^4],[2^4,2^5],..[2^{3+20}..2^{3+21}]$:\\
{\tt batramaxn(3,21)}\\
On obtient (Temps mis pour l'évaluation: 115.5) :\\
{\tt 7/11,14/23,13/22,53/92,101/178,207/370,399/719,818/1487,1586/2897,3248/5969,6320/11651,12002/22223,24290/45083,24037/44758,97226/181385,189095/353683,385703/722589,758041/1423078,1544473/2903564,3024959/5696576,6170687/11635316,}\\
On tape :\\
{\tt batramax1(24)}\\
On obtient (Temps mis pour l'évaluation: 162.44) :\\
{\tt 12109427/22866150}
\subsection{Un exercice et sa correction}
{\bf \'Enonc\'e}\\
\`A l'aide des fonctions {\tt Lc(n,k)} d\'ecrire les trajets :\\
{\tt T5,T6,T7,T8}\\
{\bf Correction}\\
On a :\\
{\tt T5=(1,0,4,1,3,1,2,1,1,2,2,1,1,2,1,3,1,4,0,1)}\\
Donc :\\
{\tt T5=(Lc(5,0),Lc(4,1),Lc(3,2),Lc(2,3),Lc(1,4),Lc(0,1))}\\
ou bien :\\
{\tt T5=(Lc(5,0),Lc(4,1),Lc(3,3),Lc(1,4),Lc(0,1))}\\
On a :\\
{\tt T6=(1,0,5,1,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,1,5,0,1)}\\
Donc :\\
{\tt T6=(Lc(6,0),Lc(5,1),Lc(4,2),Lc(3,2),Lc(2,3),Lc(2,4),Lc(1,5),Lc(0,6))}\\
ou bien :\\
{\tt T6=(Lc(6,0),Lc(5,1),Lc(4,4),Lc(1,5),Lc(0,6))}\\
On a {\tt T7=} :\\
{\tt 1,0,6,1,5,1,4,1,3,1,2,1,1,2,4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3,\\
    3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,2,1,1,2,1,3,1,4,1,5,1,7)}\\
Donc {\tt T7=} :\\
{\tt (Lc(7,0),Lc(6,1),Lc(5,2),Lc(4,3),Lc(3,4),Lc(2,5),Lc(1,6),Lc(0,7))}\\
ou bien :\\
{\tt T7=(Lc(7,0),Lc(6,1),Lc(5,3),Lc(3,5),Lc(1,6),Lc(0,7))}\\
On a :
\begin{verbatim}
T8=(1,0,7,1,
        6,1,5,1,4,1,3,1,2,1,1,2,
            5,1,4,1,3,1,2,1,1,2,
                4,1,3,1,2,1,1,2,
                    3,1,2,1,1,2,
                        2,1,1,2,1,3,
            4,1,3,1,2,1,1,2,
                3,1,2,1,1,2,
                    2,1,1,2,1,3,
            3,1,2,1,1,2,
                2,1,1,2,1,3,
                2,1,1,2,1,3,1,4,
             3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4,
                 2,1,1,2,1,3,1,4,1,5,2,1,1,2,1,3,1,4,1,5,1,6,1,8)
\end{verbatim}
Donc {\tt T8=} :\\
{\tt (Lc(8,0),Lc(7,1),Lc(6,2),Lc(5,3),Lc(4,4),Lc(3,5),Lc(2,6),Lc(1,7),Lc(0,1))}\\
ou bien :\\
{\tt T8=(Lc(8,0),Lc(7,1),Lc(6,3),Lc(4,3),Lc(3,4),Lc(3,6),Lc(1,7),Lc(0,1))}\\
et on a :\\
{\tt T9=(Lc(9,0),Lc(8,1),Lc(7,3),Lc(5,4),Lc(4,5),Lc(3,7),Lc(1,8),Lc(0,1))}

\part*{Partie III} 
La partie III consiste \`a rappeler certaines propri\'et\'es des combinaisons.\\
\section{D\'efinition}
On a pour pour $1\leq$ {\tt n} et {\tt p}$\leq$ {\tt n}:\\
{\tt comb(n,p)=}$\displaystyle \frac{n!}{p!(n-p)!}=\frac{n(n-1)...(n-p+1)}{p!}$.\\
On tape :\\
{\tt comb(7,0)}\\
On obtient :\\
{\tt 1}\\
On tape :\\
{\tt comb(7,1)}\\
On obtient :\\
{\tt 7}\\
On tape :\\
{\tt comb(7,2)}\\
On obtient :\\
{\tt 21}\\
On tape :\\
{\tt comb(7,3)}\\
On obtient :\\
{\tt 35}\\
en effet $(7*6*5)/3!=7*5=35$\\
On tape :\\
{\tt comb(7,0)}\\
On obtient :\\
{\tt 1}\\
en effet $(7*6*5)/3!=7*5=35$
\section{Propri\'et\'es de base}
On a pour $1\leq $ {\tt n} et {\tt p}$\leq$ {\tt n} :\\
{\tt comb(n,p)}=$\frac{n!}{p!*(n-p)!}=\frac{n*(n-1)*...*(n-p+1)}{p!}$.\\
On a :\\
{\tt comb(n,p)=comb(n,n-p)}\\
{\tt comb(n,p)=n/p*comb(n-1,p-1)}\\
{\tt comb(n,p)=(n-p+1)/p*comb(n,p-1)}\\
 Pour {\tt n>0} on a {\tt comb(n,p)=comb(n-1,p-1)+comb(n-1,p)}\\
 {\tt n} \'etant fix\'e l'application {\tt m-> comb(n,m)} est croissante.
\section{Propri\'et\'es utilisant la formule du bin\^ome}
\begin{itemize}
\item Rappel de la formule du bin\^ome\\
On a pour $n\in \N$ et $x\in \R$ :\\
{\tt Sn=(1+x)\verb|^|n=$\displaystyle\sum_{k=0}^n$ comb(n,k)*x\verb|^|k}
\item En rempla\c{c}ant dans {\tt Sn}, {\tt x} par 1 on obtient :\\
{\tt sum(comb(n,k),k=0..n)=2\verb|^|n}\\
Si $n=2p+1$, {\tt Sn} a alors un nombre pair de termes et puisque 
{\tt comb(n,p)=comb(n,n-p)}, on a :\\
{\tt sum(comb(2p+1,k),k=0..p)=2\verb|^|(2p-1)}\\
Par exemple :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)=3*2\verb|^|12=12288}\\
Si $n=2p$, {\tt Sn} a alors un nombre impair de termes.  \\
Puisque {\tt comb(n,p)=comb(n,n-p)} et que \\
{\tt comb(2*p,p)=2*comb(2*p-1,p-1)=2*comb(2*p-1,p)} on a :\\
{\tt sum(comb(2*p,k),k=0..p-1)+comb(2*p,p)/2=}\\
{\tt sum(comb(2*p,k),k=0..p-1)+comb(2*p-1,p-1)=2\verb|^|(2p-1)}\\
Par exemple :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)=3*2\verb|^|11+comb(11,5)=6606}
Cela servira pour trouver l'expression de la suite des milieux des arches  
correspondant au parcours du candidat 4.
\item En rempla\c{c}ant  $x$ par 1 dans {\tt Sn}, on obtient :\\
{\tt a=sum(comb(n,k),k=0..n)=2\verb|^|n} et \\
en rempla\c{c}ant $x$ par -1 dans {\tt Sn}, on obtient :\\
{\tt b=sum((-1)\verb|^|k*comb(n,k),k=0..n)=0}
En calculant {\tt a+b} et {\tt a-b} on en d\'eduit que :\\
{\tt a+b=2+2*comb(n,2)+2*comb(n,4)+2*comb(n,6)....=2\verb|^|n}\\
{\tt a-b= 2*comb(n,1)+2*comb(n,3)+2*comb(n,5)....=2\verb|^|n}\\
On d\'efinit :\\
{\tt S0n=}$\displaystyle \sum_{k=0}^{p}{\tt comb(n,2k+1)}$ si $n=2p$ et\\
{\tt S0n=}$\displaystyle \sum_{k=0}^{p-1}{\tt comb(n,2k+1)}$ si $n=2p+1$ \\
{\tt S1n=}$\displaystyle \sum_{k=0}^{p}{\tt comb(n,2k-1)}$ si $n=2p$ et\\
{\tt S1n=}$\displaystyle \sum_{k=0}^{p-1}{\tt comb(n,2k)}$ si $n=2p+1$ \\
On a alors : $S0n=S1n=2^{n-1}$\\
Par exemple :\\
{\tt sum(comb(8,2*k),k=0..4)=sum(comb(8,2*k-1),k=0..4)=128=2\verb|^|7}\\
{\tt sum(comb(9,2*k),k=0..4)=1+sum(comb(9,2*k-1),k=0..4)=256=2\verb|^|8}\\
{\tt sum(comb(16,2*k),k=0..8)=sum(comb(16,2*k-1),k=0..8)=32768=2\verb|^|7}\\
{\tt sum(comb(17,2*k),k=0..8)=1+sum(comb(17,2*k-1),k=0..8)=65536=2\verb|^|8}\\
\item On montre par r\'ecurrence que :\\
{\tt comb(p,p)+comb(p+1,p)+...+comb(p+(n-p),p)=comb(n+1,p+1)=comb(n-p,p+1)}
{\tt comb(p,0)+comb(p+1,1)+...+comb(p+(n-p),n-p)=comb(n+1,p+1)}
Par exemple :\\
{\tt comb(5,0)+comb(6,1)+comb(7,2)+comb(8,3)=comb(9,6)}\\
car on a ici {\tt p=5} et {\tt n=8}
{\tt comb(7,0)+comb(8,1)+comb(9,2)+comb(10,3)+comb(11,4)=comb(12,8)}\\
car on a ici {\tt p=7} et {\tt n=11}
\section{Les combinaisons et la fonction Gamma}
{\bf D\'efinition de la fonction Gamma}\\
La fonction Gamma  est d\'efinie pour {\tt a>0} par :\\
{\tt Gamma(a)=}$\int_0^{inf}t^{a-1}e^{-t}dt$\\
{\bf Propri\'et\'es}\\
Lorsque {\tt a} est un entier {\tt n>0} on a :\\
{\tt Gamma(n)=}$\int_0^{inf}x^{n-1}e^{-x}dx$\\
On a alors :\\
{\tt Gamma(1)=1}\\
{\tt Gamma(n+1)=n*Gamma(n)}\\
On a donc :\\
{\tt Gamma(n+1)=n!}\\
On peut montrer que {\tt Gamma(1/2)=}$\sqrt{\pi}$\\
Lorsque {\tt n} est grand la formule asymptotique de {\tt Gamma(n)} est :\\
{\tt Gamma(n+1)=}$\sqrt{2n\pi}n^ne^{-n}e^{\theta/(12*(n+1))}$ avec $0<\theta<1$.\\
Quand {\tt n} tend vers l'infini on a une formule asymptotique pour $n!$ :\\
{\tt n!=Gamma(n+1)}$\simeq \sqrt{2n\pi}n^ne^{-n}$
\section{Exercice}
Montrer que {\tt comb(2*n,n)/(3*2\verb|^|(n+1))} tend vers 0 quand {\tt n} tend vers $+\infty$.\\
Montrer que {\tt comb(2*n,n)/(2\verb|^|2*n)} tend vers 0 quand {\tt n} tend vers $+\infty$.\\
On a :\\
{\tt n!}$\simeq \sqrt{2n\pi}n^ne^{-n}$ donc\\
{\tt comb(2*n,n)=}$\frac{2n!}{n!*n!}\simeq \frac{2^{2*n}}{\sqrt{n\pi}}$\\
donc :\\
{\tt comb(2*n,n)/(2\verb|^|2*n}$\simeq \frac{1}{\sqrt{n\pi}}$\\
donc {\tt comb(2*n,n)/(3*2\verb|^|(n+1))} tend vers 0 quand {\tt n} tend vers 
$+\infty$.\\
Avec {\tt Xcas}, on tape :\\
{\tt limit(comb(2*n,n)/(2\verb|^|(2*n)),n=+infinity)}\\
On obtient :\\
{\tt 0}
\end{itemize}
\end{document}
2. Pourquoi la suite {\tt b(n)} est-elle définie ?
Pour cela, montrons par r\'ecurrence que pour tout {\tt n>=1} on a {\tt 1<=b(n)<=n}.\\
On a \\
{\tt 1<=b(2)=1<=2}\\{\tt 1<=b(3)=2<=3}\\
Soit {\tt P(n)} la propri'et\'e {\tt 1<=b(n)<=n}
Supposons que pour tout {\tt k<=n} {\tt P(k)} soit vraie i.e. que l'on a :\\
{\tt 1<=b(k)<=k}\\
Est ce que cela entraine que {\tt P(n+1)} est vraie ?
Soit {\tt k=b(n)} puisque {\tt P(n)} est vraie 
qu'alors pour tout {\tt 1<=k<=n} on a {\tt 1<=b(k)<=k}.\\Il faut donc montrer que {\tt 1<=b(n)<=n}.\\Posons {\tt p=b(n-1)}, on a :\\{\tt 1<=p=b(n-1)<=n-1} et aussi \\{\tt n-(n-1)=1<=n-b(n-1)=n-p<=n-1} donc \\ d'apr\`es l'hypoth\`ese de r\'ecurrence si {\tt 1<=p<=n-1} alors on a :\\{\tt 1<=b(p)=b(b(n-1))<=p-1} et aussi si {\tt 1<=n-p<=n-1} alors on a :\\{\tt n-(n-1)=1<=b(n-p)=b(n-b(n-1))<=n-p<=n-1} \\cela entraine que :\\{\tt b(n)=b(p)+b(n-p)} est d\'efinie et on a :\\{\tt 1<=2<=b(n)=b(b(n-1))+b(n-b(n-1))=b(p)+b(n-p)<=p-1+n-p-1=n-2<=n-1}.\\




\part*{Partie II}
\section{D\'efinition}
Les batracions sont des suites fractales ayant une structure auto-similaire 
quand on les examine \`a diff\'erentes \'echelles.\\
Voici un exemple de batracion, c'est la suite {\tt b(n)} d\'efinie par :\\
{\tt b(0)=0}\\
{\tt b(1)=1}\\
{\tt b(2)=1}\\
{\tt b(n)=b(b(n-1))+b(n-b(n-1))} pour {\tt n>2}\\
{\bf Attention} {\tt b(2)} ne v\'erifie pas la relation de r\'ecurrence et
{\tt b(0)=0} ne sert pas.\\
\section{Exercice}
\begin{enumerate}
\item Calculer les valeurs de {\tt b(k)} pour {\tt k=0..8}.
%\item Montrer que pour tout {\tt n>= 1} on a {\tt 1<=b(n)<=n}. En d\'eduire que {\tt b(n)} est bien d\'efinie par la relation de r\'ecurrence pour {\tt n>=3}.
\item \'Ecrire un programme {\tt batracion(n)} qui calcule {\tt b(n)}
\item \'Ecrire un programme {\tt batrarc(n)} qui affiche le graphe de
{\tt b(n)/n} en fonction de {\tt n} pour {\tt 2<=n<=1000}
\item Modifier le programme pr\'ec\'edent pour tracer le graphe de
{\tt b(n)/n} en fonction de {\tt n} pour {\tt 1000<=n<=5000}
\end{enumerate}
\section{Solution}
1. Les 9 premi\`eres valeurs de {\tt b} sont :\\
{\tt b(0)=0;b(1)=1; b(2)=1,}\\
{\tt b(3)=b(b(2))+b(3-b(2))=b(1)+b(2)=2}\\
{\tt b(4)=b(b(3))+b(4-b(3))=b(2)+b(2)=2}\\
{\tt b(5)=b(b(4))+b(5-b(4))=b(2)+b(3)=3}\\
{\tt b(6)=b(b(5))+b(6-b(5))=b(3)+b(3)=4}\\
{\tt b(7)=b(b(6))+b(7-b(6))=b(4)+b(3)=4}\\
{\tt b(8)=b(b(7))+b(8-b(7))=b(4)+b(4)=4}\\
Ou bien on tape pour avoir les valeurs de {\tt b(k)} pour {\tt k=0..16} :\\
{\tt b:=0,1,1:;pour k de 3 jusque 16 faire b:=b,b[b[k-1]]+b[k-b[k-1]]; fpour;}
ou encore en \'evitant des recopies de {\tt b}, on modifie {\tt b} en place :\\
{\tt b:=0,1,1:;pour k de 3 jusque 16 faire b.append(b[b[k-1]]+b[k-b[k-1]]);fpour;}\\

2. Pourquoi la suite {\tt b(n)} est-elle définie ?
Pour cele, montrons par r\'ecurrence que pour tout {\tt n>=1} on a {\tt 1<=b(n)<=n}.\\
On a \\
{\tt 1<=b(2)=1<=2}\\{\tt 1<=b(3)=2<=3}\\
Soit {\tt P(n)} la propri'et\'e {\tt 1<=b(n)<=n}
Supposons que pour tout {\tt k<=n} {\tt P(k)} soit vraie i.e. que l'on a :\\
{\tt 1<=b(k)<=k}\\
Est ce que cela entraine que {\tt P(n+1)} est vraie ?
Soit {\tt k=b(n)} puisque {\tt P(n)} est vraie 
qu'alors pour tout {\tt 1<=k<=n} on a {\tt 1<=b(k)<=k}.\\Il faut donc montrer que {\tt 1<=b(n)<=n}.\\Posons {\tt p=b(n-1)}, on a :\\{\tt 1<=p=b(n-1)<=n-1} et aussi \\{\tt n-(n-1)=1<=n-b(n-1)=n-p<=n-1} donc \\ d'apr\`es l'hypoth\`ese de r\'ecurrence si {\tt 1<=p<=n-1} alors on a :\\{\tt 1<=b(p)=b(b(n-1))<=p-1} et aussi si {\tt 1<=n-p<=n-1} alors on a :\\{\tt n-(n-1)=1<=b(n-p)=b(n-b(n-1))<=n-p<=n-1} \\cela entraine que :\\{\tt b(n)=b(p)+b(n-p)} est d\'efinie et on a :\\{\tt 1<=2<=b(n)=b(b(n-1))+b(n-b(n-1))=b(p)+b(n-p)<=p-1+n-p-1=n-2<=n-1}.\\
2. On \'ecrit les programmes :\\
 {\tt Lb(n)} qui renvoie la suite {\tt (b(1),...b(n))} et \\
 {\tt batracion(n1,n2)} qui renvoie la suite {\tt (b(n1),...b(n2))} et \\
 {\tt b(n)} qui calcule la valeur de {\tt b(n)} \\
On tape :
\begin{verbatim}
Lb(n):={
  local k,bk,B,b1;
  B:=0,1,1;
  pour k de 3 jusque n faire 
    b1:=B[k-1];
    bk:=B[b1]+B[k-b1];
    B.append(bk);
  fpour;
retourne B;
  }:;
\end{verbatim}
\begin{verbatim}
batracion(n1,n2):={
  local k,b,B1,b1,B2;
  B1:=0,1,1;
  pour k de 3 jusque n1-1 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
  fpour;
  B2:=NULL;
  pour k de n1 jusque n2 faire 
    b1:=B1[k-1];
    b:=B1[b1]+B1[k-b1];
    B1.append(b);
    B2.append(b);
  fpour;
retourne B2;
  }:;
\end{verbatim}
\begin{verbatim}
b(n):={
  local k,b,B,b1;
 B:=0,1,1;
  pour k de 3 jusque n faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    B.append(b);
  fpour;
retourne B[n];
  }:; 
\end{verbatim}
\begin{verbatim}
batrarc(n):={
local
}:;
\end{verbatim}
On \'ecrit le programme {\tt batracon(p)} qui renvoie 2 listes :\\
{\tt B} qui est la liste {\tt b(k)} pour {\tt k=1..2\verb|^|p)}\\
et \\
{\tt A} qui est la liste {\tt b(k)/k} pour {\tt k=1..2\verb|^|p} :
\begin{verbatim}
batracon(p):={
 local k,b,b1,a,A,B;
  B:=0,1,1;
  A:=0,1,1/2;
  pour k de 3 jusque 2^p faire 
    b1:=B[k-1];
    b:=B[b1]+B[k-b1];
    a:=b/k;
    B.append(b);
    A.append(a);
  fpour;
  retourne [B],[A];
}:;
\end{verbatim}
On \'ecrit le programme {\tt batramax(p)} qui renvoie la liste :\\
{\tt DM} qui est la liste du  maximum des arches  $2^{n-1}..2^n$ \`a savoir :\\
{\tt [n-1,b(jm)/(jm} pour {\tt n=2..p-1)}\\
\begin{verbatim}
batramax(p):={
  local DM,k,j,A,a,m,jm;
  DM:=NULL;
  A:=batracon(p)[1];
  pour k de 1 jusque p-1 faire
    m:=1/2; jm:=1;
    pour j de 2^k+1 jusque 3*2^(k-1) faire
      a:=A[j];
      si a>m alors jm:=j;m:=a; fsi;
    fpour;
  DM.append([jm-2^k,m]);
  fpour;
retourne [DM];
}:;
\end{verbatim}
On tape :\\
{\tt batramax(14)}\\
On obtient les maximum des arches $2^p..2^{p+1}$ pour {\tt p=1..13} :
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],
[114,207/370],[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],
[3459,6320/11651]]
\end{verbatim}
On tape :\\
{\tt batramax(24)}\\
On obtient (temps 89.73) les maximum des arches $2^p..2^{p+1}$ pour {\tt p=1..23}:\\
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],[114,207/370],
[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],[3459,6320/11651],
[5839,12002/22223],[12315,24290/45083],[23980,24037/44758],[50313,97226/181385],
[91539,189095/353683],[198301,385703/722589],[374502,758041/1423078],
[806412,1544473/2903564],[1502272,3024959/5696576],[3246708,6170687/11635316]]
\end{verbatim}
{\tt batramax(23)}\\
\begin{verbatim}
[[1,2/3],[2,2/3],[3,7/11],[7,14/23],[12,13/22],[28,53/92],[50,101/178],[114,207/370],
[207,399/719],[463,818/1487],[849,1586/2897],[1873,3248/5969],[3459,6320/11651],
[5839,12002/22223],[12315,24290/45083],[23980,24037/44758],[50313,97226/181385],
[91539,189095/353683],[198301,385703/722589],[374502,758041/1423078],
[806412,1544473/2903564],[1502272,3024959/5696576],[3246708,6170687/11635316]]
\end{verbatim}
On a par exemple pour {\tt p=21}  les \'egalités :\\
{\tt 3*2\verb|^|20-e13,3*2\verb|^|20-242164,2\verb|^|21+806412,2903564}
\subsection{Des remarques}
On remarque que m11<M13<m10 en tapant :\\
{\tt 1662/3072<6320/11651<838/1536}\\
On obtient :\\
{\tt vrai}\\
On remarque que m13<M14<m12 en tapant :\\
{\tt 6606/12288<12002/22223<1662/3072}
On obtient :\\
{\tt vrai}\\
On remarque que m14<M15<m11 en tapant :\\
{\tt 6606/12288<24290/45083<1662/3072}\\
On obtient :\\
{\tt vrai}\\q
On remarque que m17<M16<m13 en tapant :\\
{\tt 104739/196608<48074/89516<6606/12288}\\
On obtient :\\
{\tt vrai}
On remarque que m16<M17<m14 en tapant :\\
{\tt 52584/98304<97226/181385<13212/24576}\\
On obtient :\\
{\tt vrai}\\
On remarque que m18<M18<m16 en tapant :\\
{\tt 209478/393216<189095/353683<52584/983044}\\
On obtient :\\
{\tt vrai}\\
On remarque que m19<M19<m16 en tapant :\\
{\tt 417526/786432<385703/722589<52584/98304}\\
On obtient :\\
{\tt vrai}\\
On remarque que m20<M20<m15 en tapant :\\
{\tt 835052/1572864<758041/1423078<209478/393216}\\
On obtient :\\
{\tt vrai}\\
On remarque que m19<M21<m18 en tapant :\\
{\tt <1544473/2903564<835052/1572864}\\
On obtient :\\
{\tt vrai}
On remarque que m19<M22<m18 en tapant :\\
{\tt 835052/1572864<3024959/5696576<209478/393216}\\
On obtient :\\
{\tt vrai}
On remarque que m21<M23<m20 en tapant :\\
{\tt 1665242/3145728<6170687/11635316<835052/1572864}
On obtient :\\
{\tt vrai}

\section{Transformons la liste {\tt L=batracion}$(2^p,2^{p+1}+1)$}
{\tt trans(L)} renvoie la valeur de {\tt L[0]} suivie de la liste transform\'ee 
{\tt Lt} qui est obtenue en notant au f\^ur et \`a mesure  le nombre de sauts 
successifs, le nombre de pauses successives quand $n\in 2^p+1....2^{p+1}$. 
\begin{verbatim}
trans(L):={
 //L est la liste batracion(2^p,2^(p+1)+1) et trans(L)=[L[0],Lt] 
  local k,b0,b1,v0,v1,Rep,n0,n1,s;
  s:=size(L);
  Rep:=NULL;
  k:=1;
  tantque k<s-2 faire
  b0:=L[k];b1:=L[k+1];
  n0:=1;n1:=0;
  //afficher(k);
  //afficher(b0,b1,n0,n1);
  tantque b0!=b1 and k<s-2 faire
    n0:=n0+1;
    k:=k+1;
    b0:=b1;
    b1:=L[k+1];
    //afficher(b0,b1,n0,n1);
 ftantque; 
  Rep:=Rep,n0;
 tantque b0==b1 and k<s-2 faire
    n1:=n1+1;
    k:=k+1;
    b0:=b1;b1:=L[k+1];
 // afficher(b0,b1,n0,n1);
Rep:=Rep,n1;
k:=k+1;
ftantque; 
//Rep[0]:=Rep[0]-1;Rep[size(Rep)-1]:=Rep[0];Rep:=(1,0,Rep,0,1);
return [L[0],Rep];}:;
}:;
\end{verbatim}
On tape la liste des batracions $b(n)$ qui varient entre  $2^3$ et $2^4+1$ 
lorsque $n$ varie entre $2^4$ et $2^5+1$:\\
{\tt L:=8,9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16,17}\\
{\tt V0:=L[0],Lt:=trans(L)}\\
On obtient :\\
{\tt 8,[0,4,1,2,1,1,2,1,4]}\\
 cela veut dire que :\\
{\tt L[0]=8} puis {\tt L} augmente 4 fois de 1  donc :\\
{\tt L[1]=9,L[2]=10,L[3]=11,L[4]=12}
puis reste  1 fois \`a la valeur pr\'ec\'edente donc :\\
{\tt L[5]=12}\\
puis {\tt L} augmente 2 fois de 1 donc :\\
{\tt L[6]=13,L[7]=14}\\
puis reste 1 fois \`a la valeur pr\'ec\'edente  donc :\\
{\tt L[8]=14}\\,
puis {\tt L} augmente 1 fois de 1 donc :\\
{\tt L[9]=15}\\
puis reste 2 fois \`a la valeur pr\'ec\'edente  donc :\\
{\tt L[10]=15,L[11]=15}
puis{\tt L}  augmente 1 fois de 1 donc :\\
{\tt L[12]=16}\\
puis reste 4 fois \`a la valeur pr\'ec\'edente  donc :\\
{\tt L[13]=16,L[14]=16,L[15]=16,L[16]=16}\\
\section{Les programmes}
On remarque qu'à partir de {\tt Lt} on retrouve facilement les valeurs de 
{\tt L[n]} :
on note :\\
{\tt sum0(L,n)} la somme des valeurs {\tt L[j]} lorsque {\tt j} est pair et
$0\leq j\leq n$ et \\
{\tt sum1(L,n)} la somme des valeurs {\tt L[j]} lorsque {\tt j} est impair et
$0\leq j\leq n$ et \\
{\tt sumt(L,n)} la somme des valeurs {\tt L[j]} lorsque $0\leq j\leq n$.\\
Si on a : {\tt sum(Lt[k],m)<n<sum(Lt[k],m+1)}\\
alors la valeur de {\tt L[n]} sera \'egale \`a {\tt V0+sum1(Lt[k],m)}.\\
{\tt V0:=8;Lt:=[0,4,1,2,1,1,2,1,4]}\\
\begin{verbatim}
sum0(L,n):={
local k,S,S0;
  S0:=NULL;
  S:=0;
 pour k de 0 jusque n pas 2 faire
   S:=S+L[k];
   S0:=S0,S;
 fpour;
 return S0;
 }:;
\end{verbatim}
\begin{verbatim}
//Lt[1]+Lt[3]+...Lt[2j+1] avec 2j+1<=n<2j+2=k
sum1(L,n):={
local k,S,S1,s;
s:=size(L)-1;
si n>s alors return "erreur" fsi;
S1:=0,0;
  S:=0;
 pour k de 2 jusque s-2 pas 2 faire
   S:=S+L[k];
   S1:=S1,S,S;
 fpour;
 return [S1,S+L[s]];
 }:;
\end{verbatim}
\begin{verbatim}
sumt(L,n):={
local k,S,St;
si n>size(L)-1 alors return "erreur" fsi;
St:=NULL;
  S:=0;
 pour k de 0 jusque n  faire
   S:=S+L[k];
   St:=St,S;
 fpour;
 return [St];
 }:;
\end{verbatim}
On \'ecrit le programme {\tt Val(Lt,n,V0} qui renvoie {\tt V0+Lt[n]}.\\
{\tt Lt} repr\'esente la liste  qui est 
la valeur  
{\tt V0+Lt[n]}
\begin{verbatim}
Val(Lt,n,V0):={
  local k,s,S1,St;
  si n>sum(Lt) alors return "erreur" fsi;
  s:=size(Lt)-1;
  St:=sumt(Lt,s);
  S1:=sum1(Lt,s);  
  k:=1; 
  tantque n>St[k] and k<=s faire
     k:=k+1;
  ftantque;
 //afficher(k,St[k-1],n,St[k]); 
 //St[k-1]<n<=St[k]
  si est_pair(k) alors return V0+St[k-1]-S1[k-1] ;fsi;
 return  V0+n-S1[k-1];
 }:; 
\end{verbatim}
Si V0
Les valeurs de {\tt Lt[n1]..Lt[n2]} lorsque {\tt Lt[0]=0} et
{\tt Lt[1]..Lt[n]} est la liste transformée de {\tt L=[V0,V1...Vn]}
\begin{verbatim}
Valeur(Lt,n1,n2,V0):={
  local j,k,s,S1,St,L;
  si n2<n1 ou n2>sum(Lt) alors return "erreur" fsi;
  s:=size(Lt)-1;
  St:=sumt(Lt,s);
  S1:=sum1(Lt,s);  
  L:=V0;
  k:=1; 
  pour j de n1 jusque n2 faire
   tantque j>St[k] and k<=s faire
     k:=k+1;
   ftantque;
   si est_pair(k) alors 
       L:=L,V0+St[k-1]-S1[k-1];
       sinon
       L:=L,V0+j-S1[k-1];
   fsi;
  fpour; 
  return  L;
}:;   
\end{verbatim}

On tape :\\
{\tt Lt:=[1,0,3,1,2,1,1,2,1,3,01];}\\
{\tt Valeur(Lt,16,32,8}\
On obtient :\\
{\tt Valeur(Lt,n1,n2,V0}\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
\begin{verbatim}

\end{verbatim}
\begin{verbatim}

\end{verbatim}


On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
On tape :\\
{\tt }\\
On obtient :\\
{\tt }\\
\section{Les d\'efinitions}
\subsection{D\'efinition de {\tt Lc(n,m)}}
On a vu pr\'ec\'edemment que la suite des batracions entre $2^9$ et $2^{10}$ 
pouvait se traduire par :
\begin{verbatim}
 1,0,8,1, (i.e. 9,1)
     7,1,6,1,5,1,4,1,3,1,2,1,1,2,
         6,1,5,1,4,1,3,1,2,1,1,2,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2, 
                         2,1,1,2,1,3,
             5,1,4,1,3,1,2,1,1,2,
                 4,1,3,1,2,1,1,2,
                     3,1,2,1,1,2,
                         2,1,1,2,1,3,
             4,1,3,1,2,1,1,2,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                 3,1,2,1,1,2,
                     2,1,1,2,1,3,
                     2,1,1,2,1,3,1,4,
\end{verbatim}
suivi par sa suite sym\'etrique :
\begin{verbatim}
4,1,3,1,2,1,1,2,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5, 
    3,1,2,1,1,2,
        2,1,1,2,1,3,
        2,1,1,2,1,3,1,4,
        2,1,1,2,1,3,1,4,1,5,
        2,1,1,2,1,3,1,4,1,5,1,6,
        2,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,0,1
\end{verbatim}
que l'on va traduire avec les d\'efinitions qui vont suivre par :\\
{\tt Lc(9,0),Lc(8,1),Lc(7,2),Lc(6,3),Lc(5,4),Lc(4,5),Lc(3,6),Lc(2,4),Lc(1,8),Lc(0,9)}
{\bf Remarque} Lorsque $p=9$, la somme des param\`etres vaut de {\tt Lc} vaut 9\\

{\bf Les d\'efinitions des suites} {\tt Lc(n;k)} :
\begin{itemize}
\item {\tt Lc(n,0)=(1,0)}
\item {\tt Lc(n,1)=(n,1)}
On a alors :\\
{\tt Lc(n,1)=Lc(n,0),Lc((n-1),1)}
\item {\tt Lc(n,2)} une s\'equence courante par :\\
{\tt Lc(n,2):=n,1,(n-1),1,....3,1,2,1,1,2;}\\
ou encore \\
{\tt Lc(n,2):=Lc(n,1),Lc((n-1),1),....Lc(3,1),Lc(2,1),1,2;}\\
On a alors :\\
{\tt Lc(2,2)} est \'egale \`a {\tt 2,1,1,2} et\\
{\tt Lc(3,2)} est \'egale \`a {\tt 3,1,2,1,1,2}
\item {\tt Lc(n,3)} un bloc de s\'equences courantes par ;\\
{\tt Lc(n,3):=Lc(n,2),Lc(n-1,2),....Lc(3,2),Lc(2,2),1,3;}\\
On a alors :\\
{\tt Lc(2,3)} est \'egale \`a {\tt 2,1,1,2,1,3} et\\
{\tt Lc(3,3)} est \'egale \`a {\tt Lc(3,2),Lc(2,3)= 3,1,2,1,1,2,2,1,1,2,1,3}
\item {\tt Lc(n,4)} une suite de  bloc de s\'equences courantes par ;\\
{\tt Lc(n,4):=Lc(n,3),Lc(n-1,3),....Lc(3,3),Lc(2,3),1,4;}\\
On a alors :\\
{\tt Lc(2,4)} est \'egale \`a {\tt 2,1,1,2,1,3,1,4} et\\
{\tt Lc(3,4)}={\tt 3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4}
\item ......
\item {\tt Lc(n,k):=Lc(n,k-1),Lc(n-1,k-1),....Lc(3,k-1),Lc(2,k-1),1,k;}\\
On a alors :\\
{\tt Lc(2,k)} est \'egale \`a {\tt 2,1,1,2,1,3,1,4...1,k}\\
{\tt Lc(3,k)} est \'egale \`a :
\begin{verbatim}
(3,1,2,1,1,2,
     2,1,1,2,1,3,
     2,1,1,2,1,3,1,4
    .....
     2,1,1,2,1,3,1,4...1,k-1,
     2,1,1,2,1,3,1,4...1,k-1,1,k)
\end{verbatim}
\end{itemize}
\subsection{Le programme {\tt Lc(n,m)}}
\begin{verbatim}
Lc(n,m):={
  local k,L,Lf;
  L:=NULL; Lf:=NULL;
  si m>n alors return revlist(Lc(m,n)); fsi;
  si m==0 alors return (1,0) fsi;
  si m==1 alors return (n,1) fsi;
  pour k de n jusque 2 pas -1 faire 
    L:=L,Lc(k,m-1);
  fpour;
  L:=L,1,m;
  return L;
  }:;
\end{verbatim}
\section{Les calculs de la somme de la liste Lc(n,k)}
On veut connaitre :\\
\begin{itemize}
\item la dur\'ee du parcours d\'ecrit par la liste {\tt Lc(m,k)} 
i.e. de combien augmente l'indice quand on ex\'ecute {\tt Lc(m,k)}, 
\item de combien augmente la valeur {\tt b(n)} quand on ex\'ecute {\tt Lc(m,k)}.
\end{itemize}
Si avant l'ex\'ecution de {\tt Lc(m,k)} l'indice vaut {\tt nd} et si  apr\`es 
l'ex\'ecution de {\tt Lc(m,k)} l'indice vaut {\tt na} on a la relation :\\
{\tt na=nd+sum(Lc(m,k))}.\\
Si avant l'ex\'ecution de {\tt Lc(m,k)} la valeur {\tt b(n)} vaut {\tt vd} et 
si apr\`es l'ex\'ecution de {\tt Lc(m,k)} la valeur {\tt b(n)} vaut {\tt va} on 
a la relation :\\
{\tt va=vd+sum2(Lc(m,k))} ou {\tt sum2} est la somme des indices pairs de 
{\tt Lc(m,k)}.
\subsection{Somme de Lc(n,k)}
On a :\begin{itemize}
\item pour $k=1$ {\tt sum(Lc(n,1))=(n+1)=comb(n+1,1)}, 
\item pour $k=2$ on a :\\
{\tt sum(Lc(n,2))=(n+1)+n+(n-1)+..3+2+1=(n+2)*(n+1)/2=comb(n+2,2)},
\item pour $k=3$ on a:\\
{\tt sum(Lc(n,3))=sum(comb(j+2,2),j=O..n)=(1+n)*(2+n)*(3+n)/6=comb(n+3,3)} 
\item pour $k=4$ on a:\\
{\tt sum(Lc(n,4))=sum(comb(j+3,3),j=0..n)=(1+n)*(2+n)*(3+n)*(4+n)/24=comb(n+4,4)} 
\item par r\'ecurrence on montre que :\\
{\tt sum(Lc(n,k))=sum(comb(j+k,k),j=0..n)=comb(n+k,k)}
\end{itemize}
\subsection{Somme des indices pairs de de Lc(n,k) si n>=k}
\begin{itemize}
\item pour $k=1$ {\tt sum2(Lc(n,1))=n=comb(n,1)},
\item pour $k=2$ on a :\\
{\tt sum2(Lc(n,2))=n+(n-1)+..3+2+1=(n+1)*n/2=comb(n+1,2)},
\item pour $k=3$ on a:\\
{\tt sum2(Lc(n,3))=sum(comb(j+1,2),j=O..n)=n*(1+n)*(2+n)/6=comb(n+2,3)} 
\item par r\'ecurrence on montre que :\\
{\tt sum2(Lc(n,k))=sum(comb(j+k-1,k),j=0..n)=comb(n+k-1,k)}
\end{itemize}
\subsection{Somme des indices pairs de de Lc(n,k) si n<=k}
\begin{itemize}
\item pour $k=1$ {\tt sum2(Lc(n,1))=n=comb(n,1)},
\item pour $k=2$ on a :\\
{\tt sum2(Lc(n,2))=n+(n-1)+..3+2+1=(n+1)*n/2=comb(n+1,2)},
\item pour $k=3$ on a:\\
{\tt sum2(Lc(n,3))=sum(comb(j+1,2),j=O..n)=n*(1+n)*(2+n)/6=comb(n+2,3)} 
\item par r\'ecurrence on montre que :\\
{\tt sum2(Lc(n,k))=sum(comb(j+k-1,k),j=0..n)=comb(n+k-1,k)}
\end{itemize}
\section{Coordonn\`ees des milieux de l'intervalle $[2^p,2^{p+1}]$}
Prenons comme exemple {\tt p=13} puis {\tt p=14}.
Puisque {\tt comb(13,k)=comb(13,13-k)}, on a d'apr\`es la formule du bin\^ome :\\
$(1+1)^{13}=sum(comb(13,k),k=0..13)=2*sum(comb(13,k),k=0..6)$
Donc $2^{12}=sum(comb(13,k),k=0..6)$
Puisque {\tt comb(14,7)=2*comb(13,6)}, on a d'apr\`es la formule du bin\^ome :\\
$(1+1)^{14}=sum(comb(14,k),k=0..14)=2*(sum(comb(14,k),k=0..6)+comb(13,6))$
Donc $2^{13}=sum(comb(14,k),k=0..6)+comb(13,6)$
Si {\tt p=13}\\
{\tt B13=(Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6),\\
Lc(6,17),Lc(5,8),Lc(4,9),Lc(3,10),Lc(2,11),Lc(1,12),Lc(0,13))}\\
l'indice du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)=2\verb|^|13+(2\verb|^|13)/2=3*2\verb|^|12}\\
c'est aussi le milieu de l'intervalle $[2^{13},2^{14}]$ i.e. $3*2^{12}$\\
la valeur du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)=2\verb|^|12+
sum(comb(12,k),k=0..5)+comb(12,6)=2\verb|^|12+
sum(comb(12,k),k=0..5)+comb(11,6)+comb(11,5)}\\
c'est bien {\tt 3*2\verb|^|11+comb(11,5)}
Si {\tt p=14} \\
{\tt B14=(Lc(14,0),Lc(13,1),Lc(12,2),Lc(11,3),Lc(10,4),Lc(9,5),Lc(8,6),Lc(7,6)\\
Lc(6,7),Lc(6,8),Lc(5,9),Lc(4,10),Lc(3,11),Lc(2,12),Lc(1,13),Lc(0,14))}\\
l'indice du milieu de B14 est \'egal \`a :\\
{\tt 2\verb|^|14+sum(comb(14,k),k=0..6)+comb(13,6),3*2\verb|^|13}\\
c'est bien le milieu de l'intervalle $[2^{14},2^{15}]$ i.e. $3*2^{13}$\\
la valeur du milieu de B14 est \'egal \`a :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)+comb(12,6)}\\
c'est aussi  {\tt 3*2\verb|^|12+comb(12,6)}\\
On tape :\\
\begin{verbatim}
xymilieu(p):={
  local x,y;
  y:=3*2^(p-2);
  x:=3*2^(p-1);
  si est_pair(p) alors 
    y:=y+comb(p-2,(p-2)/2);
  sinon
    y:=y+comb(p-2,(p-3)/2); 
     fsi;
  retourne [x,y,y/x];
  }:;
pentevn0(p):={
  local v,n,j,vd,nd,p0,p1,p2;
  vd:=2^(p-1);
  nd:=2*vd;
  p0:=1/2;p1:=1/2;
  p2:=(vd+p-1)/(nd+p);
  j:=1;
  tantque p2>p1 faire 
    j:=j+1;
    p0:=p1;p1:=p2;
    p2:=(vd+comb(p,j))/(nd+comb(p+1,j));
  ftantque;
  return [j-1,p1,p0,p2];
 }:;
pentevn(p):={
  local v,n,j,vd,nd,d0,d1,d2,,f0,f1,f2,p0,p1,p2;
  vd:=2^(p-1);
  nd:=2*vd;
  p0:=1/2;p1:=1/2;
  p2:=(vd+p-1)/(nd+p);
  j:=1;
  tantque p2>p1 faire 
    j:=j+1;
    p0:=p1;p1:=p2;
    p2:=(vd+comb(p,j))/(nd+comb(p+1,j));
  ftantque;
  f0:=p-d0;f1:=p-d1;f2:=p-d2;
  return [j-1,d1,f1,d0,f0,d2,f2];
 }:;
Lcmax0(v0,n0,d,f):={
  local v1,n1,j,vd,nd,p0,p1,p2;
  vd:=v0;v1:=v0+comb(d+f-2,f-1);
  nd:=n0;n1:=n0+comb(d+f-1,f-1);
  p0:=v0/n0;p1:=v1/n1;
  j:=1;f:=f-1;
  tantque d>3 et p1>p0 faire 
    j:=j+1;d:=d-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v0+comb(d+f-2,f);
    n1:=n0+comb(d+f-1,f);
    p1:=v1/n1;
  ftantque;
  si d==2 alors f:=f+1;fsi;
  return [d,f,j-1,p1,p0];
 }:;

\end{verbatim}
%cf gremaxmil.xws gremaxecart.xws
\section{Coordonn\'ees du maximum de u(n)/n pour $n\in[2^p...2^{p+1}]$}
Prenons comme exemple {\tt p=13} puis {\tt p=14}.
Si {\tt p=13} 
{\tt B13=(Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6),\\
Lc(6,17),Lc(5,8),Lc(4,9),Lc(3,10),Lc(2,11),Lc(1,12),Lc(0,1))}\\
l'indice du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)}\\
c'est aussi le milieu de l'intervalle $[2^{13},2^{14}]$ i.e. $3*2^{12}$\\
la valeur du milieu de B13 est \'egal \`a :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)}\\
c'est aussi  {\tt 3*2\verb|^|11+comb(11,5)}
\begin{verbatim}
Lcmax(p):={
  local v0,n0,mp,v1,n1,vd,nd,p0,p1,p2,d,f;
  si est_impair(p) alors v0:=3*2^(p-2)+comb(p-2,(p-3)/2);n0:=3*2^(p-1);
  d:=(p+1)/2;f:=(p-1)/2; fsi;
   v1:=v0-comb(p-1,f);n1:=n0-comb(p,f)
   p0:=v0/n0;p1:=v1/n1;
   tantque f>3 et p1>p0 faire 
    f:=f-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v0-comb(p,f);
    n1:=n0-comb(p-1,f);
    p1:=v1/n1;
  ftantque;
 return [p-f,f,p0];
 fsi
 si est_pair(p) alors v0:=3*2^(p-2)+comb(p-2,(p-3)/2);n0:=3*2^(p-1);
  d:=(p+1)/2;f:=(p-1)/2; 
  v1:=v0-comb(p-1,f);n1:=n0-comb(p,f)
   p0:=v0/n0;p1:=v1/n1;
   tantque f>3 et p1>p0 faire 
    f:=f-1;
    p0:=p1;v0:=v1;n0:=n1;
    v1:=v0-comb(p,f);
    n1:=n0-comb(p-1,f);
    p1:=v1/n1;
  ftantque;
return [p-f,f,p0];
fsi;
}:;
\end{verbatim}
On a :
\begin{verbatim}
nM(p):=nm(p)-comb(,);
bM(p):=bm(p)-comb(,);
\end{verbatim}
On tape :\\
{\tt nM(14),bM(14)}\\
On obtient :\\
{\tt 24576,13212}\\
On tape :\\
{\tt nM(15),bm(15)}\\
On obtient :\\
{\tt 49152,26292}\\
On v\'erifie, on tape :\\
{\tt b(89516),b(48074)}\\
On obtient :\\
{\tt 13212,26292}\\
On tape :\\
{\tt nm(14),bm(14)}\\
On obtient :\\
{\tt }



Pour {p=19} :\\
On tape :\\
\begin{verbatim}

\end{verbatim}
On obtient :\\
{\tt }

\begin{verbatim}

\end{verbatim}
\begin{verbatim}

\end{verbatim}
\begin{verbatim}

\end{verbatim}
\part*{Partie III} 
La partie III consiste \`a rappeler certaines propri\'et\'es des combinaisons.\\
\section{D\'efinition }
On a pour pour $1\leq$ {\tt n} et {\tt p}$\leq$ {\tt n}:\\
{\tt comb(n,p)=}$\displaystyle \frac{n!}{p!(n-p)!}=\frac{n(n-1)...(n-p+1)}{p!}$.\\
On tape :\\
{\tt comb(7,0)}\\
On obtient :\\
{\tt 1}\\
On tape :\\
{\tt comb(7,1)}\\
On obtient :\\
{\tt 7}\\
On tape :\\
{\tt comb(7,2)}\\
On obtient :\\
{\tt 21}\\
On tape :\\
{\tt comb(7,3)}\\
On obtient :\\
{\tt 35}\\
en effet $(7*6*5)/3!=7*5=35$\\
On tape :\\
{\tt comb(7,0)}\\
On obtient :\\
{\tt 1}\\
en effet $(7*6*5)/3!=7*5=35$\\
\section{Propri\'et\'es de base}
On a pour $1\leq $ {\tt n} et {\tt p}$\leq$ {\tt n} :\\
{\tt comb(n,p)}=$\frac{n!}{p!*(n-p)!}=\frac{n*(n-1)*...*(n-p+1)}{p!}$.\\
On a :\\
{\tt comb(n,p)=comb(n,n-p)}\\
{\tt comb(n,p)=n/p*comb(n-1,p-1)}\\
{\tt comb(n,p)=(n-p+1)/p*comb(n,p-1)}\\
 Pour {\tt n>0} on a {\tt comb(n,p)=comb(n-1,p-1)+comb(n-1,p)}\\
 {\tt n} \'etant fix\'e l'application {\tt m-> comb(n,m)} est croissante.
\section{Propri\'et\'es utilisant la formule du bin\^ome}
\begin{itemize}
\item Rappel de la formule du bin\^ome\\
On a pour $n\in \N$ et $x\in \R$ :\\
{\tt Sn=(1+x)\verb|^|n=$\displaystyle\sum_{k=0}^n$ comb(n,k)*x\verb|^|k}
\item En rempla\c{c}ant dans {\tt Sn}, {\tt x} par 1 on obtient :\\
{\tt sum(comb(n,k),k=0..n)=2\verb|^|n}\\
Si $n=2p+1$, {\tt Sn} a alors un nombre pair de termes et puisque 
{\tt comb(n,p)=comb(n,n-p)}, on a :\\
{\tt sum(comb(2p+1,k),k=0..p)=2\verb|^|(2p-1)}\\
Par exemple :\\
{\tt 2\verb|^|13+sum(comb(13,k),k=0..6)=3*2\verb|^|12=12288}\\
Si $n=2p$, {\tt Sn} a alors un nombre impair de termes.  \\
Puisque {\tt comb(n,p)=comb(n,n-p)} et que \\
{\tt comb(2*p,p)=2*comb(2*p-1,p-1)=2*comb(2*p-1,p)} on a :\\
{\tt sum(comb(2*p,k),k=0..p-1)+comb(2*p,p)/2=}\\
{\tt sum(comb(2*p,k),k=0..p-1)+comb(2*p-1,p-1)=2\verb|^|(2p-1)}\\
Par exemple :\\
{\tt 2\verb|^|12+sum(comb(12,k),k=0..6)=3*2\verb|^|11+comb(11,5)=6606}
Cela servira pour trouver l'expression de la suite des milieux des arches  
correspondant au parcours du candidat 4.
\item En rempla\c{c}ant  $x$ par 1 dans {\tt Sn}, on obtient :\\
{\tt a=sum(comb(n,k),k=0..n)=2\verb|^|n} et \\
en rempla\c{c}ant $x$ par -1 dans {\tt Sn}, on obtient :\\
{\tt b=sum((-1)\verb|^|k*comb(n,k),k=0..n)=0}
En calculant {\tt a+b} et {\tt a-b} on en d\'eduit que :\\
{\tt a+b=2+2*comb(n,2)+2*comb(n,4)+2*comb(n,6)....=2\verb|^|n}\\
{\tt a-b= 2*comb(n,1)+2*comb(n,3)+2*comb(n,5)....=2\verb|^|n}\\
On d\'efinit :\\
{\tt S0n=}$\displaystyle \sum_{k=0}^{p}{\tt comb(n,2k+1)}$ si $n=2p$ et\\
{\tt S0n=}$\displaystyle \sum_{k=0}^{p-1}{\tt comb(n,2k+1)}$ si $n=2p+1$ \\
{\tt S1n=}$\displaystyle \sum_{k=0}^{p}{\tt comb(n,2k-1)}$ si $n=2p$ et\\
{\tt S1n=}$\displaystyle \sum_{k=0}^{p-1}{\tt comb(n,2k)}$ si $n=2p+1$ \\
On a alors : $S0n=S1n=2^{n-1}$\\
Par exemple :\\
{\tt sum(comb(8,2*k),k=0..4)=sum(comb(8,2*k-1),k=0..4)=128=2\verb|^|7}\\
{\tt sum(comb(9,2*k),k=0..4)=1+sum(comb(9,2*k-1),k=0..4)=256=2\verb|^|8}\\
{\tt sum(comb(16,2*k),k=0..8)=sum(comb(16,2*k-1),k=0..8)=32768=2\verb|^|7}\\
{\tt sum(comb(17,2*k),k=0..8)=1+sum(comb(17,2*k-1),k=0..8)=65536=2\verb|^|8}\\
\item On montre par r\'ecurrence que :\\
{\tt comb(p,p)+comb(p+1,p)+...+comb(p+(n-p),p)=comb(n+1,p+1)=comb(n-p,p+1)}
{\tt comb(p,0)+comb(p+1,1)+...+comb(p+(n-p),n-p)=comb(n+1,p+1)}
Par exemple :\\
{\tt comb(5,0)+comb(6,1)+comb(7,2)+comb(8,3)=comb(9,6)}\\
car on a ici {\tt p=5} et {\tt n=8}
{\tt comb(7,0)+comb(8,1)+comb(9,2)+comb(10,3)+comb(11,4)=comb(12,8)}\\
car on a ici {\tt p=7} et {\tt n=11}
\end{itemize}

2. Pourquoi la suite {\tt b(n)} est-elle définie ?
Pour cela, montrons par r\'ecurrence que pour tout {\tt n>=1} on a {\tt 1<=b(n)<=n}.\\
On a \\
{\tt 1<=b(2)=1<=2}\\{\tt 1<=b(3)=2<=3}\\
Soit {\tt P(n)} la propri'et\'e {\tt 1<=b(n)<=n}
Supposons que pour tout {\tt k<=n} {\tt P(k)} soit vraie i.e. que l'on a :\\
{\tt 1<=b(k)<=k}\\
Est ce que cela entraine que {\tt P(n+1)} est vraie ?
Soit {\tt k=b(n)} puisque {\tt P(n)} est vraie 
qu'alors pour tout {\tt 1<=k<=n} on a {\tt 1<=b(k)<=k}.\\Il faut donc montrer que {\tt 1<=b(n)<=n}.\\Posons {\tt p=b(n-1)}, on a :\\{\tt 1<=p=b(n-1)<=n-1} et aussi \\{\tt n-(n-1)=1<=n-b(n-1)=n-p<=n-1} donc \\ d'apr\`es l'hypoth\`ese de r\'ecurrence si {\tt 1<=p<=n-1} alors on a :\\{\tt 1<=b(p)=b(b(n-1))<=p-1} et aussi si {\tt 1<=n-p<=n-1} alors on a :\\{\tt n-(n-1)=1<=b(n-p)=b(n-b(n-1))<=n-p<=n-1} \\cela entraine que :\\{\tt b(n)=b(p)+b(n-p)} est d\'efinie et on a :\\{\tt 1<=2<=b(n)=b(b(n-1))+b(n-b(n-1))=b(p)+b(n-p)<=p-1+n-p-1=n-2<=n-1}.\\