Quentin L. Meunier

Problème 1009

Un papetier possède des chaines de trombones attachés à la suite les uns des autres.

Lors d'une "manipulation", il détache un trombone à ses deux extrémités et obtient ce trombone ainsi que deux nouvelles chaines plus petites.

1A. À partir d'une chaine de 63 trombones, combien de manipulations devra-t-il effectuer au minimum pour être capable de fournir, sans nouvelle manipulation, n'importe quel nombre de trombones entre 1 et 63 ?
1B. Quelle est la plus longue chaine initiale qui permet, en 8 manipulations, de fournir n'importe quel nombre de trombones compris entre 1 et la longueur de la chaine ?

Le papetier reçoit une chaine formée de 200 trombones de trois couleurs différentes : le premier est rouge, le deuxième bleu, le troisième vert. Il remarque qu'en enlevant un trombone sur quatre (à partir du quatrième), la suite des 50 trombones enlevés est identique à la suite des 50 premiers trombones de la chaine initiale et la suite des 150 restants est identique à celle des 150 premiers trombones de la chaine initiale.

2A, 2B, 2C. Quel est le nombre de trombones rouges (2A), bleus (2B) et verts (2C) de la chaine ?

Pour la question 1B, le programme suivant permet de vérifier qu'un découpage donné permet bien d'atteindre tous les nombres de trombones. Une exploration de tous les découpages obtenus par les différentes manipulations possibles est aussi réalisable mais explose très vite en nombre de configurations.

Pour la question 2, le programme suivant implémente les règles et les appelle de manière itérative jusqu'à ce que toutes les couleurs de la chaine soient connues.

1A. À partir de 63 trombones, on obtient tous les nombres de 1 à 63 avec au minimum 3 manipulations.
1B. Avec 8 manipulations, la plus longue chaine possible est de 4 607 trombones.
2A, 2B, 2C : Il y a dans la chaîne 120 trombones rouges, 46 bleus et 34 verts.