Chaînes d additions - Lycée Fragonard (L Isle-Adam)

Établissement
Lycée Fragonard (L Isle-Adam)
Année
2007-2008
Résumé
On se donne un entier n. Une chaîne d’additions est une suite d’entiers dont le premier terme est 1, le dernier terme est n et chaque terme est la somme de deux termes obtenus précédemment. Quelques questions : pour un entier n, quelle est la longueur d’une chaîne la plus courte ? la meilleure chaîne ? Est-ce toujours possible ? Et si on s’autorise également des soustractions ? Une utilité de telles chaînes : obtenir une puissance d’un nombre en effectuant le moins d’opérations possible.