Avant-propos

Le point de départ de ce document est de résoudre le "Problème 40" intitulé : Cartes grenouilles et suites fractales du livre "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...
La première partie est constituée d’exercices de programmation déstinés à des élèves.
Elle est destinée aussi à faciliter la compréhension de la deuxième partie.
La deuxième partie est indépendante et elle consiste à édutier la suite récursive définie par :
b(1)=b(2)=1 et pour n>2 par b(n)=b(b(n-1))+b(n-b(n-1)).
La troisième partie consiste à rappeler différentes propriétés des combinaisons utilisées dans la deuxième partie.
Notations utilisées en deuxième partie
On notera :

• B la liste constituée par b(n), pour n ∈ ℕ,
• GB est le graphe des segments reliant les points de coordonnées n,b(n), pour n ∈ ℕ,
• B(p) la liste :
  [b(2^p+k)$(k=0..2^p)]=[b(2^p+1)....b(2^(p+1))], pour p∈ ℕ,
• pour p∈ ℕ :
  xm_p=3*2^(p-1) qui est l’indice du milieu de B(p),
  ym_p)=b(3*2^(p-1))=b(xm_p),
  pm_p)=ym_p)/ xm_p)=b(3*2^(p-1))/(3*2^(p-1)) qui est la pente du graphe GB au point milieu de B(p).
  La suite pm_k sera appelée la suite "pentemilieu".
  On étudiera la suite des pentes des milieux pm_k) pour k∈ ℕ et on montrera que cette suite tend vers 1/2 quand p tend vers +∞,
• pour p∈ ℕ:
  pM_p:=max([(b(n)/n)$(n=2^p..2^(p+1))])
  pM_p sera appellée la suite "pentemaximum".
  On édutiera aussi la suite des pentes des maximums pM_k) pour k∈ ℕet on montrera que cette suite tend aussi vers 1/2 quand p tend vers +∞.

On suppose ici que :

• la distance entre 2 nénuphars est de 1 unité de longueur,
• un saut de crapaud met 1 unité de temps,
• 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 à la suite.

1  Les consignes du concours de sauts

Un concours d’endurance de sauts est organisé. Pour cela, les crapauds doivent observer les consignes suivantes :

• au départ i.e. au temps 0, le crapaud doit faire un saut puis il doit faire une pause, (après cela le temps vaut 2 unités de temps),
• ensuite, pour tout entier p≥ 1, durant le lapps de temps allant de 2^p à 2^p+1, le crapaud doit faire 2^p−1 sauts : il doit donc durant cette période sauter 2^p−1 fois et se reposer pendant 2^p−1 fois.
• faire un saut au temps 2^p pour tout p≥ 1,
• se reposer durant la période allant de 2^p+1−1 à 2^p+1 pour tout p≥ 1,
• 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épondant aux consignes seront sélectionnés.

1.1  Les explications données par les 4 candidats sélectionnés

• Le candidat 1 dit : "je fais un saut puis je me repose 1 fois etc...",
• Le candidat 2 dit : "je saute durant tout le temps imposé puis, je me repose le reste du temps" i.e. "pour tout p≥ 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",
• Le candidat 3 dit : "pour tout p≥ 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",
• 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éplacement débute 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 à vous de vérifier que cette formule définit un parcours qui respecte bien les consignes.

Le jury vérifie facilement que les consignes des 3 premiers candidats sont respectées. Pour le candidat 4, le jury, ne comptant aucun mathématicien, est perplexe aussi, il se contente de tester le début du parcours en calculant les premiers termes de la suite b(n), puis il sélectionne le candidat 4.
On invite le jury à lire la 2ième partie pour comprendre l’évolution du parcours du candidat 4 ; cette 2ième partie est l’étude de la suite définie par :
b(0)=0, b(1)=b(2)=1, b(n)=b(b(n−1))+b(n−b(n−1)) pour n>2
Remarque
La valeur b(0)=0 n’est pas utile pour la définition de la suite b(n).
On pourra se référer à la partie II pour avoir la démonstration qui montre que la suite b(n) est bien définie.

1.2  Les parcours de ces 4 candidats pour n=0..16

L’entier n désigne le temps écoulé depuis le départ et
U1(n) (resp U2(n),U3(n),U4(n)=b(n)) désigne la position du candidat 1 (resp 2,3,4) en fonction du temps n.
Exercice
Donner le début du parcours des quatre candidats durant le lapps de temps 0,16 (ou 0..32 pour les courageux)
Correction
Voici le début du parcours durant le lapps de temps 0,16 des quatre premiers candidats

On remarquera que pour n entre 0 et 5 le parcours est imposé par les consignes mais ensuite il n’est pas le même pour tout le monde.

2  Exercices

2.1  Exercice 1

Écrire les programmes qui donne la liste des positions U₁(n) (resp U₂(n),U₃(n),U₄(n)) du candidat 1 (resp 2,3,4) en fonction du temps n. Il faudra se référer à la Partie II pour vérifier que le candidat 4 respecte bien toutes les consignes.

2.2  Correction de l’exercice 1

• La position U₁(n) du parcours du candidat 1 est :
  U₁(0)=0, U₁(2n−1)=n,U₁(2n)=n pour n>=1
  On tape :
  eval([0,(k,k)$(k=1..8)])
  On obtient :
  [0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8]
  On tape le programme LU1(p) qui donne la suite des valeurs de U1(n) pour n allant de 0 jusque 2^p :

   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);
    }:;
  

  On tape :
  LU1(4)
  On obtient les 16+1 premiers termes de LU1 :
  (0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8)
  On tape :
  LU1(5)
  On obtient 32+1 premiers termes de LU1 :
  (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)
• 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 L2U(n) qui donne la suite des valeurs de U2(n) pour n allant de 0 jusque 2^p :

  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);
    }:;
  

  On tape :
  LU2(4)
  On obtient les 16+1 premiers termes de LU2 :
  (0,1,1,2,2,3,4,4,4,5,6,7,8,8,8,8,8)
  On tape :
  LU2(5)
  On obtient 32+1 premiers termes de LU2 :
  (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)
• 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 :
  (2^2+k)$(k=0..3),(2^2+3)$(k=4..5),2^3,2^3$(k=7..8)
  On obtient :
  (4,5,6,7,7,7,8,8,8)
  On tape le programme LU3(n) qui donne la liste des valeurs de U3(n) pour n allant de 0 jusque 2^p :

  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);
    }:;
  

  On tape :
  LU3(4)
  On obtient 16+1 premiers termes de L3 :
  (0,1,1,2,2,3,3,4,4,5,6,7,7,7,8,8,8)
  On tape :
  LU3(5)
  On obtient les 32 premiers termes de 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)
• On calcule les valeurs de la suite U4(n)=b(n).
  On a :
  b(1)=1
  b(2)=1
  b(3)=b(b(2))+b(3-b(2))=b(1)+b(2)=2
  b(4)=b(b(3))+b(4-b(3))=b(2)+b(2)=2
  b(5)=b(b(4))+b(5-b(4))=b(2)+b(1)=3
  b(6)=b(b(5))+b(6-b(5))=b(3)+b(3)=4
  b(7)=b(b(6))+b(7-b(6))=b(4)+b(3)=4
  b(8)=b(b(7))+b(8-b(7))=b(4)+b(4)=4
  b(9)=b(b(8))+b(9-b(8))=b(4)+b(5)=5
  b(10)=b(b(9))+b(10-b(9))=b(5)+b(5)=6
  b(11)=b(b(10))+b(11-b(10))=b(6)+b(5)=7
  b(12)=b(b(11))+b(12-b(11))=b(7)+b(5)=7
  b(13)=b(b(12))+b(13-b(12))=b(7)+b(7)=8
  b(14)=b(b(13))+b(14-b(13))=b(8)+b(6)=8
  b(15)=b(b(14))+b(15-b(14))=b(8)+b(7)=8
  b(16)=b(b(15))+b(16-b(15))=b(8)+b(8)=8
  On remarque que la définition de cette suite est récursive.
  Mais le programme donnant la liste LU4(p) sera itératif pour que son éxécution soit plus rapide.
  On tape :

  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);
    }:;
  

  On remarquera que l’on a mis L.append(uk) au lieu de L:=append(L,uk) car l’éxécution de L.append(uk) est plus rapide puisqu’elle évite la recopie de L.
  On tape :
  LU4(4)
  On obtient les 16+1 premiers termes de L4 :
  (0,1,1,2,2,3,4,4,4,5,6,7,7,8,8,8,8)
  On tape :
  LU4(5)
  On obtient les 32+1 premiers terme de 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)

2.3  Exercice 2

• Énoncé :
  Utiliser les programmes précédents pour avoir les valeurs des suites LU1(n), (resp LU2(n), LU3(n), LU4(n)) pour 2^p≤ n ≤ 2^p+1+1.
• Correction :
  On définit la fonction L1(p) qui renvoie LU1(n) pour n∈ [2^p, 2^p+1+1] :

   L1(p):={
    local L,k;
    L:=LU1(p+1);
    return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
    }:;
  

  On définit la fonction L2(p) qui renvoie LU2(n) pour n∈ [2^p, 2^p+1+1] :

   L2(p):={
    local L,k;
    L:=LU2(p+1);
    return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
    }:;
  

  On définit la fonction L3(p) qui renvoie LU3(n) pour n∈ [2^p, 2^p+1+1] :

  L3(p):={
    local L,k;
    L:=LU3(p+1);
    return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;;
    }:;
  

  On définit la fonction L4(p) qui renvoie LU4(n) pour n∈ [2^p, 2^p+1+1] :

  L4(p):={
   local Lk;
    L:=LU4(p+1);
    return eval(L[k]$(k=2^p..2^(p+1))),2^p+1;
    }:;
  

2.4  Exercice 3

• Énoncé :
  Utiliser les programmes précédents pour tracer les arches graphiques AG1(p) (resp AG2(p), AG3(p), AG(p)) repprésentant LU1(n)/n (resp LU2(n)/n, LU3(n)/n, LU4(n)/n) pour 2≤ n ≤ 2^p.
  Faire sur un même graphe AG1(p),(resp AG2(p), AG3(p), AG(p)), pour p=1..8
• Correction :
  On tape :

  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;
  }:;
  

  On tape :
  AG1(8)
  On tape :
  AG2(8)
  On tape :
  AG3(8)
  On tape :
  AG4(5)
  ou on rajoute le paramètre L pour représenter LU1 ou LU2 ou LU3 ou LU4 :

  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;
  }:;
  

  On tape :
  AG(LU1(8),8)
  On tape :
  AG(LU2(8),8)
  On tape :
  AG(LU3(8),8)
  On tape :
  AG(LU4(8),8)

2.5  Exercice 4

• Énoncé :
  Écrire un programme qui renvoie le milieu de la suite :
  (LU1(p)[k]/k)$(k=2^(n-1)..2^n) pour n=2..p.
  c’est a dire la suite :
  LU1(p)[3*2^k]/(3*2^k) pour k=0..(p-2).
  Utiliser les programmes précédents pour tracer la ligne polygonale reliant les points milieux des arches précédentes pour LU1 (resp LU2,LU3,LU4)
  Attention
  La suite LU1(p) est la suite des valeurs U1[n] pour n=0..2^p.
  Pour n=2..2^p on a p−1 arches [2¹,2²],[2²,2³]..[2^p−1,2^p].
  La suite des milieux des arches de LU1(p) est donc de longueur p-1.
  Il y a donc p-2 segments reliant ces points.
• Correction :
  On tape :

  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];
    }:;
  

  Ou bien on tape :

  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;
  }:;
  

  Ou bien on tape :

  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;
  }:;
  

  On tape pour avoir l’affichage des milieux en rouge :
  L:=LU4(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1)
  Ou on tape :
  AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)
  Ou on tape :
  AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)
  Ou bien on tape plus simplement :
  affichage(plotlist([[L[3*2^j]/(3*2^k),3*2^k]$(j=0..12)]),1)
  On tape :
  AG(LU1(8),8),affichage(Gmil(LU1(8),8),1)
  AG(LU2(8),8),affichage(Gmil(LU2(8),8),1)
  AG(LU3(8),8),affichage(Gmil(LU3(8),8),1)
  AG(LU4(8),8),affichage(Gmil(LU4(8),8),1)

)

2.6  Exercice 5

• Énoncé :
  Écrire un programme qui renvoie les coordonées du maximum de l’arche 2^k−1..2^k, i.e. les coordonées de :
  max(LU1(p)[n]/n$(n=2^k-1..2^k)).
  Puis, utiliser les programmes précédents pour tracer la suite des maximum des arches précédentes pour LU1(p) (resp LU2(p), LU3(p), LU4(p))
  Attention
  La suite LU1(p) est la suite des valeurs U1[n] pour n=0..2^p Pour n=2..2^p on a p−1 arches ([2¹,2²],[2²,2³]..[2^p−1,2^p]).
  La suite des maximum des arches pour LU1(p) est donc de longueur p-1.
  ) Il y a donc p-2 segments reliant ces points.
• Correction :
  On tape :

  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];
    }:;
  

  On tape :
  MaxL(LU1(8),j)$(j=2..8)
  MaxL(LU2(8),j)$(j=2..8)
  MaxL(LU3(8),j)$(j=2..8)
  MaxL(LU4(8),j)$(j=2..8)
  

Les graphes
On tape :
L:=LU1(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
L:=LU2(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
L:=LU3(12):;AG(L,12),affichage(plotlist([milieuL(L,10)]),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
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 :
L:=LU1(12):;AG(L,12),affichage(Gmil(L,12),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
L:=LU2(12):;AG(L,12),affichage(Gmil(L,12),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
L:=LU3(12):;AG(L,12),affichage(Gmil(L,12),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)
L:=LU4(12):;AG(L,12),affichage(Gmil(L,12),1),
affichage(plotlist([Max(L,j)$(j=2..12)]),2)

2.7  Exercice 6

• Énoncé :
  Trouver l’expression de :
  milieuL(L,n) en fonction de n>0 pour L=L1(n) (resp L2(n), L3(n))
  Trouver l’expression de :
  MaxL(L,n) en fonction de n pour L=L1(n) (resp L2(n), L3(n)).
• Correction :
  On a :
  pour L=L1(n)
  pour n=1 milieuL(L1(1),1)=[3,2/3]
  pour n>1milieuL(L1(n),1)=[3*2^(n-1),1/2]
  pour L=L2(n)
  pour n>=1 milieuL(L1(n),1)=[3*2^(n-1),2/3]
  pour L=L3(n)
  pour n=1 milieuL(L1(1),1)=[3,2/3]
  pour n>=2milieuL(L1(n),1)=[3*2^(n-1),(2^n-1)/3*2^(n-1)]
  On vérifie pour LU3(10), pour cela on tape :
  L:=LU3(8):;milieuL(L,6)
  On obtient :
  [[3,2/3],[6,1/2],[12,7/12],[24,5/8],[48,31/48],
  [96,21/32],[192,127/192]]
  On tape :
  [(3*2^(n-1),(2^n-1)/3*2^(n-1))]$(n=2..7)
  On obtient :
  [[6,1/2],[12,7/12],[24,5/8],[48,31/48],[96,21/32],
  [192,127/192]]

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.

3  Autre reprśentation des parcours

Sur chaque intervalle [2^p+1,2^p+1], on décide de représenter les différents parcours L1(p) (resp L2(p),L3(p),L4(p)) par la suite :
T1(p) (resp T2(p),T3(p),T4(p))
Pour T1(p) on commence par T1(p)[0] qui est la valeur de U1(2^p), puis on note successivement le nombre de sauts et le nombre de pauses du candidat 1 (resp 2,3,4).
Par exemple :

• pour p=3, U3 est représenté pour n=2³..2⁴+1 par la suite :
  (4,5,6,7,7,8,8,8,8,9), mais on peut aussi la représenter :
  pour n=2³+1..12⁴ par la suite T3(3)=(4,3,2,1,2).
  En effet T3[0] vaut U3(8)=4 qui est la valeur de la distance à partir de laquelle le premier saut est réalisé, 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 être représenté pour n=2⁴..2⁵+1 par la suite :
  T3(4)=(8,7,4,1,4),
• pour p=3, U4 pour n=17=16+1..32 par la liste :
  T4(3)=[4,3,1,1,3],
  pour p=4, U4 pour n=33=12+1..64 par la liste :
  T4(4)=[8,4,1,2,1,1,2,1,4].

Il faut bien voir que :

• lorsqu’on compte le nombre de sauts, on compte le nombre d’intervalles qui sépare 2 valeurs différentes de la distance,
• lorsqu’on compte le nombre de pauses, on compte le nombre d’intervalles qui sépare 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 à 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),
• pour que la représentation sur l’intervalle [n₁,n₂] soit correcte il faut que :
  u(n₁)=u(n₁−1)+1 (i.e. u(n₁) est obtenu après un saut)
  et que u(n₂+1)=u(n₂)+1 (i.e. u(n₂+1) est obtenu après un saut),
  ce qui est le cas sur les intervalles [n₁=2^p+1,n₂=2^p+1] puisque les candidats respectent les consignes.
  Pour reconstituer les valeurs de u(n) avec cette nouvelle représentation il faudra aussi connaître les valeurs de u(n₁−1) et de u(n₂+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.

Voici les différentes suites Lp et Tp selon les candidats pour n=2⁴...2⁵ (p=4):

• le candidat 1 peut représenter son parcours par la suite L1(4) :
  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 T1(4) (qui sera une suite de 1) :
  T1=[8,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
• le candidat 2 peut représenter son parcours par la suite L2(4) :
  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 T2=[8,8,8]
• le candidat 3 peut représenter son parcours par la suite L3(4) :
  L3(4)=(8,9,10,11,12,13,14,15,15,15,15,15,16,16,16,16,16,17)
  par la liste T3=[8,7,4,1,4]
• le candidat 4 peut représenter son parcours par la suite L4(4) :
  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 T4=[8,4,1,2,1,1,2,1,4]
  Pour avoir la liste Tn] se référer à la partie II

3.1  Comment savoir où se trouve le crapaud au temps n ?

À l’instant n (n∈ ℕ), pour chacune des représentations, on veut savoir à quelle distance d du départ 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ésentation L(p) si 0≤ n ≤ 2^p+1, la distance d est égale à L(p)[n]
Pour n=12, on a puisque 2³<12<16=2⁴ :
Pour le candidat 1, on tape :
:
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 (6,12)
Pour le candidat 2, on tape :
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 (8,16)
Pour le candidat 3, on tape :
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 (7,15)
Pour le candidat 4, on tape :
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 (7,14)
Pour la représentation T :
Si le temps écoulé est égal à l’indice n d’un élément de L alors n est égal à la somme des termes jusqu’à n, i.e. sum([T[k]],k=0..n) et la distance se mesure par la somme des termes impairs jusqu’à n, i.e.sum1([L[k]],k=0..n)
d=L(n).
On définit deux sommes :

• sum0(L) qui renvoie la somme des termes de L d’indices pairs :
• sum1(L) qui renvoie la somme des termes de L d’indices impairs,

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)

On tape :
T1:=[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
[sum(T1[k],k=1..s),sum(T1[12])],[sum1(T1[24]),sum(T1[24])]
On obtient (6,12)
On tape :
T2:=[0,1,1,1,1,2,2,4,4,8,8];
[sum1(T2[12]),sum(T2[12])],[sum1(T2[24]),sum(T2[24])]
On obtient (8,16)
On tape :
T3:=[0,1,1,1,1,1,1,1,1,3,2,1,2,7,1,4,1,4]; [sum1(T3[12]),sum(T3[12])],[sum1(T3[24]),sum(T3[24])]
On obtient (7,15)
On tape :
T4:=[0,1,1,1,1,2,2,3,1,4,5,1,2,1,4];
[sum1(T4[12]),sum(T4[2]12)],[sum(T4[24]),sum(T4[24])]
On obtient (7,14)
On vérifie, pour n=12 ou n=24, on tape :
L1u(12),L1u(24) renvoie 6,12
L2u(12),L2u(24) renvoie 8,16
L3u(12),L3u(24) renvoie 7,15
L4u(12),L4u(24) renvoie 7,14

4  Définition

Les batracions sont des suites fractales ayant une structure auto-similaire quand on les examine à différentes échelles.
Voici un exemple de batracion, c’est la suite b(n) définie par :
b(1)=1
b(2)=1
b(n)=b(b(n-1))+b(n-b(n-1)) pour n>2

5  Pourquoi la suite b(n) est-elle définie ?

Pour que b(n) soit définie il faut et il suffit que la définition de b(n-1) entraine la définition de b(n). Donc, il faut et il suffit de montrer que 1<=b(n-1)<=n-1 puisque 1<=n-b(n-1)<=n-1 est équivalent à 1<=b(n-1)<=n-1.
Donc si b(n-1) est définie et si 1<=b(n-1)<=n-1 alors b(n) est définie.
Montrons par récurrence que pour tout n>=1 on a 1<=b(n)<=n.
Soit P(n) la propri’eté 1<=b(n)<=n.
On a :
1<=b(1)=1<=1
1<=b(2)=1<=2
1<=b(3)=2<=3
Donc les propri’etés P(1),P(2),P(3) sont vraies.
Supposons que pour tout k<=n la propri’eté P(k) est vraie i.e. que l’on a :
1<=b(k)<=k pour tout 1<=k<=n
Est ce que cela entraine que P(n+1) est vraie ?
On a b(n+1)=b(b(n))+b(n+1-b(n))
Puisque P(n) est vraie on a 1<=b(n)<=n
Soit k=b(n) on a 1<=b(k)<=k=b(n)<=n puisque P(k) est vraie.
Puisque 1<=b(b(n))=b(k)<=n, la propri’eté P(b(k))=P(b(b(n))) est vraie donc :

. Posons j=n+1-b(n)
P(n) est vraie i.e. 1<=b(n)<=n donc :
1<=j=n+1-b(n)<=n donc
P(j) est vraie i.e. 1<=b(j)=b(n+1-b(n))<=j=n+1-b(n) donc :

. On a donc montrer que si pour tout 1<=k<=n la propri’eté P(k) est vraie alors on a :
1<=b(b(n))<=b(n) et 1<=b(n+1-b(n))<=n+1-b(n)
ce qui est équivalent à :
1+1<=b(n+1)=b(b(n))+b(n+1-b(n))<=b(n)+n+1-b(n)=n+1

6  Exercice

Énoncé
Montrer par récurrence que pour tout n>=2 on a :
b(n)=b(n-1) ou b(n)=b(n-1)+1.
Correction
Soit Q(n) la propriété :
pour tout n>=2 on a b(n)=b(n-1) ou b(n)=b(n-1)+1.
Ce qui signifie que lorsque n augmente de 1, soit le "crapaud" se repose soit il effectue un saut.
Supposons que pour tout k<=n, la propriété Q(k) est vraie et montrons qu’alors Q(n+1) est vraie.
Par définition on a :
b(n+1)=b(b(n))+b(n+1-b(n))
Q(n) est vraie (hypothèse de récurrence) donc on a :
b(n)=b(n-1) ou bien b(n)=b(n-1)+1
Étudions chacune de ces 2 possibilités :

1. Supposons que b(n)=b(n-1) on a alors :
   b(n+1)=b(b(n))+b(n+1-b(n)) et
   b(n)=b(b(n))+b(n-b(n)) (puisque on a supposé que b(n)=b(n-1)) Comparons b(n-b(n)) et b(n+1-b(n)).
   Soit j=n+1-b(n) On a vu précédemment que pour tout n>=1 on a 1<=b(n)<=n et 1<=j=n+1-b(n)<=n donc Q(j) est vraie c’est à dire b(j-1)=b(j) ou b(j-1)+1=b(j) donc
   b(n-b(n))=b(n+1-b(n)) ou bien b(n-b(n))+1=b(n+1-b(n))
   ce qui signifie que Q(n+1) est vraie.
   
2. Supposons que b(n)=b(n-1)+1 et montrons qu’alors Q(n+1) est vraie.
   On a alors b(n-1)=b(n)-1 donc :
   b(n+1)=b(b(n))+b(n+1-b(n)) et
   b(n)=b(b(n)-1)+b(n+1-b(n)) (puisque on a supposé que b(n)=b(n-1)+1) Comparons b(b(n)) et b(b(n)-1).
   Soit j=b(n). On a vu précédemment que pour tout n>=1 on a 1<=j=b(n)<=n donc Q(j) est vraie donc b(j)=b(j-1) ou b(j)=b(j-1)+1
   b(b(n))=b(b(n)-1) ou b(b(n))=b(b(n)-1)+1
   donc on a :
   b(b(n))=b(b(n)-1) ou b(b(n))= b(b(n)-1)+1
   ce qui signifie que b(n+1)=b(n) ou bien b(n+1)=b(n)+1
   donc dans ce cas aussi Q(n+1) est vraie.
   Donc on a montré que :
   pour tout n>=2 on a b(n)=b(n-1) ou b(n)=b(n-1)+1

7  Exercice

1. Calculer les valeurs de b(k) pour k=0..8.
2. Écrire un programme batracion(n) qui calcule b(n)
3. Écrire un programme batrarc(n) qui affiche le graphe de b(n)/n en fonction de n pour 2<=n<=1000
4. Modifier le programme précédent pour tracer le graphe de b(n)/n en fonction de n pour 1000<=n<=5000

8  Solution

1. Les 9 premières valeurs de b sont :
b(0)=0;b(1)=1; b(2)=1,
b(3)=b(b(2))+b(3-b(2))=b(1)+b(2)=2
b(4)=b(b(3))+b(4-b(3))=b(2)+b(2)=2
b(5)=b(b(4))+b(5-b(4))=b(2)+b(3)=3
b(6)=b(b(5))+b(6-b(5))=b(3)+b(3)=4
b(7)=b(b(6))+b(7-b(6))=b(4)+b(3)=4
b(8)=b(b(7))+b(8-b(7))=b(4)+b(4)=4
Ou bien on tape pour avoir les valeurs de b(k) pour k=0..16 :
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 évitant des recopies de b, on modifie b en place :
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 écrit les programmes :
Lb(n) qui renvoie la suite (b(1),...b(n)) et
batracion(n1,n2) qui renvoie la suite (b(n1),...b(n2)) et
b(n) qui calcule la valeur de b(n)
On tape :

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;
  }:;

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];
  }:; 

On écrit le programme batrarc(p) qui renvoie 2 listes :
B qui est la liste b(k) pour k=1..2^p)
et
A qui est la liste b(k)/k pour k=1..2^p :

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];
}:;

On écrit le programme batramax(p) qui renvoie la liste :
DM qui est la liste du maximum des arches 2ⁿ⁻¹..2ⁿ à savoir :
[n-1,b(jm)/(jm pour n=2..p-1)

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];
}:;

On tape :
batramax(14)
On obtient les maximum des arches 2^p..2^p+1 pour p=1..13 :

[[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]]

On tape :
batramax(24)
On obtient (temps 89.73) le maximum des arches 2^p..2^p+1 pour p=1..23:

[[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]]

batramax(23)

[[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]]

On a par exemple pour p=21 les égalités :
3*2^20-e13,3*2^20-242164,2^21+806412,2903564

8.1  Des remarques

On remarque que m11<M13<m10 en tapant :
1662/3072<6320/11651<838/1536
On obtient :
vrai
On remarque que m13<M14<m12 en tapant :
6606/12288<12002/22223<1662/3072 On obtient :
vrai
On remarque que m14<M15<m11 en tapant :
6606/12288<24290/45083<1662/3072
On obtient :
vrai
On remarque que m17<M16<m13 en tapant :
104739/196608<48074/89516<6606/12288
On obtient :
vrai On remarque que m16<M17<m14 en tapant :
52584/98304<97226/181385<13212/24576
On obtient :
vrai
On remarque que m18<M18<m16 en tapant :
209478/393216<189095/353683<52584/983044
On obtient :
vrai
On remarque que m19<M19<m16 en tapant :
417526/786432<385703/722589<52584/98304
On obtient :
vrai
On remarque que m20<M20<m15 en tapant :
835052/1572864<758041/1423078<209478/393216
On obtient :
vrai
On remarque que m19<M21<m18 en tapant :
835052/1572864<1544473/2903564<835052/1572864
On obtient :
vrai On remarque que m19<M22<m18 en tapant :
835052/1572864<3024959/5696576<209478/393216
On obtient :
vrai On remarque que m21<M23<m20 en tapant :
1665242/3145728<6170687/11635316<835052/1572864 On obtient :
vrai

9  Comment transformer la liste L en la liste T ?

Pour comprendre l’évolution de b(n) en fonction de n i.e. le parcours du candidat 4 (cf partie I), on va écrire le programme LtoT(L) qui tranforme liste L des valeurs des distances au temps n=2^p..2^(p+1) en la liste T constituée successivement par le nombre de sauts et le nombre de pauses.
La fonction LtoT(L) renvoie une liste de premier terme L[0] suivie de T qui est la suite constituée successivement par le nombre de sauts et le nombre de pauses.

9.1  Le programme effectuant cette transformation

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];
}:;

Vérification du programme LtoT(L)
On vérifie le résultat sur le parcours du candidat 4 et on tape pour n=2³..2⁴ :
L(4):=[4,5,6,7,7,8,8,8,8]:;) T:=LtoT(L(4)
On obtient : [3,1,1,3] En effet pour passer de 4 à 5, puis de 5 à 6, puis de 5 à 7, le crapaud fait 3 sauts, puis il se repose 1 fois, ensuite il saute 1 fois et passe de 7 à 8 puis il fait 3 pauses. Bien voir qu’il y a 1 saut si 2 nombres consécutifs sont différents et il y a 1 pause si 2 nombres consécutifs sont égaux.

9.2  On transforme le parcours du candidat 4

On cherche maintenant à comprendre l’évolution du parcours du candidat 4.
On appelle B(p) la liste L(p) i.e la suite du candidat 4.
B(5) est donc la suite des valeurs de b(n) lorsque n=0..2⁵ :
On tape :
B5:=B(5)
On obtient :
(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 :
TB5:=LtoT(B5)
On obtient :
[0,1,1,1,1,2,2,3,1,1,3,4,1,2,1,1,2,1,4]
On a donc :
entre 2⁰+1 et 2¹] on a TB1=(1,1)
entre 2¹+1 et 2²] on a TB2= (1,1)
entre 2²+1 et 2³] on a TB3=(2,2)
entre 2³+1 et 2⁴] on a TB4=(3,1,1,3)
entre 2⁴+1 et 2⁵] on a TB5=(4,1,2,1,1,2,1,4)
On remarquera que ces listes sont :

• symétriques (on a : revlist(4,1,2,1)=(1,2,1,4),
• elles sont de longueur 2³ lorsque n∈ [2⁴+1..2⁵],
• elle débute par p lorsque n∈ [2^p+1..2^p+1]

On tape :
L(5)
On obtient :
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 :
T5:=LtoT(L(5))
On obtient une liste commençant par 16=2⁴ qui est la valeur de b(2⁵) suivi par une suite symétrique de longueur 2⁴ commençant par 5,1,3,1... i.e. :
[16,5,1,3,1,2,1,1,2,2,1,1,2,1,3,1,5]
On tape :
B6:=L(6)
On obtient :
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 :
T6:=LtoT(B6)
On obtient une liste de longueur 32=2⁵ commençant par L6(2^6)=2^5=32, puis par la suite commençant par 6,1,4,1,3,1,3,1,2,1,1,2, puis par sa suite symétrique.

[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]

On tape :
T7:=LtoT(L(7))
On obtient une liste commençant par 2⁶=64 puis par la suite :
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étrique :
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 à dire :

[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

On tape :
T8:=LtoT(L(8))
On obtient ne liste commençant par 2⁷=128 puis par la liste :

[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,

puis par sa liste symétrique :

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]

Attention
Pour éviter, d’avoir une première ligne et une dernière ligne différentes des autres lignes (le 6,1 suit le 8,1), on remplace 8,1 par (1,0,7,1) et 1,8 par (1,7,0,1).
On obtient :

[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,

suivi par sa liste symétrique :

  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]

On changera donc pour la suite des batracions la procédure LtoT(L) en BtoT(L) en rajoutant à la fin les instructions adéquates :

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];
}:;

On appelle B(p) la liste L4(p) i.e la suite du candidat 4 :

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;
  }:;

Pour obtenir le parcours du candidat 4 de n=2⁹ à 2¹⁰, on tape :
B(9)
On obtient le parcours du candidat 4 de n=2⁹ à 2¹⁰ un résultat qui est difficile à analyser :

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}

On tape :
T9:=BtoT(B(9))
On obtient en ne tenant pas compte du terme 256=2⁸ d’indice 0 :

 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,

suivi par sa suite symétrique :

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

On peut voir des blocs se former, pour les décrire on va définir la suite Lc(n,k) pour n>=k et on définit Lc(n,k) pour n<k par Lc(n,k)=revlist(Lc(k,kn)):

• pour n≥ 1 et k=0 , Lc(n,0)=(1,0),
• pour n≥ 1 et k=1, Lc(n,1)=(n,1),
• pour n≥ 1 et k=2, Lc(n,2)= (n,1,n-1,1...2,1,1,2), i.e. Lc(1,2)=(1,2) et pour n≥ 1 Lc(n,2)=(n,1,Lc(n-1,2))
• pour n≥ 2 et k=3, Lc(n,3)= Lc(n,2),Lc(n-1,2)...,Lc(3,2),Lc(2,3), i.e. Lc(2,3)=(2,1,1,2,1,3)=revlist(3,1,2,1,1,2)

On a ainsi :
Lc(n,0) la séquence (1,0) ,
Lc(n,1) la séquence (n,1)=(Lc(n,0),Lc(n-1,1)),
Lc(n,2) la séquence (n,1,(n-1),1,....3,1,2,1,1,2) i.e.
Lc(n,2)=(Lc(n,1),Lc(n-1,1)...Lc(3,1),Lc(2,1),1,2)
Lc(n,3) par (Lc(n,2),Lc(n-1,2),....Lc(3,2),Lc(2,2),1,3)
Lc(n,4) par Lc(n,3),Lc(n-1,3),....Lc(3,3),Lc(2,3),1,4
......
Lc(n,k) par Lc(n,k-1),Lc(n-1,k-1),....Lc(3,k-1),Lc(2,k-1),Lc(1,k)
On a alors :
Lc(2,0)=(1,0), Lc(2,1)=(2,1)
Lc(2,2)=(2,1,1,2)
Lc(2,3)=2,1,1,2,1,3
Lc(2,4)=2,1,1,2,1,3,1,4=revlist(Lc(4,2))
Lc(3,3)=3,1,2,1,1,2,2,1,1,2,1,3
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))
Lc(4,2)=4,1,3,1,2,1,1,2
Lc(4,3)=4,1,3,1,2,1,1,2,3,1,2,1,1,2,2,1,1,2,1,3 et
Lc(4,4)=Lc(4,3),Lc(3,4)
On voit alors que B(9) est égal à :
(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))=(Lc(9-k,k)$(k=0..9))
On a alors :
le première ligne :
1,0,8,1, i.e.Lc(9,0),Lc(8,1),
le deuxième bloc par :
7,1,6,1,5,1,4,1,3,1,2,1,1,2, i.e.Lc(7,2)
le troisième bloc par :
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.Lc(6,3)=Lc(6,2),Lc(5,2),Lc(4,2),Lc(3,2),Lc(2,2),1,3
le quatrième bloc par :
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. Lc(5,4)=Lc(5,3),Lc(4,3),Lc(2,3),1,4
Ainsi, on peut décrire B9 par :
(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))

9.3  Définition de Lc(n,k)

On a vu précédemment que la suite des batracions entre 2⁹ et 2¹⁰ pouvait se traduire par :

 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,

suivi par sa suite symétrique :

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

que l’on va traduire avec les définitions qui vont suivre par :
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ètres vaut :
p=9+0=8+2=7+3=...=9.
Les définitions des suites Lc(n,k) :

• Pour tout n, Lc(n,0)=(1,0) et
  Lc(0,n)=(0,1)
• Pour tout n>=1, Lc(n,1)=(n,1) et Lc(1,n)=(1,n) On a alors : Lc(n,1)=(Lc(1,0),Lc((n-1),1)),
• Pour n>=2, on définit :
  Lc(n,2) par Lc(n,2)=(n,1,(n-1),1,....3,1,2,1,1,2) et
  et Lc(n,2) par :Lc(2,n)= revlist(Lc(n,2)).
  ou encore
  Lc(n,2)=(Lc(n,1),Lc((n-1),1),....Lc(3,1),Lc(2,1),1,2)
  On a alors :
  Lc(2,2) est égale à 2,1,1,2,
  Lc(3,2) est égale à 3,1,2,1,1,2 et
  Lc(2,3) est égale à 2,1,1,2,1,3.
  On a :
  Lc(3,2)=Lc(3,1),Lc(2,2)==Lc(3,1),Lc(2,1),Lc(1,2)
• Pour n>=3, on définit Lc(n,3) par :
  Lc(n,3)=(Lc(n,2),Lc(n-1,2),....Lc(3,2),Lc(2,2),Lc(1,3))
  et Lc(3,n) par Lc(3,n)=revlist(Lc(n,3) i.e. par :
  Lc(1,3)=(1,3), Lc(2,3)=(2,1,1,2,1,3) On a alors :
  Lc(2,3) est égale à 2,1,1,2,1,3 et
  Lc(3,3) est égale à Lc(3,2),Lc(2,3)= 3,1,2,1,1,2,2,1,1,2,1,3,
• Pour n>=4, on définit Lc(n,4) par :
  Lc(n,4)=(Lc(n,3),Lc(n-1,3),....Lc(3,3),Lc(2,3),Lc(1,4))
  et Lc(4,n) par Lc(4,n)=revlist(Lc(n,4)
  On a alors :
  Lc(1,4)=(1,4) , Lc(2,4)=(2,1,1,2,1,3,1,4) Lc(3,4) est égale à (3,1,2,1,1,2,2,1,1,2,1,3,2,1,1,2,1,3,1,4)
• ......
• Pour n>=k>=2, on définit Lc(n,k) par :
  Lc(n,k)=(Lc(n,k-1),Lc(n-1,k-1),....Lc(3,k-1),Lc(2,k-1),Lc(1,k)) et
  Lc(k,n) par Lc(k,n)=revlist(Lc(n,k)
  On a alors :
  Lc(2,k) est égale à (2,1,1,2,1,3,1,4...1,k)
  Lc(3,k) est égale à :

  (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)
  

9.4  Le programme des suites Lc(n,k)

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;
  }:;

10  Comment transformer la liste T en la liste L ?

Écrire un programme qui tranforme une liste T qui a comme premier terme la valeur de la distance de départ en la liste L.
Par exemple si T1 est la liste de longueur s constituée successivement par le nombre de sauts et le nombre de pauses à partir du temps t=T[0]=2^p jusqu’au temps t=T[s−1]=2^p+1, T=2p,T1:
T[0]=2^p et T[1]..T[s-1] est la liste constituée successivement par le nombre de sauts et le nombre de pauses à partir du temps t=T[0]=2^p jusqu’au temps t=T[s−1]=2^p+1.
On tape :

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;
}:;

On tape :
L4(4)
On obtient :
8,9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16,17
On tape :
T4:= LtoT(L4(4))
On obtient :
[8,4,1,2,1,1,2,1,4]
On tape :
TtoL(T4)
On obtient :
8,9,10,11,12,12,13,14,14,15,15,15,16,16,16,16,16

11  Étude fe la suite des pentemilieu

11.1  Coordonnèes des milieux de l’intervalle [2^p,2^p+1]

Traitons tout d’abord 2 exemples : p=13 puis p=14.

• p=13
  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 n du milieu de B13 est égal à :
  2^13+2^12=3*2^12
  puisque le milieu de l’intervalle [2¹³,2¹⁴] vaut (2¹³+2¹⁴)/2=(3*2¹³)/2=3*2¹² Puisque le développement de (1+1)¹³ est une somme ayant un nombre pair de termes, on a :
  sum(comb(13,k) ,k=0..13)=2^(13)| et on a donc :
  sum(comb(13,k),k=0..6)=2^(12) donc on a
  3*2^12=2^13+sum(comb(13,k),k=0..6)
  La valeur b(n) du milieu de B13 est donc égale à :
  2^12+sum(comb(12,k),k=0..6)
  Puisque comb(12,k)=comb(11,k)+comb(11,k-1)=comb(11,k)+comb(11,12-k) on a:
  2^11=sum(comb(11,k),k=0..11)=sum(comb(12,k),k=0..5)+comb(11,5)
  la valeur b(n) du milieu de B13 est donc égale à :
  3*2^11+comb(11,5)
• p=14
  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éveloppement de (1+1)¹⁴ est une somme ayant un nombre impair de termes,l’indice du milieu de B14 est égal à :
  2^14+2^13=2^14+sum(comb(14,k),k=0..6)+comb(14,7)/2
  c’est aussi le milieu de l’intervalle [2¹⁴,2¹⁵] i.e. 2¹⁴+2¹³=3*2¹³.
  La valeur du milieu de B14 est égal à :
  2^13+sum(comb(13,k),k=0..6)+comb(13,6)/2=3*2^12+comb(12,6)
  c’est aussi 3*2^12+comb(12,6)

Remarque: Pour p=13 et pour p=14 on a égalité des pentes au milieu en effet :
puisque comb(12,6)=2*comb(11,5), on a :
3*2^12+comb(12,6)=2*(3*2^11+comb(11,5))
Cela se généralise puisque on a toujours :
comb(2n,n)=2*comb(2n-1,n-1)
On tape (sans tenir compte de la remarque) :

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];
 }:;

11.2  Limite de la suite des pentemilieu

On tape :

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;
}:;

On tape :
pmil(17),pmil(18),pmil(19),pmil(20),pmil(21),pmil1(22)
On obtient :
34913/65536,34913/65536,208763/393216,208763/393216,832621/1572864,832621/1572864 On remarque que pmil(2*p-1)=pmil(2*p) ce qu’on démontre facilement puisque :
lorsque p=2*n-1 les coordonnèes du milieu sont :
3*2^(2*n-2),3*2^(2n-3)+comb(2n-3,n-2) et lorsque p=2*n les coordonnèes du milieu sont :
3*2^(2*n-1),3*2^(2n-2)+comb(2n-2,n-1).
On a :
3*2^(2*n-1)=2*(3*2^(2*n-2)) et
puisque comb(2n-2,n-1)=comb(2n-3,n-1)+comb(2n-3,n-2)=2*comb(2n-3,n-1), on a : 3*2^(2n-2)+comb(2n-2,n-1)=2*(3*2^(2n-3)+comb(2n-3,n-2))
On tape pour p=2*n :
limit((3*2^(2*n-2)+comb(2*n-2,n-1))/(3*2^(2*n-1)),n=+infinity)
On obtient :
1/2
On tape pour p=2*n+1 :
limit((3*2^(2*n-1)+comb(2*n-1,n-1))/(3*2^(2*n)),n=+infinity)
On obtient :
1/2
Donc la suite des milieux tend vers 1/2.
Pour le montrer on se sert de l’équivalent de n! au voisinage de l’infini, équivalent obtenu grâce à la fonction Gamma (cf la démonstration dans la partie III.

12  Coordonnées du maximum de b(n)/n pour n∈[2^p...2^p+1]

12.1  Prenons comme exemple p=13 puis p=14

Si p=13 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 égal à :
2^13+sum(comb(13,k),k=0..6)
c’est aussi le milieu de l’intervalle [2¹³,2¹⁴] i.e. 3*2¹²
la valeur du milieu de B13 est égal à :
2^12+sum(comb(12,k),k=0..6)
c’est aussi 3*2^11+comb(11,5)

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];
}:;

On a :

nM(p):=nm(p)-comb(,);
bM(p):=bm(p)-comb(,);

On tape :
nM(14),bM(14)
On obtient :
24576,13212
On tape :
nM(15),bm(15)
On obtient :
49152,26292
On vérifie, on tape :
b(89516),b(48074)
On obtient :
13212,26292
On tape :
nm(14),bm(14)
On obtient :

//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)]);
   }:;

On tape :
Max(4,3,3*2^5-comb(5,3),3*2^6-comb(7,3))
On obtient :
101/178
On tape :
Max(5,4,3*2^7-comb(7,3),3*2^8-comb(9,4))
On obtient :
399/719
On tape :
Max(6,5,3*2^9-comb(9,4),3*2^10-comb(11,5))
On obtient :
1586/2897
On tape :
Max(7,6,3*2^11-comb(11,5),3*2^12-comb(13,6))
On obtient :
6320/11651
On tape :
Max(8,7,3*2^13-comb(13,6),3*2^14-comb(15,7))
On obtient :
24290/45083
On tape :

On obtient :

12.2  Une tentative pour trouver le maximum de l’arche

On écrit le progpamme qui renvoie la liste Lc(a,b).
On tape :

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;
  }:;

Puis on cherche le maximum de Lc(a,b) lorsque l’indice de départ vaut xd et la valeur de départ vaut yd On suppose dans un premier temps que a est impair.
On tape

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]);
    }:;  
      

On tape pour p=3 :
TrajetLc(2,1,9,5)
On obtient :
7/11
On tape pour p=5 :
TrajetLc(3,2,38,21)
On obtient :
13/22
On tape pour p=7 :
TrajetLc(4,3,3*2^6-comb(7,3),3*2^5+comb(5,2)-comb(6,3))
On obtient :
101/178
On tape p=9 :
TrajetLc(5,4,3*2^8-comb(9,4),3*2^7+comb(7,3)-comb(8,4))
On obtient :
399/719
On tape pour p=11 :
TrajetLc(6,5,3*2^10-comb(11,5),3*2^9+comb(9,4)-comb(10,5))
On obtient :
1586/2897
On tape pour p=13 :
TrajetLc(7,6,3*2^12-comb(13,6),3*2^11+comb(11,5)-comb(12,6))
On obtient :
6320/11651
On tape p=15 :
TrajetLc(8,7,3*2^14-comb(15,7),3*2^13+comb(13,6)-comb(14,7))
On obtient :
24290/45083
On tape pour p=17 :
TrajetLc(9,8,3*2^16-comb(17,8),3*2^15+comb(15,7)-comb(16,8))
On obtient :
97226/181385
On tape pour p=19 :
TrajetLc(10,8,3*2^18-comb(19,9),3*2^17+comb(17,8)-comb(18,9))
On obtient :
385703/722589
On tape pour p=21 :
TrajetLc(11,9,3*2^20-comb(21,10),3*2^19+comb(19,9)-comb(20,10))T
On obtient temps de l’évaluation 78.04:
1544473/2903564
Le temps étant trop long il faut améliorer le programme !

12.3  Combien de Lc(6,6) dans Lc(n,q) pour n>q?

• si q<6 il y a 0 Lc(6,6)
  
• si q=6+0 il y a 1=comb(n-6,0) Lc(6,6)
  
• si q=7=6+1 on a Lc(n,7)=(n,6),(n-1,6)...(8,6),(7,6),(6,6),(5,7)
  Puisque 6=n−(n−6), dans Lc(n,7) il y a n−5=comb(n-5),1) Lc(6,6)
  
• si q=8=6+2 on a 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))=(n−4)*(n−5)/2=comb(n-4),2)
  
• si q=9=6+3 on a Lc(n,9)=(n,8),(n-1,8)...(8,8),(7,8),(6,8),(5,8)
  Donc il y a :
  (n−4)*(n−5)/2+(n−5)*(n−6)/2+...+2*1/2comb(n-3),3)
  
• par récurrence on a donc pour q=q−6+6 :
  si n>q, dans Lc(n,q) il y a comb(n+q-12, q-6) Lc(6,6)

Remarque Si q<n) on en déduit par symétrie que le nombre de Lc(6,6) dans Lc(q,n) et le même que dans Lc(n,q) i.e. comb(n+q-12, q-6).
Si n==q) on en déduit que le nombre de Lc(6,6) dans Lc(n,n) est 2* fois celui de Lc(n,n-1) i.e. 2*comb(n+n-13,n-7) On tape :

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;
}:;

12.4  Où 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étriques par rapport à 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ère moitié de l’arche. En effet, cherchons où trouve le maximum pour différentes valeurs de p.

• Pour p=13.
  La première moitié de l’arche est décrite par les listes :
  Lc(13,0),Lc(12,1),Lc(11,2),Lc(10,3),Lc(9,4),Lc(8,5),Lc(7,6)
  En décomposant Lc(7,6) on a :
  Lc(7,6)=Lc(7,5),Lc(6,5),Lc(6,6)
  En décomposant Lc(6,6) on a :
  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 :
  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èes :
  xm13=3*2¹³⁻¹=12288 et ym13=3*2¹³⁻²+comb(13−2,(13−3)/2)=6606
  Avec le programme batramax, on a trouvé que le point de pente maximum a pour coordonnèes :
  xM13=11651 et yM13=6320
  On note :
  xe13=xm13-xM13=637 et ye13=xm13-yM13=286
  On a :
  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
  comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(2,0)=comb(13,3)=286
  On a décompose le premier Lc(6,6) rencontré.
  On a :
  Lc(6,6)=(6,5),(5,4),(4,3),(3,2),[(2,1)],(1,2),(2,3),(3,4),(4,5),(5,6))
  Donc le maximum est atteint à la fin du deuxième saut de Lc(2,1).
• Pour p=14.
  La première moitié de l’arche est décrite par les listes :
  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écomposant Lc(8,6) on a :
  (8,6),(7,6)=(8,5),(7,6),(7,6))=(8,5),(7,5),[(6,6)],(7,6)
  En décomposant Lc(6,6) comme précédament on a :
  (8,6),(7,6)=(8,5),(7,5),(6,5),(5,4),(4,3),(3,2),[(2,1)],(1,2),(2,3),(3,4),(4,5),(5,6))(7,6).
  On a décomposé le deuxième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=14, le point de pente maximum a pour coordonnèes xM14=22223 et yM14=12002.
  On note :
  xe14=xm14-xM14=2353 et ye14=xm14-yM14=1210
  On a :
  comb(13,6)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=432+636=2353
  et
  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 à la fin du deuxième saut de Lc(2,1).
• Pour p=15.
  La première moitié de l’arche est décrite par les listes :
  Lc(15,0),Lc(14,1),...,Lc(9,6),Lc(8,7)
  En décomposant Lc(8,7) on a :
  (8,7)=(8,6),(7,7)=(8,5),(7,6),(7,7))=(8,5),(7,5),[(6,6)],(7,7)
  On décompose Lc(6,6) comme pour p=13 et on a :
  (8,7))=(8,5),(7,5),(6,5),(5,4),(4,3),(3,2),[(2,1)],(1,2),(2,3),(3,4),(4,5),(5,6))(7,6),(7,7)
  On a décomposé le troisième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=15, le point de pente maximum a pour coordonnèes xM15=45083 et yM15=24290.
  On note :
  xe15=xm15-xM15=4069 et ye15=xm15-yM15=2002
  On a :
  comb(14,7)+comb(11,5)+comb(9,4)+comb(7,3)+comb(5,2)+comb(2,1)+1=3432+637=4069
  et
  comb(13,6)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=1716+286=2002
  Donc xe15=comb(14,7)+637 et ye15=comb(13,6)+286
• Pour p=16.
  La première moitié de l’arche est décrite par les listes :
  Lc(16,0),Lc(15,1),...,Lc(10,6),Lc(9,7),Lc(8,7)
  En décomposant Lc(9,7) on a :
  (9,7),(8,7)=(9,6),(8,6),(7,7),(8,7)= (9,6),(8,6),(7,5),(6,6),(6,7),(8,7)
  On a utilisé le quatrième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=16, le point de pente maximum a pour coordonnèes xM16=89516 et yM16=48074.
  Donc :
  xe16=xm16-xM16=8788 et ye16=xm16-yM16=4510
  On a :
  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
  comb(14,7)+comb(12,5)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=4224+286=4510
• Pour p=17.
  La première moitié de l’arche est décrite par les listes :
  Lc(17,0),Lc(16,1),...,Lc(11,6),Lc(10,7),Lc(9,8)
  On décompose Lc(9,8) on a :
  (9,8)=[(9,7)],(8,8)=(9,6),(8,6),(7,5),[(6,6)],(6,7),(8,8)
  On a utilisé le septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=17, le point de pente maximum a pour coordonnèes xM17=181385 et yM17=97226.
  Donc :
  xe17=xm17-xM17=15223 et ye17=xm17-yM17=7513 On a :
  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
  comb(15,8)+comb(12,5)+comb(10,4)+comb(8,3)+comb(6,2)+comb(4,1)+comb(1,0)=7227+286=7513
• Pour p=18.
  La première moitié de l’arche est décrite par les listes :
  Lc(18,0),Lc(17,1),...,Lc(11,7),Lc(10,8),Lc(9,8)
  On décompose Lc(10,8) on a :
  [(10,8),(9,8)=(10,7),[(9,7)],(8,8),(9,8)=
  (10,7),(9,6),[(8,7)],(8,8),(9,8)=
  (10,7),(9,6),(8,6),(7,5),[(6,6)],(6,7),(8,8),(9,8)
  On a utilisé le dix septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=18, le point de pente maximum a pour coordonnèes xM18=353683 et yM18=189695.
  Donc :
  xe18=xm18-xM18=39533 et ye18=xm18-yM18=20383
  On a :
  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
  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
• Pour p=19.
  La première moitié de l’arche est décrite par les listes :
  Lc(19,0),Lc(18,1),...,Lc(11,8),Lc(10,9)
  On décompose Lc(10,9) on a :
  (10,9)=[(10,8)],(9,9)=(10,7),[(9,7)],(8,8),(9,9)=
  (10,7),(9,6),(8,6),(7,5),[(6,6)],(6,7),(8,8),(9,9)
  On a utilisé le vingt septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=19, le point de pente maximum a pour coordonnèes xM19=353683 et yM19=189695.
  Donc :
  xe19=xm19-xM19=39533 et ye19=xm19-yM19=20383
  On a :
  comb(18,9)+comb(16,8)+comb(13,6)+637=63843
  comb(17,9)+comb(15,7)+comb(12,5)+286=31823
• Pour p=20.
  La première moitié de l’arche est décrite par les listes :
  Lc(20,0),Lc(19,1),...,Lc(11,9),Lc(10,9)
  On décompose Lc(11,9) on a :
  [(11,9)],(10,9)=(11,8),(10,7),([(9,8)],(9,9),(10,9)=
  (11,8),(10,7),(9,7),[(8,7)],(7,8),(9,9),(10,9)=
  (11,8),(10,7),(9,7),(8,6),(7,5),[(6,6)],(6,7),(7,8),(9,9),(10,9)
  On a utilisé le vingt septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=20, le point de pente maximum a pour coordonnèes xM20=1423078 et yM20=758041.
  Donc :
  xe20=xm20-xM20=149786 et ye20=xm20-yM20=77011
  On a :
  comb(19,9)+comb(18,9)+comb(15,7)+comb(13,6)+637=149786
  comb(17,9)+comb(15,7)+comb(12,5)+286=77011
• Pour p=21.
  La première moitié de l’arche est décrite par les listes :
  Lc(21,0),Lc(20,1),...,Lc(12,9),Lc(11,10)
  On décompose Lc(11,10) on a :
  (11,10)=(11,9),(10,9),[(9,9)],(8,10)=
  (11,8),(10,7),(9,7),[(8,6)],(6,7),(7,8),(9,9),(10,9)=
  (11,8),(10,7),(9,7),(8,5),(7,5),[(6,6)],(6,7),(7,8),(9,9),(10,10)
  (11,10)=(11,9),(10,10)=(11,8),(10,7),(9,7),(8,6),(7,7),(7,8),(9,9),(10,10)=
  (11,8),(10,7),(9,7),(8,6),(7,5),[(6,6)],(6,7),(7,8),(9,9),(10,10) On a utilisé le vingt septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=20, le point de pente maximum a pour coordonnèes xM20=1423078 et yM20=758041.
  Donc :
  xe21=xm21-xM21=242164 et ye21=xm21-yM21=120769
  On a :
  comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637=242164
  comb(19,9)+comb(17,8)+comb(14,6)+comb(12,5)+286=120769 On a aussi :
  xe21=xe16+comb(20,10)+comb(18,9)
  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)
• Pour p=22.
  La première moitié de l’arche est décrite par les listes :
  Lc(22,0),Lc(21,1),...,Lc(13,9),Lc(12,10),Lc(11,10)
  On décompose Lc(12,10) on a :
  (12,10),(11,10)=(12,9),(11,10),(11,10)=
  (12,9),(11,8),[(10,9)],(10,10),(11,10)=
  (12,9),(11,8),[(10,8),(9,7),[(8,7)],(7,8),(8,9)],(10,10),(11,10)
  [(8,7)],(7,8),(8,9)],(10,10),(11,10)=(8,6),(7,6),[(6,6)], (6,7),(7,8),(9,9),(10,10),(11,10)
  On a utilisé le vingt septième Lc(6,6) rencontré.
  Avec le programme batramax on a trouvé que pour p=20, le point de pente maximum a pour coordonnèes xM20=5696576 et yM20=3024959.
  Donc :
  xe22=xm22-xM22=594880 et ye22=xm22-yM22=305525
  On tape :
  comb(21,10)+comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637
  On obtient :
  594880
  On tape :
  comb(20,10)+comb(19,9)+comb(17,9)+comb(14,6)+comb(12,5)+286 On obtient :
  305525
  
• Pour p=23.
  On tape :
  comb(22,11)+comb(20,10)+comb(18,9)+comb(15,7)+comb(13,6)+637
  On obtient :
  947596
  On tape :
  comb(21,10)+comb(19,9)+comb(17,8)+comb(14,6)+comb(12,5)+286
  On obtient :
  473485
  (12,11)=(12,10),(11,11)=(12,9),(11,9),(10,10),(11,11)
  (12,11)=(12,9),(11,10),[(10,9)],(10,10),(11,11)
• Pour p=24.
  On tape :
  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 :
  
  On tape :
  
  On obtient :
  
  (13,11),(12,11)=(13,11)=(12,9),(11,9),(10,10),(11,11)
  (12,11)=(12,9),(11,10),[(10,9)],(10,10),(11,11)
  comb(23,11)+comb(22,11)
  //p=24 (13,11),(12,11)=(13,10),(12,11),(12,11)=(13,10),(12,10),(11,10),(10,11),(11,11),(12,11) //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^18+comb(18,9))/(3*2^19),(3*2^22+comb(22,11))/(3*2^23) 0.530911763509,0.530911763509,0.528031349182 comb(23,11)+947896,comb(22,11)+305525,(3*2^22+comb(22,11)-comb(22,11)-305525)/(3*2^23-comb(23,11)-947896) 2299974,1010957,0.536931144042
• Pour p=25.
  On tape :
  
  On obtient :
  
  On tape :
  
  On obtient :
  
  
• Pour p=26.
  On tape :
  
  On obtient :
  
  On tape :
  
  On obtient :
  
  
• Pour p=27.
  On tape :
  
  On obtient :
  
  On tape :
  
  On obtient :
  
  

13  La suite des pentemaximum

On peut trouver cette suite en utilisant les programmes précédents rappelés ici) et les programmes batramax1(p) (resp batramax2(p), batramax3(p), 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 :

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;
}:;

On tape pour avoir la pentemaximum des arches [2³,2⁴],[2⁴,2⁵],..[2³⁺²⁰..2³⁺²¹]:
batramaxn(3,21)
On obtient (Temps mis pour l’évaluation: 115.5) :
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 :
batramax1(24)
On obtient (Temps mis pour l’évaluation: 162.44) :
12109427/22866150

13.1  Un exercice et sa correction

Énoncé
À l’aide des fonctions Lc(n,k) décrire les trajets :
T5,T6,T7,T8
Correction
On a :
T5=(1,0,4,1,3,1,2,1,1,2,2,1,1,2,1,3,1,4,0,1)
Donc :
T5=(Lc(5,0),Lc(4,1),Lc(3,2),Lc(2,3),Lc(1,4),Lc(0,1))
ou bien :
T5=(Lc(5,0),Lc(4,1),Lc(3,3),Lc(1,4),Lc(0,1))
On a :
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 :
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 :
T6=(Lc(6,0),Lc(5,1),Lc(4,4),Lc(1,5),Lc(0,6))
On a T7= :
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 T7= :
(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 :
T7=(Lc(7,0),Lc(6,1),Lc(5,3),Lc(3,5),Lc(1,6),Lc(0,7))
On a :

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)

Donc T8= :
(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 :
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 :
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))

La partie III consiste à rappeler certaines propriétés des combinaisons.

14  Définition

On a pour pour 1≤ n et p≤ n:
comb(n,p)= n!/p!(n−p)!=n(n−1)...(n−p+1)/p!.
On tape :
comb(7,0)
On obtient :
1
On tape :
comb(7,1)
On obtient :
7
On tape :
comb(7,2)
On obtient :
21
On tape :
comb(7,3)
On obtient :
35
en effet (7*6*5)/3!=7*5=35
On tape :
comb(7,0)
On obtient :
1
en effet (7*6*5)/3!=7*5=35

15  Propriétés de base

On a pour 1≤ n et p≤ n :
comb(n,p)=n!/p!*(n−p)!=n*(n−1)*...*(n−p+1)/p!.
On a :
comb(n,p)=comb(n,n-p)
comb(n,p)=n/p*comb(n-1,p-1)
comb(n,p)=(n-p+1)/p*comb(n,p-1)
Pour n>0 on a comb(n,p)=comb(n-1,p-1)+comb(n-1,p)
n étant fixé l’application m-> comb(n,m) est croissante.

16  Propriétés utilisant la formule du binôme

• Rappel de la formule du binôme
  On a pour n∈ ℕ et x∈ ℝ :
  Sn=(1+x)^n=∑_k=0ⁿ comb(n,k)*x^k
• En remplaçant dans Sn, x par 1 on obtient :
  sum(comb(n,k),k=0..n)=2^n
  Si n=2p+1, Sn a alors un nombre pair de termes et puisque comb(n,p)=comb(n,n-p), on a :
  sum(comb(2p+1,k),k=0..p)=2^(2p-1)
  Par exemple :
  2^13+sum(comb(13,k),k=0..6)=3*2^12=12288
  Si n=2p, Sn a alors un nombre impair de termes.
  Puisque comb(n,p)=comb(n,n-p) et que
  comb(2*p,p)=2*comb(2*p-1,p-1)=2*comb(2*p-1,p) on a :
  sum(comb(2*p,k),k=0..p-1)+comb(2*p,p)/2=
  sum(comb(2*p,k),k=0..p-1)+comb(2*p-1,p-1)=2^(2p-1)
  Par exemple :
  2^12+sum(comb(12,k),k=0..6)=3*2^11+comb(11,5)=6606 Cela servira pour trouver l’expression de la suite des milieux des arches correspondant au parcours du candidat 4.
• En remplaçant x par 1 dans Sn, on obtient :
  a=sum(comb(n,k),k=0..n)=2^n et
  en remplaçant x par -1 dans Sn, on obtient :
  b=sum((-1)^k*comb(n,k),k=0..n)=0 En calculant a+b et a-b on en déduit que :
  a+b=2+2*comb(n,2)+2*comb(n,4)+2*comb(n,6)....=2^n
  a-b= 2*comb(n,1)+2*comb(n,3)+2*comb(n,5)....=2^n
  On définit :
  S0n= ∑_k=0^pcomb(n,2k+1) si n=2p et
  S0n= ∑_k=0^p−1comb(n,2k+1) si n=2p+1
  S1n= ∑_k=0^pcomb(n,2k-1) si n=2p et
  S1n= ∑_k=0^p−1comb(n,2k) si n=2p+1
  On a alors : S0n=S1n=2ⁿ⁻¹
  Par exemple :
  sum(comb(8,2*k),k=0..4)=sum(comb(8,2*k-1),k=0..4)=128=2^7
  sum(comb(9,2*k),k=0..4)=1+sum(comb(9,2*k-1),k=0..4)=256=2^8
  sum(comb(16,2*k),k=0..8)=sum(comb(16,2*k-1),k=0..8)=32768=2^7
  sum(comb(17,2*k),k=0..8)=1+sum(comb(17,2*k-1),k=0..8)=65536=2^8
  
• On montre par récurrence que :
  comb(p,p)+comb(p+1,p)+...+comb(p+(n-p),p)=comb(n+1,p+1)=comb(n-p,p+1) comb(p,0)+comb(p+1,1)+...+comb(p+(n-p),n-p)=comb(n+1,p+1) Par exemple :
  comb(5,0)+comb(6,1)+comb(7,2)+comb(8,3)=comb(9,6)
  car on a ici p=5 et n=8 comb(7,0)+comb(8,1)+comb(9,2)+comb(10,3)+comb(11,4)=comb(12,8)
  car on a ici p=7 et n=11

  17  Les combinaisons et la fonction Gamma

  Définition de la fonction Gamma
  La fonction Gamma est définie pour a>0 par :
  Gamma(a)=∫₀^inft^a−1e^−tdt
  Propriétés
  Lorsque a est un entier n>0 on a :
  Gamma(n)=∫₀^infxⁿ⁻¹e^−xdx
  On a alors :
  Gamma(1)=1
  Gamma(n+1)=n*Gamma(n)
  On a donc :
  Gamma(n+1)=n!
  On peut montrer que Gamma(1/2)=√π
  Lorsque n est grand la formule asymptotique de Gamma(n) est :
  Gamma(n+1)=√2nπnⁿe⁻ⁿe^{θ/(12*(n+1))} avec 0<θ<1.
  Quand n tend vers l’infini on a une formule asymptotique pour n! :
  n!=Gamma(n+1)≃ √2nπnⁿe⁻ⁿ

  18  Exercice

  Montrer que comb(2*n,n)/(3*2^(n+1)) tend vers 0 quand n tend vers +∞.
  Montrer que comb(2*n,n)/(2^2*n) tend vers 0 quand n tend vers +∞.
  On a :
  n!≃ √2nπnⁿe⁻ⁿ donc
  comb(2*n,n)=2n!/n!*n!≃ 2^2*n/√nπ
  donc :
  comb(2*n,n)/(2^2*n≃ 1/√nπ
  donc comb(2*n,n)/(3*2^(n+1)) tend vers 0 quand n tend vers +∞.
  Avec Xcas, on tape :
  limit(comb(2*n,n)/(2^(2*n)),n=+infinity)
  On obtient :
  0

This document was translated from L^AT_EX by H^EV^EA.