Un exo olympique

einton

Salut Yann,

En fait personne n'a trouve la solution a ton exercice d'olympiade a priori. Je n'ai pas essaye avec ton indication (j'ai les oraux pour l'instant), avant je n'avais que c > 1/2. Tu pourrais mettre ta solution si tu as le temps ?

Vincent22

J'ai posé la question sur sci.math, vu que je ne trouvais pas non plus.
Voici la réponse (en anglais) de Erick Bryce Wong :

For any n >= 2, we define the weighted graph G_n with vertices 1,...,n
where the edge (i,j) has weight exactly 1/(i+j). We will find a lower
bound for the least-weight Hamiltonian path in G_n (open TSP tour).

Let p = (p_1 p_2 ... p_n) be any permutation of {1,...,n} representing a
Hamiltonian path, and define r_i = p_i + p_{i+1}, 1 <= i <= n-1, so that
the weight of the path p, denoted W(p), is exactly sum(1/r_i). We have:

sum(r_i) = 2*sum(p_i) - p_1 - p_n = n(n+1) - p_1 - p_n >= n^2 + n - 3.

Since all r_i's are positive, a convexity argument shows that for a given
value of sum(r_i), sum(1/r_i) is minimised when all r_i's are equal, thus

sum(1/r_i) >= (n-1)^2/(n^2+n-3) = 1-(3n-4)/(n^2+n-3) = 1 - 3/n + O(1/n^2).

[ Note: this bound is pretty close to tight, since the permutation
(1 n 2 n-1 3 n-2 ... 1+[n/2]) has a weight of 1 - 5/2n + O(1/n^2). ]

Now let {a_n} be a sequence satisfying the above. Fix m > 1, and sort
the elements {a_1,a_2,...,a_m} in ascending order:

a_{i_1} < a_{i_2} < ... < a_{i_m}.

Now | a_{i_m} - a_{i_1} |
= | a_{i_2} - a_{i_1} | + ... + | a_{i_m-1} - a_{i_m} |
>= 1/(i_1+i_2) + 1/(i_2+i_3)... + 1/(i_m-1 + i_m)
= W(i_1 i_2 ... i_m) >= 1 - O(1/m).

Thus a_{i_m} = max(a_1,...,a_m) >= 1 - O(1/m). Taking limits, we get
c >= sup{a_n} >= 1.

einton

merci Vincent

Simplet0

En lisant (sans vraiment tout comprendre :-( ) la solution de M. Wong, je me suis dit que qu'en même il devait y avoir une solution avec uniquement les connaissances requises pour une olympiade.
Je crois que j'ai une solution élémentaire inspirée (fortement !) de la solution very high-tech de M. Wong.

L'idée à avoir est bien de prendre une permutation des a(i).


Soit b(n) = a(f(n)) où f est une permutation qui rend les b(i) croissants :

0 <= b1 <= b2 <= ... <= bn <= c

Alors c >= b(n) - b(1) = (b(n) - b(n-1)) + .. + (b(2) - b(1)) >= 1/(f(n)+(fn-1)) + ... + 1/(f(2)+f(1))

Par Cauchy-Schwarz-Buniakowski : (somme x_i)*(somme 1/x_i) >= N^2

Chaque f(i) est comptés deux fois sauf f(n) et f(1) :
(f(n)+(fn-1)) + ... + (f(2)+f(1)) = n(n+1) - (f(n) + f(1)) <= n(n+1) - (1 + 2) = n^2 + n - 3


Donc c >= (n-1)^2 / (n^2 + n - 3) -> 1.