Exercice mathématiques première générale

Exercice 1 :

1. Dans cet arbre, il y a 4 nœuds ainsi que la racine, donc la taille 1 est de 5.

Sur la branche la plus longue, il y a trois arrêtes donc la hauteur 1 est 3.

Oscar et Tartuffe n’ont pas d’enfants, donc le nombre de feuilles est de 2.

2. a) On cherche à encadrer le nombre de feuilles d’un arbre de hauteur 3. Le minimum de feuilles d’un arbre de hauteur 3 où chaque nœud a 1 seul enfant est égal à F = 1 tandis que le maximum de feuilles d’un arbre de hauteur 3 où chaque nœud a exactement 2 enfants est égal à F = 8. Donc, le nombre de feuilles est compris entre 1 et 8. Alors, 1 ≤ F ≤ 8.

b. La taille minimum d’un arbre de hauteur 3 où chaque nœud a un seul enfant est de 4 nœuds. La taille maximale d’un arbre de hauteur 3 où chaque nœud a deux enfants est de 15 nœuds.  Alors, 4 ≤ T ≤ 15.

3. () une suite géométrique de 1er therme  [pic 1][pic 2]

On calcule la somme des termes d'une suite de puissances de q = 2.

S =  =  = 511.    [pic 3][pic 4]

4. a) On sait que chaque nœud a un et un seul fils et que la hauteur h est strictement positive, donc cet arbre contient une feuille F = 1.

b) Pour h quelconque strictement positive, chaque nœud ayant exactement un fils, il y a un nœud par génération, soit h nœuds. Donc, la taille d'un arbre binaire filaire est T = h+1.

5. a) la suite dans laquelle  contient le nombre de nœuds se trouvant à la hauteur n, avec .[pic 5][pic 6][pic 7]

On sait que  = 2, puisque chaque nœud a exactement 2 fils. De même pour = 4. On remarque qu’à chaque hauteur, le nombre de nœud va doubler. [pic 8][pic 9]

Donc,  la suite géométrique de raison q = 2 et de 1er terme . Pour tout n, on a :  = 2[pic 10][pic 11][pic 12][pic 13]

(  [pic 14][pic 15]

b) La suite  est géométrique puisqu’il existe un nombre réel q tel que, pour tout n dans N,  = 2[pic 16][pic 17][pic 18]

La suite étant géométrique : 

Soit  une suite géométrique de raison q = 2 et de 1er terme = 1. Alors pour tout n dans N,  =  x  [pic 19][pic 20][pic 21][pic 22][pic 23]

Donc,  = 1 x =  [pic 24][pic 25][pic 26]

Finalement, le nombre total de feuilles d'un arbre de hauteur h est égal au nombre de nœuds du dernier niveau, donc celui de rang h. Alors, on peut en déduire que le nombre total de feuilles sur un arbre de hauteur h est égal à   feuilles.[pic 27]

c) Avec l’expression explicite de , on sait que la taille S d’un arbre complet de hauteur h est égale à la somme des nombres de nœuds de chaque hauteur n, compris entre le rang 0 et le rang h. [pic 28]

Alors, on sait que :

   S = 1 + 2 + 4 + 8 + …  [pic 29][pic 30][pic 31]

Si q ≠ 1 alors pour tout entier naturel n, S =    [pic 32][pic 33]

Donc, S = 1 ×  =  = - () = [pic 38][pic 34][pic 35][pic 36][pic 37]

6. Le nombre de feuilles minimum est le nombre de feuilles d’un arbre filaire, donc F = 1. Le nombre de feuilles maximum est le nombre de feuilles d’un arbre complet, donc F = Le nombre de feuilles est compris entre 1 et , donc 1 ⩽ F .[pic 39][pic 40][pic 41]

La taille T d’un arbre binaire de hauteur h est comprise entre et , donc h + 1 ⩽ n ⩽ .[pic 42][pic 43][pic 44]

...