La dernière moyenne

Publié le 29/01/17

On écrit une liste de n nombres réels.
On en efface deux, pris au hasard, pour les remplacer par leur demi-somme.
On répète cette opération jusqu’à ce qu’il reste un seul réel X.
Quelle est la valeur minimum possible pour X? Illustrer avec Python.
Chacun des n réels participe (soit directement, soit indirectement quand il a déjà été effacé) à un certain nombre des {n-1} moyennes successives.

Par exemple, si {E=\{x,y,z,t,u,v\}}, on peut passer à {\Bigl\{\dfrac{x}2+\dfrac{z}2,y,t,u,v\Bigr\}},

puis obtenir {\Bigl\{\dfrac{x}2+\dfrac{z}2,\dfrac{y}2+\dfrac{t}{2},u,v\Bigr\}}, puis {\Bigl\{\dfrac{x}4+\dfrac{z}4+\dfrac{u}2,\dfrac{y}{2}+\dfrac{t}2,v\Bigr\}},

puis {\Bigl\{\dfrac{x}8+\dfrac{z}8+\dfrac{u}4+\dfrac{v}2,\dfrac{y}{2}+\dfrac{t}{2}\Bigr\}}, et enfin {\Bigl\{\dfrac{x}{16}+\dfrac{z}{16}+\dfrac{u}8+\dfrac{v}4+\dfrac{y}{4}+\dfrac{t}{4}\Bigr\}}.

Ici {x} a donc été sollicité {4} fois, alors que {t} ne l’a été que deux fois.

Sur cet exemple, obtient la somme minimum quand {\{x,z\}\ge u\ge \{v,y,t\}} (autrement dit quand les plus grands éléments sont aussi les plus sollicités, c’est logique).

Supposons {E=\{x_1,x_2,x_3,x_4,x_5,x_6\}} avec x_1\le x_2\le x_3\le x_4\le x_5\le x_6.

Alors la somme minimum est obtenue en maximisant le nombre de fois où {x_6}, puis {x_5}, etc. sont sollicités dans le calcul.

Le résultat minimum dans ce cas exemple est alors:
{\begin{array}{rl}S&=\dfrac{1}{2}\Big(x_1+\dfrac{1}{2}\Big(x_2+\dfrac{1}{2}\Big(x_3+\dfrac{1}{2}\Big(x_4+\dfrac{1}{2}\Big(x_5+x_6\Big)\Big)\Big)\Big)\Big)\\\\&=\dfrac{x_1}{2^{1}}+\dfrac{x_2}{2^{2}}+\dfrac{x_3}{2^{3}}+\dfrac{x_4}{2^{4}}+\dfrac{x_5}{2^{5}}+\dfrac{x_6}{2^{5}}\\\\&=\dfrac{x_1}{2^{1}}+\dfrac{x_2}{2^{2}}+\dfrac{x_3}{2^{3}}+\dfrac{x_4}{2^{4}}+\dfrac{x_5}{2^{5}}+\dfrac{x_6}{2^{6}}+\dfrac{x_6}{2^{6}}\\\\&=\displaystyle\sum_{i=1}^{6}\dfrac{x_{i}}{2^i}\;+\;\dfrac{x_{6}}{2^6}\end{array}}Plus généralement supposons E=\{x_1,x_2,\ldots,x_n\}, avec x_i\le x_{i+1}.

Alors la somme minimum est {X_{m}=\displaystyle\sum_{i=1}^{n}\dfrac{x_{i}}{2^i}\;+\;\dfrac{x_{n}}{2^n}}

Par exemple, si E=\{2,2^2,\ldots,2^n\}, alors {X_{m}=\dfrac{2^{n}}{2^n}+\displaystyle\sum_{i=1}^{n}\dfrac{2^i}{2^i}=n+1}.

De même, si E=\{1,2,\ldots,n\}, alors {X_{m}=\dfrac{n}{2^n}+\displaystyle\sum_{i=1}^{n}\dfrac{i}{2^i}=2-\dfrac{1}{2^{n-1}}}.

La fonction ledernier applique l’algorithme à une liste L et renvoie l’élément final :

L’expression experiment(n,N) applique N fois l’algorithme à la liste \{0,1,\ldots,n\}.

Elle renvoie un histogramme des N résultats, en comptant les effectifs sur des intervalles [k,k+1[, avec n/4\le k\le 3n/4) :

Voici un exemple d’affichage obtenu avec n=100 et N=100000 :

article-29-01-17-hist

La symétrie observée par rapport à la valeur n/2 tient au fait que les variables aléatoires X et n-X ont ici la même loi (imaginer des jetons marqués k sur une face et n-k sur l’autre).