Nous montrons dans cette vidéo comment manipuler efficacement les sommes multiples.
Synopsis :
Niveau d'accessibilité : Terminale.
Exercice (HEC 2014, 8, 9, 10) Soit $N$ un entier supérieur ou égal à 2. On considère $N$ réels $d_1,d_2,\dots,d_N$ (appelés points de départ) et $N$ réels $a_1,a_2,\dots,a_N$ (appelés points d'arrivée) vérifiant $d_1<\! d_2<\! \dots<\! d_N$ et $a_1<\! a_2<\! \dots<\! a_N$.
On pose : $D=\{d_1,d_2,\dots,d_N\}$ et $A=\{a_1,a_2,\dots,a_N \}$.
1.a) Montrer que pour tout couple $(k,l)\in[\![1,N]\!]^2$, on a : $d_ka_k\geq d_ka_l+d_la_k-d_la_l$.
Si $k\geq l$ alors $d_l-d_k\leq 0$ et $a_l-a_k\leq 0$, par conséquent $(d_l-d_k)(a_l-a_k)\geq 0$. De la même manière on montre que si $k\leq l$ on a aussi $(d_l-d_k)(a_l-a_k)\geq 0$. Donc dans tous les cas on a $(d_l-d_k)(a_l-a_k)\geq 0$. Il ne reste plus qu'à développer cette dernière inégalité et organiser pour trouver l'inégalité recherchée.
b) En déduire à l'aide d'une double sommation que pour tout $N$-uplet $(p_1,p_2,\dots,p_N)\in\mathbb R_+^N$ tel que $\sum_{k=1}^Np_k=1$, on a : $$\sum_{k=1}^Np_kd_ka_k\geq\left(\sum_{k=1}^Np_kd_k\right)\times\left(\sum_{k=1}^Np_ka_k\right)\ (1)$$
On multiplie l'inégalité de la question précédente par $p_kp_l$ puis on double somme sur $k$ et $l$. Grâce au fait que $\sum_{k=1}^Np_k=1$, on a : $$\begin{align} &\sum_{k=1}^N\sum_{l=1}^Np_kp_ld_ka_k\geq \sum_{k=1}^N\sum_{l=1}^Np_kp_l(d_ka_l+d_la_k-d_la_l)\\ &\Longleftrightarrow \sum_{l=1}^Np_l \sum_{k=1}^Np_kd_ka_k\sum_{k=1}^Np_kd_k\geq \sum_{k=1}^Np_kd_k\sum_{l=1}^Np_la_l+\sum_{k=1}^Np_ka_k\sum_{l=1}^Np_ld_l-\sum_{k=1}^Np_k\sum_{l=1}^Np_ld_la_l\\ &\Longleftrightarrow \sum_{k=1}^Np_kd_ka_k\geq \sum_{k=1}^Np_kd_k\sum_{l=1}^Np_la_l+\sum_{k=1}^Np_ka_k\sum_{l=1}^Np_ld_l-\sum_{l=1}^Np_ld_la_l. \end{align}$$ Il ne reste plus qu'à réorganiser et à changer le noms des indices de sommation pour obtenir le résultat recherché.
2. Soit une application $t:[\![1,N]\!]\to [\![1,N]\!]$. On réordonne la liste $(t(1),t(2),\dots,t(N))$ selon les valeurs croissantes et on note alors $(\hat t(1),\hat t(2),\dots,\hat t(N))$ la liste ordonnée obtenue. On a donc $\hat t(1)\leq\hat t(2)\leq\dots\leq\hat t(N)$.
a) Justifier pour tout $n\in[\![1,N]\!]$, l'inégalité : $\sum_{k=n}^Na_{t(k)}\leq\sum_{k=n}^Na_{\hat t(k)}$.
On observe que si on prend la somme des $p$ plus grand éléments parmi une liste donnée, cette somme sera plus grande qu'une somme quelconque d'autres éléments. Ici, comme $(a_1,\dots,a_N)$ est ordonée et que $(\hat t(1),\dots,\hat t(N))$ aussi, $\sum_{k=n}^Na_{\hat t(k)}$ est donc la somme des $N-n+1$ plus grand éléments de $(a_{t(1)},\dots,a_{t(N)})$ ce qui justifie l'inégalité.
b) On pose $d_0=0$. Justifier l'égalité : $\sum_{n=1}^Nd_na_{t(n)}=\sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)$.
On a $$\begin{align} \sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)&= \sum_{n=1}^Nd_n\sum_{k=n}^Na_{t(k)}-\sum_{n=1}^Nd_{n-1}\sum_{k=n}^Na_{t(k)}\\ &=\sum_{n=1}^Nd_n\sum_{k=n}^Na_{t(k)}-\sum_{n=0}^{N-1}d_{n}\sum_{k=n+1}^{N}a_{t(k)}\text{ (par changement d'indice)}\\ &=d_Na_N+\sum_{n=1}^{N-1}d_n\sum_{k=n}^Na_{t(k)}-\sum_{n=1}^{N-1}d_{n}\sum_{k=n+1}^{N}a_{t(k)}\text{ (on rapelle que }d_0=0)\\ &=d_Na_N+\sum_{n=1}^{N-1}d_n\left(\sum_{k=n}^Na_{t(k)}-\sum_{k=n+1}^{N}a_{t(k)}\right)\\ &=d_Na_N+\sum_{n=1}^{N-1}d_na_{t(n)}\\ &=\sum_{n=1}^{N}d_na_{t(n)} \end{align}$$
c) Etablir l'inégalité : $\sum_{n=1}^Nd_na_{t(n)}\leq\sum_{n=1}^Nd_na_{\hat t(n)}\ (2).$
Puisque les $d_n$ sont strictements ordonnés, on a $(d_n-d_{n-1})>0$, par conséquent d'après 9.a), on a $(d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\leq (d_n-d_{n-1})\sum_{k=n}^Na_{\hat t(k)}$. Il suit alors par 9.b) $$\sum_{n=1}^Nd_na_{t(n)}=\sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{t(k)}\right)\leq \sum_{n=1}^N\left((d_n-d_{n-1})\sum_{k=n}^Na_{\hat t(k)}\right)=\sum_{n=1}^Nd_na_{\hat t(n)},$$ et le résultat est prouvé.
On appelle programme de transport, toute bijection $T$ de $D$ sur $A$, et coût d'un programme de transport $T$, la somme $c(T)$ définie par : $c(T)=\sum_{k=1}^N(d_k-T(d_k))^2$.
3. Soit $\hat T$ le programme de transport défini par : pour tout $k\in[\![1,N]\!],\ \hat T(d_k)=a_k$.
Déduire des questions précédentes que le programme $\hat T$ est optimal, c'est à dire que pour tout programme de transport $T$, on a : $c(T)\geq c(\hat T)$.
D'abord on développe : $$c(T)=\sum_{k=1}^N(d_k-T(d_k))^2=\sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_kT(d_k)+\sum_{k=1}^N(T(d_k))^2.$$ $T$ étant une bijection et l'ordre ne comptant pas dans la sommation de $\sum_{k=1}^NT(d_k)$, nous avons : $$\sum_{k=1}^N(T(d_k))^2=\sum_{k=1}^Na_k^2=\sum_{k=1}^N(\hat T(d_k))^2.$$ D'autre part, $T$ étant une bijection, le n-uplet $(T(d_1),\dots,T(d_n))$ peut être représenté à l'aide des notations du dessus $(a_{t(1)},\dots,a_{t(n)})$ et le n-uplet $(\hat T(d_1),\dots,\hat T(d_n))$ par $(a_{\hat t(1)},\dots,a_{\hat t(n)})$, de sorte que (2) nous donne l'inégalité suivante : $$\sum_{k=1}^Nd_kT(d_k)=\sum_{k=1}^Nd_ka_{t(k)}\leq \sum_{k=1}^Nd_ka_{\hat t(k)}=\sum_{k=1}^Nd_k\hat T(d_k).$$ On a finalement : $$c(T)=\sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_kT(d_k)+\sum_{k=1}^N(T(d_k))^2\geq \sum_{k=1}^Nd_k^2-2\sum_{k=1}^Nd_k\hat T(d_k)+\sum_{k=1}^N(\hat T(d_k))^2=c(\hat T),$$ d'où le résultat.
Autre exercice de sommes multpiles combinées avec de l'algèbre linéaire : ECRICOME 2012 Problème Partie III 6.
Contacter l'auteur du site : frederic.millet @ math-sup.fr
