Lecture zen
*
optimisation, combinatoire
Quelle est la valeur maximum \(f(n)\) de \[\vert\sigma(1)-\sigma(2)\vert+\vert\sigma(3)-\sigma(4)\vert+\dots+\vert\sigma(n-1)-\sigma(n)\vert\] \(\sigma\) décrivant toutes les permutations de \(\{1,2,\dots,n\}\) ?
Barre utilisateur
[ID: 3061] [Date de publication: 9 novembre 2022 23:17] [Catégorie(s): En cours... ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]Solution(s)
Solution(s)
optimisation, combinatoire
Par Patrice Lassère le 9 novembre 2022 23:17
Par Patrice Lassère le 9 novembre 2022 23:17
Remarque liminaire : dans une configuration optimale les termes \(\sigma(i)\) doivent alternativement croitre et décroitre : en effet si \(\sigma(i)<\sigma(i+1)<\sigma(i+2)\) (ou \(\sigma(i)>\sigma(i+1)>\sigma(i+2)\)) alors \(\vert \sigma(i)-\sigma(i+1)\vert+\vert \sigma(i+1)-\sigma(i+2)\vert=\vert \sigma(i)-\sigma(i+2)\vert\), si bien que la permutation associée à l’une des deux deux suites d’entiers \((\sigma(i+1),\sigma(1),\dots,\sigma(i),\sigma(i+2),\dots,\sigma(n))\) et \((\sigma(1),\dots,\sigma(i),\sigma(i+2),\dots,\sigma(n),\sigma(i+1))\) fournira une somme strictement plus grande que celle associée à \(\sigma\).
Passons à la solution. Mieux vaut distinguer les cas \(n\) pair et impair. Si \(n=2m\)............
Documents à télécharger
L'exercice