Considérons le problème suivant.
On a trois boîtes $A$, $B$ et $C$ : la boîte $A$ contient $300$ pièces et les deux autres sont vides. Cinq opérations peuvent être répétées, dans un ordre quelconque (et pourvu qu'elles soient possibles) :
- Mettre $15$ pièces de la boîte $A$ dans la boîte $B$,
- Mettre $10$ pièces de la boîte $B$ dans la boîte $C$,
- Mettre $6$ pièces de la boîte $A$ dans la boîte $C$,
- Enlever $15$ pièces de la boîte $C$,
- Enlever $6$ pièces de la boîte $B$.
Quel est le nombre minimum d'opérations nécessaires à vider toutes les boîtes ?
Trouver un monovariant de la forme
$$x\cdot a+ y \cdot b + z \cdot c$$ où $a$, $b$ et $c$ représentent le nombre de pièces dans les boîtes $A$, $B$ et $C$ respectivement et $x$, $y$ et $z$ sont des constantes entières positives premières entre elles. Ce monovariant doit être tel qu'il diminue d'une certaine valeur positive constante $w$ à chaque opération (le nombre $w$ étant indépendant du type d'opération). Que vaut $x \cdot y \cdot z \cdot w$ ?
Pour pouvoir répondre aux exercices, vous devez être connecté.