Théorie > Combinatoire > Invariants et (mono)variants

Exercice 4 (9 points) (48% de réussite au premier essai)

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