|
 
Problème proposé par Michel Boulant
On fixe un entier n ≥ 1. On part d’un mot binaire de longueur n, noté ligne 0, dont le bit de rang 0 (le bit tout à droite) vaut 1. Le bit le plus à gauche peut, lui, valoir 0 ou 1.
Les rangs sont numérotés de droite à gauche : 0, 1, 2, …, n − 1. On note a_{k,r} le bit de la ligne k et de rang r.
À partir de la ligne 0, on construit successivement les lignes 1, 2, 3, … selon la règle suivante :
• le bit de rang 0 reste toujours égal à 1 ;
• pour tout rang r tel que 1 ≤ r ≤ n − 1, on pose
a_{k,r} = a_{k−1,r} + a_{k−1,r−1} (mod 2).
• Autrement dit, on additionne les deux bits indiqués sans retenue : 0 + 0 = 0, 1 + 1 = 0, 0 + 1=1, 1 + 0 =1.
Comme il n’existe que 2ⁿ⁻¹ mots binaires de longueur n dont le dernier bit vaut 1, la suite obtenue finit nécessairement par devenir périodique.
Q1 Déterminer la longueur de cette période en fonction de n.
Q2 Cette période dépend-elle du mot initial choisi ?
Solution
|
