DS 6 (MP2I 2021-2022) — Matrices de Monge¶

Devoir surveillé · MP2I · 2021-2022 · partie I du DS 6 (4 h au total)

Autres parties : II. Le problème du monnayeur

Tout document ou dispositif électronique interdit.

Dans cette partie, on note $A[i,j]$ le coefficient situé sur la $i$-ème ligne et $j$-ème colonne d'une matrice.

Une matrice $A \in \mathcal{M}_{mn}(\R)$ est une matrice de Monge lorsque $\forall i, j, k$ et $l$ tels que $1 \le i < k \le m$ et $1 \le j < l \le n$, on a

\[ A[i,j] + A[k,l] \le A[i,l] + A[k,j] \]

Autrement dit, étant donné deux lignes et deux colonnes dans la matrice, leurs intersections sont les quatre sommets d'un rectangle dont on demande que la somme des éléments en haut à gauche et en bas à droite soit inférieure ou égale à la somme des éléments en haut à droite et en bas à gauche.

Par exemple, la matrice suivante est une matrice de Monge :

Une matrice de Monge et un rectangle : 17 + 37 le 44 + 28. — Une matrice de Monge et un rectangle : $17 + 37 \le 44 + 28$.

Un exemple de rectangle est présenté et on voit bien que $17 + 37 \le 44 + 28$. Cette propriété est vraie pour tous les sous-rectangles.

Question 1

Prouver qu'une matrice est de Monge si et seulement si

\[ \forall i \in \range{1}{m-1}, \forall j \in \range{1}{n-1}, A[i,j] + A[i+1,j+1] \le A[i,j+1] + A[i+1,j] \]

Corrigé

Il y a une implication directe $\Rightarrow$ par restriction.

Dans l'autre sens, on montre d'abord que :

\[ \forall i, k \in \range{1}{m}, \forall j \in \range{1}{n-1}, i < k \Rightarrow A[i,j] + A[k,j+1] \le A[i,j+1] + A[k,j] \]

Pour cela, on procède par récurrence sur $k-i$. L'hypothèse est exactement la propriété pour $k -i = 1$. Si la propriété est vraie au rang $r$, soit $k = i + r + 1$. On a, par hypothèse,

\[ A[i,j] + A[k-1,j+1] \le A[i,j+1] + A[k-1,j] \]

et

\[ A[k-1,j] + A[k,j+1] \le A[k-1,j+1] + A[k,j] \]

Donc,

\[ A[i,j] + A[k-1,j+1] + A[k-1,j] + A[k,j+1] \le A[i,j+1] + A[k-1,j] + A[k-1,j+1] + A[k,j] \]

et il suffit de simplifier pour avoir la propriété voulue.

On montre de même, par récurrence sur $l-j$, que la matrice est de Monge.

Question 2

La matrice suivante n'est pas de Monge. Changez un seul de ses éléments pour faire en sorte qu'elle le soit. On utilisera la question précédente.

\[ \begin{pmatrix} 37 & 23 & 22 & 32 \\ 21 & 6 & 7 & 10 \\ 53 & 34 & 30 & 31 \\ 32 & 13 & 9 & 6 \\ 43 & 21 & 15 & 8 \end{pmatrix} \]

Corrigé

On remarque que seul le carré

\[ \begin{pmatrix} 23 & 22 \\ 6 & 7 \end{pmatrix} \]

est problématique car $23 + 7 = 30 > 22 + 6 = 28$. Pour résoudre ce problème, le plus simple semble être de changer la valeur du coefficient valant 22 par une valeur $v \ge 24$.

Cependant, on doit avoir le carré suivant

\[ \begin{pmatrix} v & 32 \\ 7 & 10 \end{pmatrix} \]

qui satisfait la condition, donc $10 + v \le 39 \iff v \le 29$.

On peut ainsi prendre $v = 24$.

Question 3

Soit $f(i)$ l'indice de la colonne contenant l'élément minimum le plus à gauche de la ligne $i$. Prouver que $f$ est croissante pour une matrice de Monge. C'est-à-dire que $f(1) \le f(2) \le \dots \le f(m)$.

Corrigé

Si, par l'absurde, on a $i < j$ et $f(i) > f(j)$, alors pour le carré correspondant, comme la matrice est de Monge on devrait avoir :

\[ A[i,f(j)] + A[j,f(i)] \le A[i,f(i)] + A[j,f(j)] \]

Or, par minimalité, $A[i,f(i)] \le A[i,f(j)]$ et $A[j,f(j)] \le A[j,f(i)]$. On a donc $A[i,f(j)] + A[j,f(i)] = A[i,f(i)] + A[j,f(j)]$. Si $A[i,f(j)] > A[i,f(i)]$ alors $A[j,f(i)] < A[j,f(j)]$ pour compenser ce qui est contradictoire. Ainsi, $A[j,f(j)] = A[j,f(i)]$ et donc $A[i,f(j)] = A[i,f(i)]$ or l'élément sur la colonne $f(j)$ est plus à gauche que celui sur la colonne $f(i)$ qui était censé être le plus à gauche des minimaux. Contradiction.

Question 4

On présente un algorithme Diviser-pour-régner afin de déterminer le minimum le plus à gauche de chaque ligne dans une matrice de Monge $A$ :

On construit une sous-matrice $A'$ de $A$ contenant les lignes de numéro pair. On détermine récursivement le minimum le plus à gauche de chaque ligne de $A'$. Ensuite on détermine le minimum le plus à gauche de chaque ligne de numéro impair de $A$.

Expliquer comment déterminer le minimum le plus à gauche des lignes de numéro impair de $A$, sachant qu'on connaît ces minimums pour les lignes de numéro pair, en temps $O(m+n)$.

Corrigé

Il suffit de chercher le minimum pour la ligne $2p+1$ entre les colonnes $f(2p)$ et $f(2p+2)$ par croissance de $f$. Cette recherche effectue $f(2p+2)-f(2p)+1$ opérations élémentaires. On a donc en tout $\sum f(2p+2) - f(2p) + 1 = O(m+n)$ (au maximum on fait une comparaison pour chaque colonne autre que la première, donc $O(n)$, et on fait une affectation pour chaque écart, donc $m/2 = O(m)$).

Question 5

Écrire la récurrence régissant le temps de calcul de l'algorithme précédent. Montrer qu'on peut la résoudre et obtenir une complexité globale en $O(m + n \log m)$.

Corrigé

À $n$ fixé, notons $T_m$ le temps pour une matrice $(m,n)$, on a $T$ croissante et la récurrence

\[ T_{2m} = T_m + O(m + n) \]

Donc, il existe une constante $M$ telle que $T_{2m} \le T_m + M(m+n)$.

On a $T_{2^k} \le M (2^k + n k)$ par récurrence rapide :

\[ T_{2^{k+1}} \le T_{2^k} + M(2^k+n) \le M 2^{k+1} + n M (k + 1) \]

Ainsi, par croissance et encadrement, on conclut que $T_{m} = O(m+n \log m)$.