Correction Module 2 : Exercice 1

 

1/ Par définition de l’arbre binaire, on a  l(k+1)\\;=\\;2\\;l(k)  . On en déduit que  (l(k))_{k\\in \\mathbb{N}*}   est une suite géométrique de premier terme  l(0)=1   et de raison 2 , d’où l(k) \\,=\\, 2^k .

 

2/ a) La ligne 0 commence bien par  2^0 = 1 . Supposons pour un entier k donné que la ligne k commence par 2^k . Sachant qu’il y a  l(k)  entiers à la hauteur k , la  k+1ème ligne commence par l’entier  2^k + l(k)\\;=\\;2^k\\;+\\;2^k\\;=\\;2^{k+1} .
Par récurrence on a montré que pour tout entier naturel k , la kème ligne commence par 2^k .

    b) On a   2^{10}=1024\\;\\;\\;\\; \\leq \\;\\;\\;\\;1350 \\;\\;\\;\\;\\lt \\;\\;\\;\\;\\;2048=2^{11}  , l’entier 1350 se trouve donc sur la même ligne que 2^{10}, soit la 10ème ligne d’après le résultat de la question 2/a) .

 

3/ Si a et b sont deux puissances de deux, alors il existe deux entiers naturels p et q tels que a=2^p et b=2^q . On a alors :

H(ab)=H(2^p\\,2^q)=H(2^{p+q})=p+q   puisque la ligne p+q commence par 2^{p+q}

Or   p+q\\; = \\;H(2^p)\\;+\\;H(2^q)\\;=\\;H(a)\\;+\\;H(b)  car les lignes p et q commencent respectivement par 2^p et 2^q

D’où :    \\fbox{\\;H(ab)\\;=\\;H(a)\\;+\\;H(b)\\;}


Nous avons ici défini une fonction à valeurs entières H qui à un entier en entrée renvoie sa hauteur dans l’arbre binaire en sortie, et qui transforme les produits en sommes. Nous venons en fait de fabriquer une fonction logarithme : le logarithme entier en base deux. Il est dit « en base deux » car il est la fonction réciproque de la fonction puissance de deux ( n\\\\mapsto2^n  avec n un entier naturel). C’est-à-dire que notre logarithme « annule » les effets de la fonction puissance de deux, d’où l’appellation « fonction réciproque » :   H(2^n)\\\\,=\\\\,n

Un seul problème se pose à nous, la fonction puissance de deux n’est pas la réciproque du logarithme tel que nous l’avons défini ici :  2^{H(n)}  n’est pas toujours égal à n. Par exemple,   2^{H(9)}\\\\,=\\\\,2^3\\\\,=\\\\,8\\\\,\\\\,\\\\,\\\\,\\\\,\\\\,\\\\neq \\\\,\\\\,\\\\,\\\\,\\\\,\\\\,\\\\,\\\\,\\\\,\\\\,9
L’égalité n’est vraie que lorsque n est une puissance de deux.

Cela vient du fait que notre logarithme est ici défini d’un ensemble d’entiers sur un ensemble d’entiers (et de la non-injectivité de la fonction H, mais laissons ça pour plus tard) ; or dans l’équation  2^x=\\\\,9 ,   x  n’est pas entier.  

Cela pose donc le problème de définir ce qu’est un nombre mis à un exposant réel, ce qui n’est pas si intuitif. Nous devons également trouver une autre manière de définir une fonction logarithme, qui s’étendrait plus loin que les entiers naturels.

 

 

Retour à l’exercice 2