Décomposition
dans Arithmétique
Bonjour,
Soit $n$ un entier strictement positif, et $a_0, a_1, \dots, a_{n-1}$ des entiers positifs, tels que, si $I,J \subset \{0, \dots, n-1\}$, alors $\sum_{i \in I} a_i=\sum_{j \in J} a_j$ implique $I=J$. Est-ce que $a_{n-1} \geq 2^{n-1}$ ?
J'ai montré que $\sum_{i=0}^{n-1} a_i \geq 2^n-1$.
Merci d'avance.
Soit $n$ un entier strictement positif, et $a_0, a_1, \dots, a_{n-1}$ des entiers positifs, tels que, si $I,J \subset \{0, \dots, n-1\}$, alors $\sum_{i \in I} a_i=\sum_{j \in J} a_j$ implique $I=J$. Est-ce que $a_{n-1} \geq 2^{n-1}$ ?
J'ai montré que $\sum_{i=0}^{n-1} a_i \geq 2^n-1$.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Avec $n=3,\ a_0=4,\ a_1=2,\ a_2=1$, ton hypothèse est vérifiée, mais tu n'as pas $a_{n-1} \geq 2^{n-1}$. J'imagine que tu as oublié de dire que la suite est strictement croissante (si deux termes sont égaux, la condition n'est pas réalisée). Il doit être possible de montrer la conclusion plus forte : $\forall k = 0,\ ...,\ n-1,\ a_{k} \geq 2^{k}$, qui permet une récurrence.
Cordialement.
$\underbrace{1+2+3}_{I=\{1,2,3\}}=\underbrace{6}_{J=\{4\}}$
$a_1=1,a_2=2,a_3=3,a_4=6$ et $n=5$.
PS:
Pour l'unicité d'écriture d'un entier comme combinaison linéaire à coefficients dans $\{0,1\}$ de termes d'une suite voir suite super croissante.
Oui, tu montres que tu n'as pas compris l'énoncé puisque tu proposes une situation qui ne respecte pas l'hypothèse de Marco. Ni la conclusion.
Par contre, la dénomination de suite super croissante est une bonne idée.
Cordialement.
En effet, la suite $a_0=0,a_1=1,a_2=2,a_3=3,a_4=6,a_5=7,a_6=8,.....$ est bien strictement croissante mais:
$\underbrace{1+2+3}_{I=\{1,2,3\}}=\underbrace{6}_{J=\{4\}}$ n'entraîne pas que $I=J$.
L’Hypothèse est :
Si égalité des sommes sur I et J, alors égalité de I et J.
La Conclusion est :
L’inégalité avec la puissance 2.
Pour $n = 4$, on peut choisir $a_0 = 3$, $a_1=5$, $a_2=6$ et $a_3 = 7 < 2^3$.
Par récurrence, on peut alors, à partir d'une suite strictement croissante et adéquate $a_0, \cdots ,a_{n-1}$ de $n$ termes, construire une suite $b_0, \cdots , b_n$ de $n+1$ éléments ayant également les propriétés désirées en posant $b_0=1$ et $b_i = 2a_{i-1}$ pour $i \geq 1$.
On note que $\max{b_i} = 2\max{a_i}$, ce qui répond à la question initiale.
Par contre, une conjecture d'Erdös, prouvée par Ryavec, est que pour une suite dont toutes les sommes d'éléments sont deux à deux distinctes,
on a $\displaystyle{\sum_{i=0}^{n-1} \frac{1}{a_i} < 2}$.
Cela a été généralisé par Frenkel sous la forme $\displaystyle{\sum_{i=0}^{n-1} f(a_i) \leq \sum_{i=0}^{n-1} f(2^{i})}$, pour toute fonction $f$ convexe et strictement décroissante.
Pierre.
Si on suppose que la suite est super croissante on a une suite qui vérifie la condition d'unicité. Réciproquement, si on a la condition d'unicité je me demande si la suite est super croissante.
Une suite super croissante. $a_{n+1}=1+\sum_{k=0}^{n} a_k$ avec $a_0=0$.
$a_0=0,a_1=1,a_2=2,a_3=4,a_4=8,a_5=16,....$
Et on retrouve l'unicité de l'écriture en base $2$.
J'ai bien l'impression que si on veut que les $a_i$ soient les plus petits possibles, la suite des $2^n$ est celle qui réaliserait cette condition de minimum.
Alors $\sum_{i=0}^n \frac{1}{a_i} < \frac{b}{b-1}=\sum_{k =0}^{\infty} \frac{1}{b^k}$.
Et aussi, pour toute fonction convexe décroissante $g$, on a peut-être $\sum_{i=0}^n g(a_i) \leq \sum_{i=0}^n g(b^i)$.