Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Minimisation sur les permutations

Posté par
Bactopin
25-11-23 à 21:06

Bonjour,
Je suis face à un problème de minimisation sur les permutations. On me demande de montrer l'égalité suivante :

\displaystyle\min_{\sigma\in\mathfrak{S}_n}\sum_{i=1}^n \lfloor \frac{\sigma(i)}{i}\rfloor = 1+\lfloor\log_2(n)\rfloor

En effet, il semble que pour la permutation suivante, la valeur de droite soit atteinte :

\sigma(i)=i-1\text{ si }\log_2(i)\notin\mathbb{N}
\sigma(i)=2i-1\text{ si }\log_2(i)\in\mathbb{N}

Si on écrit la permutation comme produit de cycles disjoints (voir exemple) on se rend compte que chaque cycle induit un unique 1 dans la somme, d'où le logarithme.
On a une minoration du minimum.

Exemple de \sigma optimal pour n=10 :

\sigma = \begin{pmatrix}1\end{pmatrix}\begin{pmatrix}3 & 2\end{pmatrix}\begin{pmatrix}7 & 6 & 5 & 4\end{pmatrix}\begin{pmatrix}10 & 9 & 8\end{pmatrix}

Simple remarque : 1+\lfloor\log_2(n)\rfloor=\lceil\log_2(n+1)\rceil

L'approche est-elle bonne ?
Avez-vous une idée de comment majorer le minimum ?

Merci de votre aide

Posté par
Bactopin
re : Minimisation sur les permutations 25-11-23 à 21:08

Excusez-moi, j'ai inversé les termes minoration et majoration. Le minimum est bien majoré mais pas encore minoré.

Posté par
thetapinch27
re : Minimisation sur les permutations 26-11-23 à 09:54

Bonjour,

Juste une piste que je n'ai pas testée ; ça ne fonctionne peut-être pas.

Intuitivement ça me paraît effectivement plein de bon sens que de proposer une permutation sous forme de "tronçons renversés" de longueur 2n pour minimiser la quantité.

Ensuite, on dirait qu'on peut prouver par récurrence que la somme est supérieure au membre de droite, et que le minimum est atteint avec la configuration que tu proposes.
* L'initialisation paraît simple.
* Si c'est vrai pour n, alors il y a deux cas :
  1- Soit n+1 n'est pas une puissance de 2, auquel cas la conclusion me semble rapide puisque le membre de droite ne bouge pas, et qu'on a plus de termes positifs ou nuls à sommer qu'auparavant (donc on ne peut qu'être plus grand que dans le cas "n").
  2- Soit n+1 est une puissance de 2 et là je dirais qu'il faut partir du cas minimal supposé dans l'hypothèse de récurrence et vérifier que ça fonctionne, et ensuite voir ce qui se passe si on échange le terme "n+1" (qui est une puissance de 2) avec un terme d'un autre "tronçon renversé" pour montrer qu'on ne peut que augmenter la quantité.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1673 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !