| E6938. La multiplication est gratuite |
|
| E6. Autres casse-tête |
|
Problème proposé par Stan Wagon
Soit n un entier strictement positif fixé à l’avance. A partir de l’entier 1, il s’agit d’obtenir n de la manière suivante : on peut ajouter ou multiplier deux termes précédemment calculés, pas nécessairement distincts, jusqu’à l’obtention de n. Chaque addition coûte 1 € mais la multiplication est gratuite. On désigne par c(n) le coût minimal qui permet d’obtenir n. Par exemple n = 1729 peut être obtenu avec un coût minimal de 3 € selon les opérations suivantes qui contiennent 3 additions et 4 multiplications : 1 + 1 = 2, 2 + 1 = 3, 2*3 = 6, 2*6 = 12, 12*12 = 144, 12*144 = 1728, 1728 + 1 = 1729. Q1 Déterminer le plus petit n tel que c(n) = 3 € [*] Q2 Déterminer le plus petit n tel que c(n) = 4 € [**] Q3 Calculer c(2023) [*] Q4 Pour les plus courageux : - déterminer avec l’aide d’un automate le plus petit n tel que c(n) = 5 € [***] puis le plus petit n tel que c(n) = 6 €. - prouver que quel que soit le coût k en € consenti, il y a un entier n qui ne peut pas être atteint avec un coût ≤ k. [*****] Solution
|
