
- Avancé
- Suites et motifs
- Algorithmique et procédures
- Logique et déduction
- Logique
- Combinatoire et jeux
Énoncé

Francis est face à une grande rangée de mille et une lampes. Initialement, seule la lampe située complètement à gauche est allumée.
Ensuite, toutes les secondes, chaque lampe change d’état si, et seulement si, celle située à sa gauche était allumée une seconde avant. La lampe située le plus à gauche reste allumée tout le temps.
Le processus s’arrête lorsque la lampe située à l’extrémité droite s’allume pour la première fois.
Q1Question 1 sur 1À faire
Combien de lampes sont alors allumées ?
Indice offert
Appelle « ligne $k$ » l’état de la rangée après $k-1$ secondes. Observe qu’en une seconde, l’évolution ne peut atteindre que la lampe voisine immédiatement à droite : combien de passages entre lampes faut-il donc avant que l’extrémité droite puisse être atteinte ?