080 Mille et une lampes

 

Vous trouverez ci-contre la fractale induite par ce problème qui illustre les solutions proposées. La première ligne correspond à la première seconde, et ainsi de suite. Un point noir est une lampe allumée, un point blanc une lampe éteinte.

 

Réponse 1 :

Je note e(p; n) l'état (1 = allumé; 0 = éteint) de la lampe de rang n (n >= 0) après p secondes (p >= 0) et k le rang de la lampe située à l'extrême droite (il y a donc k+1 lampes).
L'énoncé se traduit donc en :
- pour tout n > 0, e(0; n) = 0
- pour tout p >= 0, e(p; 0) = 1
- e(p; n) = e(p-1; n) si e(p-1; n-1) = 0
- e(p; n) = 1-e(p-1; n) si e(p-1; n-1) = 1
- condition d'arrêt lorsque e(p0; k) = 1 où p0 = min{p \ e(p; k) = 1}
Les deux relations donnant e(p; n) peuvent s'écrire sous une forme permettant de calculer de proche en proche les e(p;n) :
e(p; n) = e(p-1; n) + e(p-1; n-1) (modulo 2).
Cette relation est analogue à celle permettant de construire le triangle de Pascal. En fait il s'agit du triangle de Pascal modulo 2, dont la structure est isomorphe à la forme discrète du triangle de Sierpinski.
Quelques propriétés (évidentes mais qui demanderaient à être soigneusement démontrées...) :
- p0 = k
- nombre de lampes allumées pour un ensemble de k+1 lampes : a(k) = somme(n = 0; k; e(k; n)).
- a(k) = 2*a(k-2^r) où r = max {s \ 2^s <= k < 2^(s+1)} (des motifs se "répètent"...)
Cette dernière relation fournit un moyen pratique de calculer les a(k) :
a(k) = 2^x où x est le nombre de "1" (somme des poids forts) dans la décomposition en base 2 de k

Application :
1001 :
1000 = 512 + 256 + 128 + 64 + 32 + 8 => a(1000) = 2^6 = 64

12486 :
12485 = 8192 + 4096 + 128 + 64 + 4 + 1 => a(12485) = 2^6 = 64

2097153 :
2097152 = 2^21 => a(2097152) = 2^1 = 2

Réponse 2 :

N désigne le nombre de lampes. Il faut commencer par découper N en une somme de puissances de 2 (les puissances les plus élevées possibles). Désignons par K le nombre de termes ainsi obtenus dans la décomposition, et par R le plus petit de ceux-ci. Le nombre de lampes allumées lorsque s'allume la lampe n° N est alors donné par le calcul: 2^(K-1).R
Pour les nombres proposés, cela donne:
12486 = 2^13 + 2^12 + 2^7 + 2^6 + 2^2 + 2 ---> K = 6 et R = 2 ---> 2^(6-1).2 = 64 lampes allumées
2097153 = 2^21 + 2^0 ---> K = 2 et R = 1 ---> 2^1.1 = 2 lampes allumées
La méthode est basée sur les observations suivantes:
1 - à chaque seconde S qui est une puissance de 2, les lampes allumées sont exactement les S premières
2 - à partir de l'instant S+1, le processus d'évolution des allumages et des extinctions des lampes reproduit exactement - mais en double - le processus
qui s'est déroulé entre les instants 1 et S, et ce jusqu'à l'instant 2S (qui est la puissance de 2 suivante) (en effet les groupes de lampes 1 à S et S+1 à 2S se comportent tous deux, entre les instants S+1 et 2S, comme le groupe de lampes 1 à S entre les instants 1 et S).

 

Réponse 3 :

On s'aperçoit que le résultat est toujours une puissance de 2 :
1 lampe : 1
2 lampes : 2
3 lampes : 2
4 lampes : 4
5 lampes : 2
6 lampes : 4

La question devient : quelle puissance « P » associer à un nombre « N » de lampes ?
Définissons la fonction f :
P = f(N-1)
f(0) = 0
f(1) = 1
f(2n) = f(n) (n étant un entier naturel)
f(2n+1) = f(n) + 1

Ainsi on vérifie aisément pour 1001 lampes :
P = f(1001-1) = f(125) = f(62)+1 = f(31)+1 = f(15) +2 = f(7) + 3 = f(3) + 4 = f(1) + 5 = 6
2^6 = 64

pour 12486 lampes :
P = f(12486-1) = f(6242) + 1 = f(3121) + 1 = f(1560) + 2 = f(195) + 2 = f(97) + 3 = f(48) +4 = f(3) +4 = f(1) + 5 = 6
Ici aussi 64 lampes.

pour 2097153 lampes :
P = f(2097153-1) = f(1) = 1
2 lampes.

Cliquez pour agrandir