Cours et vidéos

Cours en ligne Vidéos classées

Concours corrigés

HECS
HECE

Programme de concours

HECS

Chaîne Youtube


Pour me soutenir



Autour du site

Auteur du site.
Cours particuliers.


Sommes multiples.


Nous montrons dans cette vidéo comment manipuler efficacement les sommes multiples.

Synopsis :

Niveau d'accessibilité : Terminale.


Exercices


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$.

Afficher

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)$$

Afficher

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)}$.

Afficher

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)$.

Afficher

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).$

Afficher

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)$.

Afficher

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