1. La condition d_k-1 = 1 est nécessaire et suffisante.
2. Choisir la plus grande espèce ne dépassant pas le montant (restant à) payer et recommencer jusqu'à plus soif.

3. static int [] glouton(int [] system, int m) {     int [] r = new int[system.length] ;     for (int i = 0 ;  m > 0 ; i++) {       int d = system[i] ;       r[i] = m/d ;       m %= d ; // Pour m = m % d ;     }     return r ;   }

   On note le calcul de t_i espèce par espèce, à l'aide d'une division.
   
   
4. 1. Voici le tableau, puis les justifications.

      i	8	7	6	5	4	3	2	1
      di-1	2	5	10	20	50	100	200	500
      bi	1	4	9	19	49	99	199	499

      • Avec ⟨ 5, 2, 1 ⟩. Un paiement T optimal contient au plus une pièce de 5 euros (par le doublement 5 + 5 = 10). On a ensuite V₆(T) ≤ 1 × 5 + b₇ = 9.
      • Avec ⟨ 10, 5, 2, 1 ⟩ par le même argument de doublement.
      • Avec ⟨ 20, 10, 5, 2, 1 ⟩, par 20 + 20 + 20 = 50 + 10, T contient au plus deux billets de 20. On distingue alors trois petits sous-cas :
        • Si T contient effectivement deux billets de 20, alors T ne peut pas contenir de billet de 10 (car 20 + 20 + 10 = 50), et donc V₄(T) ≤ 40 + b₆ = 49.
        • Si T contient un seul billet de 20, alors V₄(T) ≤ 20 + b₅ = 39.
        • Enfin, si T ne contient pas de billet de 20, alors on a évidemment V₄(T) ≤ b₅.
        Bref on a V₄(T) ≤ 49.
      • Par doublement (50 + 50 = 100), on a V₃(T) ≤ 50 + b₄ = 99.
      • Par doublement (100 + 100 = 200), on a V₂(T) ≤ 100 + b₃ = 199.
      • Le raisonnement est le même que pour 20 et donne la borne V₁(T) ≤ 400 + b₃ = 499.
      
      
      
   2. La condition V_i(T) < d_i-1 est en fait assez forte, elle entraîne l'unicité du paiement optimal qui est le paiement glouton. En effet on a, dans tous les cas, les égalités. m = V₀(T) = t₀ × d₀ + V₁(T), V₁(T) = t₁ × d₁ + V₂(T), ..., V_i(T) = t_i × d_i + V_i+1(T), ... Mais ici, en raison des inégalités, V_i+1(T) < d_i, les t_i sont complètement déterminés, par unicité du quotient (et du reste) de la division euclidienne de V_i(T) par d_i. Enfin, l'unique paiement optimal est bien le paiement glouton, tel que calculé à la question précédente.
   
   
   
5. On recherche un contre-exemple, il s'agit de 48. En effet un paiement possible est alors 24 + 24, tandis que le paiement glouton est 30 + 12 + 6. L'étude du système européen conduit à considérer le sous-système ⟨ 30, 24, 12, 6, 3, 1 ⟩ (30 est la première espèce qui n'est pas le double de l'espèce précédente). Autrement dit, on a le tableau partiel :

   i	8	7	6	5	4	3	2
   di-1	3	6	12	24	30	60	120	240
   bi	2	5	11	23	?

   On cherche donc la petite bête dans les paiements (optimaux) qui contiennent l'espèce 24. Le contre-exemple vient dès le premier essai sérieux : 24 + 24.
   
   Avant de critiquer les britanniques et la base 12, remarquons qu'un problème similaire se pose si on ajoute un billet de 25 au système européen.