Est-ce que l'algorithme glouton l'emporte?

On se donne un réel k tel que 0 <= k <= 1/2.

Considérons n nombres positifs ou nuls écrits sur un tableau. En un mouvement, on peut effacer deux nombres a et b du tableau, et les remplacer par le nombre k(a+b). Après n-1 mouvements, il ne reste plus qu'un seul nombre au tableau; appelons ce nombre r.

Pour un nombre quelconque n de nombres initialement écrits au tableau, quels mouvements doivent être effectués afin d'obtenir la plus petite valeur possible de r?

Je conjecture qu'à chaque mouvement, on doit choisir pour a et b les deux plus grands des nombres présents au tableau. C'est une sorte d'algorithme glouton et il est plausible intuitivement qu'il fournisse le r minimal. Mais quelqu'un a-t-il une preuve?

Le problème est inspiré par une question d'Arthur Engel, qui demande de montrer que r >= 1/n pour k = 1/4.

Bonjour mathman ;
Je crois que le k doit être strictement inférieur à 1/2
car sinon ta conjecture risque de ne pas aboutir ,
Prendre par exemple le tableau de nombres : 1 , 2 , 3 , 5
en remplaçant les deux plus grands (3 et 5) par leur moyenne
on a le nouveau tableau : 1 , 2 , 4 , 4
et à partir de là ça devient stationnaire (sauf erreur bien entendu)

Ah oui je vois.
En fait je réalise qu'il manque un truc dans mon énoncé.

Citation :

Considérons n nombres positifs ou nuls écrits sur un tableau. En un mouvement, on peut effacer deux nombres a et b du tableau, et les remplacer par le seul nombre k(a+b). Après n-1 mouvements, il ne reste plus qu'un seul nombre au tableau; appelons ce nombre r.

J'ai juste rajouté le mot "SEUL".

Du coup dans ton exemple, avec k = 1/2, on aurait 1, 2, 4 en fait.

J'ai résolu ce problème je crois.
Par contre il faudra que je formalise tout ça et ça ne sera pas facile.

Evidemment, si quelqu'un est intéressé, je peux poster l'esquisse de ma preuve.