Genre inégalité du réordonnement

[Hadoque]

Bonjour à tous. Alors je bloque sur une question, qui est très évidente intuitivement, et dont je soupçonne la démonstration de n'être pas si évidente (comme par exemple pour l'inégalité du réordonnement). Ou bien j'ai loupé quelque chose. Alors voilà

on se donne n entiers naturels m1, m2, ..., mn rangés dans l'ordre décroissant (le plus grand est donc m1, le plus petit mn). Soit sigma une permutation de 1..n. On cherche à minimiser le maximum des mi + sigma(i) ; plus précisément à montrer que le minimum pour sigma une permutation de la quantité max(m1 + sigma(1), ..., mn + sigma(n)) est atteint pour sigma = identité.

Il me semble qu'on peut supposer sans trop de difficulté pour se ramener au cas général que les mi sont tous distincts (ce qui revient à supposer qu'ils sont rangés dans l'ordre strictement décroissant). On a alors, pour sigma = identité, max(m1 + 1, ..., mn + n) = m1 + 1 est le problème est un peu plus simple. M'enfin... J'aboutis pas.

Merci de vos éclairages

[V@J]

Tu peux partir du fait que $ a \leq b $ et $ c \leq d $, alors $ \max\{a+c,b+d\} \geq \max\{a+d,b+c\} $.
Suite du raisonnement ;

SPOILER:

Puis tu construis, de proche en proche, des permutations $ \sigma_k $telles que $ \sigma_k(l) = l $ dès que $ l \leq k $ : tu poses
- $ \sigma_0 = \sigma $ ;
- $ \sigma_{k+1} = \sigma_k $ si $ \sigma_k(k+1) = k+1 $ ;
- $ \sigma_{k+1} = \epsilon_{k+1,l} \circ \sigma_k $ si $ \sigma_k(k+1) = l > k+1 $, où $ l $ est la transposition qui échange $ k+1 $ et $ l $.
Avec l'inégalité de la première ligne, tu montres alors que $ \max\{m_i + \sigma_{k}(i)\} \geq \max\{m_i + \sigma_{k+1}(i)\} $. Donc $ \max\{m_i + \sigma(i)\} \geq \max\{m_i + \sigma_{n}(i)\} = \max\{m_i + i\} $, minimum atteint quand $ \sigma = Id $.

Bonne année,

V@J

[Hadoque]

Merci à toi