Llevo dos días dándole vueltas a este problema y no he encontrado ninguna forma eficaz de resolverlo.
En un experimento realizado con 150 personas se pidió a cada participante que recibiera como identificación uno de los números comprendidos entre el 1 y el 150. A continuación, se les llevó a una sala donde había 150 lámparas, cada una numerada del 1 al 150 y con su respectivo interruptor. Todas las lámparas estaban inicialmente encendidas. A continuación, se pidió que, empezando por el participante número 1, cada persona cambiara el estado de todas las lámparas cuyo número era un divisor del número recibido por el participante antes de entrar en la sala. ¿Cuántas bombillas estaban apagadas al final del experimento?
La respuesta correcta es $104$ . Veo que el $n$ -ésima bombilla estuviera apagada si el número de múltiplos de $n$ es impar. Usando la fuerza bruta, encontré que estos números son $2$ , $4$ , $6$ , $7$ , $10$ , $11$ , $13$ , $16$ y los de los rangos $[19, 21]$ , $[26, 30]$ , $[38, 50]$ , $[76, 150]$ . Luego sumé la cantidad de estos números y encontré la respuesta correcta.
Si en lugar de "divisor" fuera "múltiplo", sabría resolverlo fácilmente utilizando la propiedad de que sólo los cuadrados perfectos tienen un número impar de divisores. Pero este problema es diferente.
Mi pregunta :
¿Existe una forma más eficaz de resolver este problema?
