Maximum du nombre de sommes...

Bonjour,

Tout d'abord, merci de t'être penché sur le problème mais j'ai l'impression que tu essayes de répondre à une autre question que celle que j'ai posée.

S'il s'agissait de trouver combien d'entiers peuvent s'écrire sous la forme $\sum\limits_{i=1}^{52}x_i$ avec $x_i \in \{1;\cdots;100\}$, la réponse serait simple : $52\times100-52+1=5149$ (voir la réponse de plumemeteore sur cet autre forum...).

La question est autre.

Si par exemple $x=(3;\cdots;3)$, les différents résultats qu'on peut obtenir en sommant des termes de $x$ sont $0;3;6;9;\cdots;153;156$. Par conséquent $S_x=53$.
Autre exemple : si $x=(50;100;50;100;50;100;\cdots;50;100;50;100)$, il est facile de voir que $S_x=79$.
Un dernier exemple astucieux pour générer beaucoup de sommes : $x=(1;2;4;8;16;32;64;100;100;\cdots;100)$ qui donne $S_x=4628$.

Je me demande comment trouver la valeur maximale prise par $S_x$ quand $x$ décrit $\{1;2;\cdots;100\}^{52}$ ? Pour l'instant, je n'ai pas trouvé mieux que $4628$.

JLT> Moi non plus, à vrai dire, je ne vois pas vraiment comment attaquer le problème...

Je pense qu'il est plus simple d'étudier le maximum de $S_x$ lorsque $x$ parcourt l'ensemble des suites à valeurs deux-à-deux distinctes[size=large]*[/size]. Mais lorsqu'on autorise $x$ à prendre plusieurs fois la même valeur, je ne parviens pas à m'en tirer.

J'avoue que je n'ai pas vraiment essayé de voir déjà comment cela se passait pour des suites plus courtes et prenant des valeurs plus petites.
Dans le cas particulier que tu évoques, sauf erreur, un programme informatique prouve que le maximum vaut $29$ et est atteint par exemple pour $x=(4;7;8;9;10)$.
Si on prend cette fois $6$ nombres entre $1$ et $10$, le maximum vaut 34 $39$ et est atteint par exemple pour $x=(4,7,8,9,10,10)$.

_____________
[size=large]*[/size] Dans mon exemple de $52$ nombres choisis entre $1$ et $100$, il est facile de montrer que le maximum $S$ en question est atteint pour $x_0=(49;50;\cdots;99;100)$ et vaut $3778$.
En effet, si on regarde les sommes de $0$ termes, $1$ termes, $2$ termes, .... , $51$ termes et $52$ termes de la suite $x_0$, elles décrivent respectivement les ensembles $\{0\}$ , $[49;100]$ , $[49+50;99+100]$ , $\cdots$ , $[49+\cdots+99;50+\cdots+100]$ et $\{49+\cdots+100\}$. On observe que les intervalles précédents recouvrent l'intervalle $[49;50+\cdots+100]$ et on constate que $S_{x_0}=3778$.
D'autre part, si $x$ ne prend que des valeurs deux à deux distinctes, alors $\cancel{S_x \leqslant 1+ \sum\limits_{k=1}^{52}x_k-(x1-1)-(x_2-1)=3+\sum\limits_{k=3}^{52}x_k$, d'où $S_x \leqslant 3+\sum\limits_{k=3}^{52}(48+k)=3778=S_{x_0}}$.

Edit : voir plus loin une correction du raisonnement ci-dessus suite au message de marco.

JLT a écrit:

Ah ? $(1,2,4,8,10,10)$ ne fait-il pas mieux ?

Non, sauf si je me suis emmêlé les pinceaux dans mon programme, avec $x=(1,2,4,8,10,10)$, on trouve $S_x=36$. (Il y avait une coquille dans mon message précédent, que j'ai corrigée. J'avais écrit $34$ au lieu de $39$.)

JLT a écrit:

Ca vaudrait peut-être le coup de faire tourner le programme pour 8 nombres compris entre 1 et 20, et voir si on trouve une solution qui ressemble un peu à (4,7,8,9,10,10), et ensuite deviner ce que pourrait être la solution pour 52 nombres compris entre 1 et 100.

Alors, j'ai fait tourner mon programme qui a réfléchi assez longtemps et voilà ce qui sort :

Le maximum est $102$, atteint pour $x=(5,10,16,17,18,19,20,20)$.

JLT a écrit:

Pour faire mieux que 4628, il suffirait de trouver une suite $x=(x_1,\ldots,x_7)$ de sept nombres entiers compris entre 1 et 100 telle que
1) Pour tout $k\in \{1,\ldots,100\}$, il existe une somme dans $S_x$ qui est congrue à $k$ modulo 100 ;
2) Il existe deux sommes dans $S_x$ qui diffèrent de $100n$ pour un certain entier $n\geqslant 2$.

Pour l'instant j'ai trouvé $(4,32,34,40,52,61,76,100, \cdots, 100)$ et $(28,56,78,82,86,87,88,100, \cdots, 100)$ qui vérifient la condition 1) et qui atteignent $4628$. Je n'ai pas encore trouvé (à supposer qu'il en existe) de suites qui vérifient 1) et 2).

Belle avancée, Marco !

Oui, je confirme.

Après quelques tâtonnements et un dernier coup de bluff avant de passer à table :

$x=(11,22,43,49,69,95,96,97,98,99,100,\cdots,100)$ me donne $S_x=4694$...

::o

On peut faire un tout petit peu mieux et prouver que $S_x \leqslant 5003$ (distinguer deux cas en comparant $x_3$ et $x_1+x_2$). On doit pouvoir encore raffiner mais la suite sera pour demain.

Merci pour vos contributions JLT et marco !

Une remarque simple en passant. Soit $x$ (croissante) tel que $S_x$ soit maximal. On a $4729 \leqslant S_x\leqslant 4+\sum\limits_{k=3}^{52}x_k$ donc $\sum\limits_{k=3}^{52}x_k \geqslant 4725$ ou encore $\sum\limits_{k=3}^{52}(100-x_k) \leqslant 275$. Si $3 \leqslant j \leqslant 52$, on a donc $(j-2)(100-x_j) \leqslant \sum\limits_{k=3}^{j}(100-x_k) \leqslant 275$ d'où $x_j \geqslant 100-\dfrac{275}{j-2}$.

Cela fournit déjà : $x_5 \geqslant 9$, $x_6 \geqslant 32$, $x_7 \geqslant 45$, $x_8 \geqslant 55$, $\cdots$, $x_{15} \geqslant 79$, $\cdots$, $x_{30} \geqslant 91$, $\cdots$, $x_{48} \geqslant 95$, $\cdots$, $x_{52} \geqslant 95$.

On doit pouvoir (r)affiner tout ça.