Zig dispose de boîtes de macarons. À chaque tour, il choisit un nombre quelconque de boîtes non vides et retire le même nombre entier q > 0 de macarons de chacune, sans jamais retirer plus que le contenu d’une boîte choisie.
Q₁. Avec n boîtes contenant 1, 2, …, n macarons, déterminer le nombre minimal m(n) de tours nécessaire pour vider toutes les boîtes. Calculer m(13) et m(31).

Q₂. On considère les contenus de quatre séries de sept boites chacune :
      n°1 : 8, 10, 12, 15, 22, 25, 33 ;
      n° 2 : 2, 5, 19, 27, 28, 35, 40 ;
      n° 3 : 3, 17, 25, 26, 35, 56, 59 ;
      n° 4 : 4, 12, 17, 18, 20, 31, 37.
Zig choisit l'une des quatre méthodes suivantes et l'applique à chaque tour jusqu'à ce que toutes les boîtes soient vides.
Méthode 1 : manger le plus de macarons possibles. On retranche q de toutes les boîtes qui en contiennent au moins q, où q maximise le produit de q par le nombre de boîtes concernées ; en cas d'égalité, on prend le plus grand q.
Méthode 2 : exécuter un algorithme binaire. q est la plus grande puissance de 2 qui ne dépasse pas le contenu maximal ; on la retranche de toutes les boîtes qui en contiennent au moins q.
Méthode 3 : réaliser une bissection des contenus. q est la médiane supérieure des contenus distincts encore positifs (la valeur de rang ⌊k/2⌋ + 1 parmi k valeurs rangées par ordre croissant) ; on la retranche de toutes les boîtes qui en contiennent au moins q.
Méthode 4 : réduire le plus possible le nombre de contenus distincts, selon les deux règles suivantes.
a) Si les contenus positifs sont tous différents, on choisit q et un sous-ensemble de boîtes contenant chacune au moins q, de façon à rendre minimal le nombre de contenus positifs distincts après le tour ; en cas d'égalité, on maximise le nombre total de macarons mangés, puis on prend le plus grand q.
b) Si plusieurs boîtes ont le même contenu, on vide le groupe de boîtes de même contenu le plus nombreux ; en cas d'égalité, on maximise le nombre de macarons qui se trouvent dans les boîtes vidées, c'est-à-dire qu'on retient le plus grand contenu commun. Ce contenu est retranché de toutes les boîtes qui en contiennent au moins autant.
Exemple : série 7, 12, 19, 25, 29, 37, 42 ; cinq tours, avec q = 12, 25, 7, 10, 5.
Prouver que, pour chaque série, une méthode exige strictement moins de tours que chacune des trois autres.

Q₃. Construire quatre séries de sept entiers distincts, tous ≤ 16, telles que sur la série n° i la méthode n° i exige strictement moins de tours que les trois autres.

 Soumettre votre solution