dandole al interruptor

El fin de semana pasado prometi a varios amigos que de esta semana no pasaba que publicara un nuevo problemilla de programancia101, porque ya veo que a la que uno se descuida, le sale competencia! Mirad si no a mi camarada Kartones, que se esta animando a publicar problemas en su blog.


Como me ha gustado la idea, se me ha ocurrido dejar otro problema que podeis resolver con un algoritmo sencillito, o bien usando «trucos»:



Imaginemos que tenemos una fila con 64 interruptores, cada uno de los cuales conectamos a una bombilla. Supongamos que partimos de una posicion en la que todas las bombillas estan apagadas y procedemos a pasar por todas ellas y cambiar el estado del interruptor. Una vez hecho esto, volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para las bombillas en posiciones que sean multiplos de 2 (la segunda, la cuarta, la sexta, …) De nuevo volvemos al principio y volvemos a cambiar la posicion del interruptor pero solo para posiciones multiplos de 3 (la tercera, la sexta, la novena, …) Y seguimos repitiendo el procedimiento para posiciones multiplos de 4, de 5, de 6… asi hasta los multiplos de 64.


Que algoritmo usarias para saber cuales de las bombillas permaneceran encendidas al terminar? Y, si te apetece complicarte un poco mas: Como podriamos hacerlo utilizando la menor cantidad de memoria posible?