Accendiamo lampadine!

[Drago]

Abbiamo $n$ lampadine in fila, una dopo l'altra, tutte spente, numerate da $1$ a $n$.
Con la prima mossa premiamo l'interruttore di quelle divisibili per $1$, con la seconda quelle divisibili per $2$, con la terza quelle divisibili per $3$, ecc... fino a fare $n$ mosse.
Quante e quali sono le lampadine accese alla fine?

[Lasker]

Se abbiamo una lampadina in posizione [tex]k[/tex] , alla fine delle operazioni sarà accesa se e solo se [tex]k[/tex] ha un numero dispari di divisori (perché ogni divisore passa una volta su [tex]k[/tex] e ne cambia lo stato)!
Ma se ha un numero dispari di divisori, deve essere per forza un quadrato perfetto, infatti il numero di divisori è il prodotto degli esponenti dei fattori primi ognuno aumentato di [tex]1[/tex], e visto che noi lo vogliamo dispari, tutti gli esponenti devono essere pari.
Ergo le lampadine che saranno accese alla fine sono i quadrati perfetti [tex]\leq\ n[/tex] e sono esattamente [tex]\lfloor \sqrt{n} \rfloor[/tex]

[Drago]

Perfect!