Marco e le lampadine

[Fbuonarroti]

Marco ha davanti a se una fila di $ n $ lampadine, numerate da $ 1 $ a $ n $ partendo da sinistra, tutte collegate rispettivamente ad $ n $ interruttori posizionati sotto ogni lampadina, numerati anch'essi come le lampadine.
Marco preme ogni interruttore tante volte quante la posizione del l'interruttore, il primo $ 1 $ volta, il secondo $ 2 $ e così via.
Sapendo che ogni volta che una lampadina si spegne quella esattamente alla sua destra cambia stato ( se esiste) e che tutte le lampadine partono da spente dire quante sono le lampadine accesse alla fine al variare di $ n $

[RiccardoKelso]

Testo nascosto:

Le lampadine con etichetta numero in forma $i=4k$ per qualche $k\in\mathbb{N}$ vengono spente un numero pari di volte, quindi le $4k+1$ partono spente. Essendo $4k+1$ dispari, alla fine queste saranno accese; inoltre notiamo che vengono anch'esse spente un numero pari di volte, di conseguenza le $4k+2$ partono spente. Essendo queste ultime etichette pari, saranno alla fine spente, dopo essere state spente un numero dispari di volte. Le $4k+3$ partiranno quindi da accese, ma essendo dispari finiranno per essere spente, dopo essere state spente anche loro un numero pari di volte (dato che partivano accese). Infine le $4k$ partiranno allora da spente ed essendo pari lo saranno anche alla fine. In conclusione, le uniche accese sono le $4k+1$, quindi in funzione di $n$ si ha $N_a=\lceil \frac{n}{4}\rceil$. Per dare una parvenza di formalità alle affermazioni pari/dispari penso si possa usare la ripetizione della sequenza ACC-SPENTA-ACC-SPENTA, che lascia inalterata la situazione.

[Fbuonarroti]

Il problema è che quando la $ 4k $ ha finito è vero che la $ 4k+1 $ parte spenta, ma la $ 4k+2 $ si è accesa, e quindi quando la $ 4k+1 $ ha finito ha si è spenta 2 volte, il che significa che la $ 4k+2 $ e la $ 4k+3 $ partono accese e così via...

[RiccardoKelso]

Scusa, ogni volta che una lampadina si spegne quali e quante cambiano stato?

[Fbuonarroti]

Dopo che una lampadina $ x $ si spegne $ x+1 $ cambia stato, questo però significa che se la $ x+1 $ passa da accesa a spenta allora la $ x+2 $ cambia anch'essa stato e quindi se era spenta si accende, quindi non è detto che agendo su una lampadina si influenzi solo quella alla sua destra, perché spegnedo quest'ultima si va a modificare anche quella ancora successiva e così via

[RiccardoKelso]

Ovviamente svista mia, scusami. Allora, se ho capito bene, tutto diventa

Testo nascosto:

quanti uni ci sono nelle prime n cifre da destra di $\sum_{i=1}^{n}i2^{i-1}$ scritto in binario? Poi provo.

editino

Testo nascosto:

Tuttavia si dimostra facilmente per induzione che $\sum_{i=1}^{n}i2^{i-1}=(n-1)2^n+1$, da cui si dovrebbe poter desumere che l'unica accesa è la prima (?)

[Fbuonarroti]

L'idea è giusta, manca solo la dimostrazione,
O la lasci come esercizio per il lettore?

[RiccardoKelso]

Ti riferisci ai passi base/induttivo? Li metto qui, mentre per quanto riguarda la formalizzazione della "traslazione" di problema lascio davvero tutto al volenteroso lettore

Testo nascosto:

passino basuccio: $\sum_{i=1}^{2}i2^{i-1}=1\cdot 2^0+2\cdot 2^1=5=1\cdot 2^2+1$
passino induttivuccio: $\sum_{i=1}^{n+1}i2^{i-1}=(n+1)2^n+\sum_{i=1}^{n}i2^{i-1}=(n+1)2^n+(n-1)2^n+1=(n-1+n+1)2^n+1=2n2^n+1=n2^{n+1}+1$