DS 6 — Matrices de Monge et problème du monnayeur¶

MP2I, année scolaire 2021-2022 — durée 4h, tout document ou dispositif électronique interdit.

Partie « Le problème du monnayeur » d'après l'épreuve d'informatique du concours Centrale-Supélec 2002.

Matrices de Monge¶

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

Le problème du monnayeur¶

Notations¶

$|E|$ désigne le cardinal de l'ensemble fini $E$.
$\lfloor x\rfloor$ désigne la partie entière inférieure du réel $x$, et $\lceil x\rceil$ sa partie entière supérieure : ce sont les relatifs définis respectivement par $\lfloor x\rfloor \leqslant x<\lfloor x\rfloor+1$ et $\lceil x\rceil-1<x \leqslant\lceil x\rceil$.
$\llbracket p, q \rrbracket$ désigne l'intervalle discret délimité par les naturels $p$ et $q$ : $\llbracket p, q \rrbracket=\{k \in \mathbb{N} \mid p \leqslant k \leqslant q\}$.

Présentation du problème¶

Nous nous intéressons au problème suivant, rencontré lors de la conception d'un monnayeur : comment rendre la monnaie, en utilisant le plus petit nombre possible de pièces ?

Formalisons ce problème : soit $\left(c_{i}\right)_{1 \leqslant i \leqslant m}$ une liste d'entiers non nuls, vérifiant

\[ c_{1}>c_{2}>\ldots>c_{m-1}>c_{m}=1 \]

Nous utiliserons le terme système pour désigner une telle liste. Les $c_{i}$ sont les valeurs faciales des pièces en service. Par exemple, si nous omettons les pièces de valeur inférieure à $1$ euro, le système utilisé en France est $(200, 100, 50, 20,10,5,2,1)$.

Pour chaque $i \in \llbracket 1, m \rrbracket$, nous disposons d'une quantité illimitée de pièces de valeur $c_{i}$. Soit $x$ un entier (le montant à rendre). Une représentation de $x$ dans le système $c$ est un $m$-uplet $\left(k_{i}\right)_{1 \leqslant i \leqslant m}$ de naturels vérifiant

\[x=\sum_{1 \leqslant i \leqslant m} k_{i} c_{i}\]

$k_{i}$ est donc le nombre de pièces de valeur $c_{i}$ que l'on doit rendre.

Pour épargner les poches des clients, nous souhaitons minimiser le poids de cette représentation, c'est-à-dire le nombre $\|k\|=\sum_{1 \leqslant i \leqslant m} k_{i}$ de pièces rendues.

Nous utiliserons en Caml des listes d'entiers pour représenter aussi bien un système (liste de valeurs de pièces), qu'une représentation d'un montant dans ce système. Par exemple, la liste $[4 ; 1 ; 3]$ est une représentation de 30 dans le système $(6,3,1)$.

Question 6. Rédigez une fonction de signature

est_un_systeme : int list -> bool

spécifiée comme suit : est_un_systeme c indique si la liste c est bien un système.

Par exemple, est_un_systeme [5 ; 2 ; 1] rendra la valeur true, tandis que est_un_systeme [5 ; 7 ; 1] rendra la valeur false, tout comme le fera est_un_systeme [7 ; 5 ; 2].

Corrigé

let rec est_un_systeme c =
  match c with
  | [] -> false
  | [x] -> x = 1
  | a :: b :: q -> a > b && est_un_systeme (b :: q)

Représentations de poids minimal¶

Soient $c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}$ un système et $x \geqslant 0$. Nous notons $M_{c}(x)$ (ou même $M(x)$ lorsqu'aucune ambiguïté n'est à craindre) le plus petit nombre de pièces nécessaires pour représenter $x$ dans le système $c$ :

\[ M(x)=\min \left\{\|k\| \mid k \in \mathbb{N}^{m} \text { et } \sum_{i=1}^m k_i c_i=x\right\} \]

Nous nous intéresserons aux représentations de poids minimal de $x$ : ce sont les représentations $k$ telles que $\|k\|=M(x)$. Pour alléger la rédaction, nous parlerons simplement de représentations minimales.

Question 7. Prouvez l'encadrement $\left\lceil x / c_{1}\right\rceil \leqslant M(x) \leqslant x$.

Question 8. Exhibez un système $c$ et un nombre $x>0$ possédant plusieurs représentations minimales dans le système $c$.

Question 9. Soient $c$ un système et $x>0$. Montrez que $M(x) \leqslant 1+M\left(x-c_{j}\right)$ pour tout indice $j$ tel que $c_{j} \leqslant x$.

Question 10. Soient $c$ un système, $x>0$ et $j$ tel que $c_{j} \leqslant x$. Montrez que $M(x)=1+M\left(x-c_{j}\right)$ si et seulement s'il existe une représentation minimale de $x$, faisant intervenir $c_{j}$ (c'est-à-dire telle que $k_{j}>0$).

Question 11. Soit $x>1$ ; notons $s$ le plus petit indice $i$ tel que $c_{i} \leqslant x$. Nous avons donc $c_{s} \leqslant x$ ; et, soit $s=1$, soit $s>1$ et $c_{s-1}>x$. Justifiez l'égalité

\[ M(x)=1+\min _{s \leqslant i \leqslant m} M\left(x-c_{i}\right) \]

Question 12. Soit $x > 0$. Montrez que l'on peut construire la liste des valeurs de $M(y)$ pour $y \leqslant x$, pour un coût $\mathcal{O}(m x)$.

Question 13. Rédigez en Caml une fonction de signature

poids_minimaux : int -> int list -> int list

spécifiée comme suit : poids_minimaux x c construit la liste des valeurs de $M_{c}(y)$, pour $1 \leqslant y \leqslant x$. Par exemple, poids_minimaux 5 [5 ; 2 ; 1] rendra la liste [1 ; 1 ; 2 ; 2 ; 1]. Vous utiliserez la formule de la question 11.

Si besoin, vous avez le droit uniquement pour cette question de passer des listes aux tableaux avec

Array.of_list : 'a list -> 'a array
Array.to_list : 'a array -> 'a list

L'algorithme glouton¶

L'algorithme glouton consiste à choisir le plus grand $c \leqslant x$, puis à rendre le montant $x-c$. Par exemple, avec le système $(10,5,2,1)$ l'algorithme glouton décomposera le montant 27 en $27=10+10+5+2$.

Avec le formalisme proposé, $m=4, c_{1}=10, c_{2}=5, c_{3}=2, c_{4}=1$ ; la solution fournie par l'algorithme glouton est le quadruplet $\left(k_{1}=2, k_{2}=1, k_{3}=1, k_{4}=0\right)$.

Le fonctionnement de l'algorithme glouton peut être accéléré avec la remarque suivante : notant $q=\left\lfloor x / c_{1}\right\rfloor$, cet algorithme rend $q$ pièces de valeur $c_{1}$, puis rend le montant $x-q c_{1}$ en utilisant le système $\left(c_{i}\right)_{2 \leqslant i \leqslant m}$.

Question 14. Rédigez une fonction de signature

glouton : int -> int list -> int list

spécifiée comme suit : glouton x c construit la représentation de $x$ dans le système $c$, en appliquant l'algorithme glouton.

Par exemple, glouton 13 [5 ; 2 ; 1] rendra la liste [2 ; 1 ; 1].

Corrigé

On applique directement la remarque précédente :

let rec glouton x c =
  match c with
  | [] -> []
  | ci :: q -> (x / ci) :: glouton (x mod ci) q

Soient $c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}$ un système et $x \geqslant 0$. Nous noterons $\Gamma_{c}(x)$ la représentation gloutonne de $x$ dans le système $c$, et $G_{c}(x)$ (ou même $G(x)$ lorsqu'aucune ambiguïté n'est à craindre) le nombre de pièces utilisées par l'algorithme glouton : $G_{c}(x)=\left\|\Gamma_{c}(x)\right\|$.

Nous dirons qu'un système $c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}$ est canonique si l'algorithme glouton donne toujours une représentation minimale ; on a donc $M(x)=G(x)$ quel que soit $x$.

Question 15. Montrez que tout système $c=\left(c_{1}, c_{2}\right)$ de deux valeurs est canonique.

Question 16. Exhibez un système $c=\left(c_{1}, c_{2}, c_{3}\right)$ non canonique.

Question 17. Soient $q$ et $n$ deux entiers $\ge 2$. Montrer que le système $(q^n, q^{n-1}, \dots, q, 1)$ est canonique.

Question 18. Montrer que le système Euro $(200, 100, 50, 20, 10, 5, 2, 1)$ est canonique.

On pourra montrer que dans une représentation minimale de $x$ : $k = (k_1,\dots,k_8)$, on a $k_8 \le 1, 2k_7 + k_8 \le 4, 5 k_6 + 2 k_7 + k_8 \le 9, \dots$.

Question 19. Avant la réforme de 1971 (introduisant un système décimal), le Royaume-Uni utilisait le système $(30,24,12,6,3,1)$. Montrez que ce système n'est pas canonique.

L'algorithme de Kozen et Zaks¶

Nous nous proposons de décrire un algorithme efficace permettant de déterminer si un système $c$ est canonique. Nous dirons qu'un entier $x$ est un contre-exemple pour $c$ si $M(x)<G(x)$. Un système canonique n'admet donc aucun contre-exemple.

Dans la suite, $m \ge 3$.

Question 20. Soit $c$ un système non canonique. Montrez qu'il existe un contre-exemple $x$ vérifiant l'encadrement

\[c_{m-2}+1<x<c_{1}+c_{2}\]

Nous allons montrer que l'intervalle de recherche des contre-exemples ne peut pas être diminué.

Question 21. Soit $q \geqslant 3$. Montrez que le système $(q+1, q, 1)$ n'est pas canonique. Quel est le plus petit contre-exemple pour ce système ?

Question 22. Soit $q \geqslant 3$. Déterminez $\alpha(q)>q$ tel que le système $(\alpha(q), q, 1)$ ne soit pas canonique, et admette $\alpha(q)+2$ comme plus petit contre-exemple.

Le résultat de la question 20 nous donne un algorithme déterminant si un système est canonique : il suffit de les rechercher dans l'intervalle discret $\llbracket c_{m-2}+2, c_{1}+c_{2}-1 \rrbracket$. Ceci nécessite la construction des représentations minimales de chacun des éléments de cet intervalle.

Nous allons étudier un algorithme plus efficace, dû à Kozen et Zaks ; leur méthode repose sur la notion de témoin. Nous dirons qu'un entier $x$ est un témoin pour le système $c=\left(c_{i}\right)_{1 \leqslant i \leqslant m}$ s'il existe un indice $i$ tel que $G\left(x-c_{i}\right)<G(x)-1$.

Question 23. Montrez que tout témoin est un contre-exemple.

Question 24. Montrez que le résultat de la question précédente n'admet pas de réciproque.

On pourra travailler dans le système $(5,4,1)$.

Question 25. Montrez que si le système $c$ admet des contre-exemples, alors le plus petit d'entre eux est un témoin.

Il résulte de cette étude que, pour savoir si un système est canonique, il suffit de vérifier l'inégalité $G(x) \leqslant G\left(x-c_{i}\right)+1$ pour tout $x \in \llbracket c_{m-2}+2, c_{1}+c_{2}-1 \rrbracket$, et tout indice $i \in \llbracket 1, m \rrbracket$ tel que $c_{i}<x$. C'est le principe de l'algorithme de Kozen et Zaks.

Question 26. En utilisant l'algorithme de Kozen et Zaks, montrer que les systèmes $(q, 2, 1)$, $(q \ge 3)$ et $(7,4,1)$ sont canoniques, alors que $(6,5,1)$ ne l'est pas.

Question 27. Rédigez en Caml une fonction de signature

kozen_zaks : int list -> bool

spécifiée comme suit : kozen_zaks c indique si la liste $c$ est canonique.

Par exemple, kozen_zaks [5 ; 2 ; 1] rendra la valeur true, tandis que kozen_zaks [6 ; 5 ; 1] rendra la valeur false. Vous utiliserez l'algorithme de Kozen et Zaks.

Question 28. Montrez que le coût de l'algorithme de Kozen et Zaks peut être exponentiel, par rapport au nombre $m$ de pièces du système.

On exhibera deux systèmes (l'un canonique, l'autre pas) pour lesquels le coût de l'algorithme est exponentiel en $m$.