OliForum Matematico

Definito $j=(n,k); r=\frac{n}{j}$, dimostriamo che le configurazioni sono $2^{n-j+1}$

Prima di tutto sicuramente il numero di configurazioni è $\le\ 2^{n-j+1}$, per questa simpatica invariante:
numeriamo le lampadine da $1$ a $j$. Le lampadine con il numero $i_1$ accese hanno la stessa parità delle lampadine accese con il numero $i_2$.

Dimostriamo ora che possiamo ottenere tutte quelle configurazioni, con questi algoritmi:
1) posso cambiare di stato $j$ lampadine consecutive: se accendo infatti $k$ lampadine "consecutivamente" prima o poi otterrò che rimarranno accese $j$ lampadine consecutive (per il fatto che l'ordine additivo di $k$ ha come minimo il gcd)
2) posso cambiare di stato 2 qualsiasi lampadine con lo stesso numero $i$ CONSECUTIVE: grazie a 1) questo segue se iteriamo il processo anche per le lampadine da $i$ a $i+j-1$ e da $i+1$ a $i+j$: avrò alla fine un cambio di $i$ e di $i+j$
3) posso cambiare di stato 2 qualsiasi lampadine con lo stesso numero $i$: reitero 2) ogni volta spostandomi di $j$
E ora ho vinto, perché se le lampadine sono pari segue subito, se invece sono dispari mi basta invertire una volta (ma proprio brutalmente e viene) $j$ lampadine consecutive e poi aggiustare.