Le rendu de la pièce - Collège Alexandre Fleming (Orsay)

Dans le royaume du Gondor, le nouveau roi assemble les savants du royaume pour frapper sa monnaie. Il veut profiter de l’occasion pour choisir les valeurs p1 , . . . , pn des pièces de façon optimale, c’est à dire qu’avec un nombre minimal n de pièces, on veut pouvoir rendre toutes les valeurs inférieures à 500 avec aussi peu de pièces que possible.
L’un des savants propose de choisir les valeurs 1,2,3,5,7,11,13,17,19,... jusqu’à ce que la somme des valeurs soit supérieure à 500. Un autre propose 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . . Pouvez-vous faire mieux ? Quel est le meilleur choix ?
Pour ne pas avoir à jeter toutes les anciennes pièces de monnaie q1 , . . . , qn , le roi se demande comment rendre la monnaie de façon efficace, c’est à dire en utilisant le moins de pièces que possibles pour un montant donné. Avez-vous un algorithme (une méthode) à proposer ? Est-elle optimale ? Pouvez-vous donner une borne sur l’écart en nombre de pièces entre la solution donnée par votre algorithme, et une solution optimale ?