Sujet
C'est du gâteau
Une pâtisserie propose des boîtes de canelés bordelais de diverses contenances : des conditionnements par 6, par 9, par 12 et par 16 sont possibles.
- Peut-on acheter 10 canelés, 20 canelés, 30 canelés ?
- a. Établir la liste des quantités, inférieures à 30 , qu'on ne peut pas réaliser en achetant plusieurs boîtes.
b. Montrer que, s'il existe un entier \(n\) tel que tout achat de \(n, n+1, n+2, n+3, n+4, n+5\) canelés soit possible, alors il est possible d'acheter toute quantité de canelés supérieure ou égale à \(n\).
c. Déterminer le plus petit entier \(n\) réalisant la condition précédente.
- a. Pourrait-on commander 50 canelés si les conditionnements possibles étaient \(6,9,12\) et 15 ?
b. Y aurait-il dans ce cas un seuil au-delà duquel toute quantité soit réalisable ?
Un algorithme glouton mais peu performant
Pour conditionner une commande de \(n\) canelés, on peut appliquer un algorithme (qualifié de glouton) consistant à utiliser un maximum de boîtes de la plus grande taille, puis de placer ce qui reste dans des boîtes de taille immédiatement inférieure, etc.
4. a. Que donne cette méthode s'il s'agit de répartir 60 canelés dans des boîtes de \(16,12,9\) et 6 ?
b. Et pour répartir 75 canelés ?
c. Pourrait-on conditionner les 75 canelés en procédant autrement?
5. On s'autorise à présent des emballages individuels, mais on souhaite limiter le nombre de boîtes utilisées.
a. Combien de boîtes de \(12,8,6\) et 1 faudrait-il utiliser pour conditionner 41 canelés en utilisant l'algorithme glouton?
b. Le même total est-il réalisable avec moins de boîtes (évidemment, sans appliquer l'algorithme) ?
6. Quels conditionnements peut-on réaliser en utilisant une boîte de chaque sorte au maximum parmi 5 boîtes de capacités \(1,2,4,8,16\) ?
Aucun corrigé disponible pour cet exercice dans la source APMEP.