Le problème de Die Hard 3 revisité - Lycée d'Estienne d'Orves (Carquefou)

Établissement
Lycée d'Estienne d'Orves (Carquefou)
Année
2022-2023
Résumé
Le problème de Die Hard 3 : on dispose d’un bidon d’eau de 5L et d’un de 3L que l’on peut remplir et vider à volonté. Sachant que les bidons n’ont aucun marquage, comment obtenir exactement 4L dans le bidon de 5L ?
Une généralisation du problème : On dispose d’un bidon d’eau de n litres et d’un bidon de p litres où p est un nombre premier et où n > p n’est pas un multiple de p. Pour tout entier p < q < n, comment obtenir exactement q litres dans le bidon de n litres ?