Задача про 1000 лампочек: сколько останется гореть?

Задача на выходные

Серые клеточки сами себя не разомнут. Давайте попробуем такую задачу:

Задача про лампочки: условие

У вас есть цепочка из 1000 пронумерованных лампочек.

В первый проход вы включаете все лампочки.
Во второй – выключаете каждую вторую (чётные номера).
В третий – переключаете каждую третью (если горела, выключаете; если была выключена, включаете).
В четвёртый – переключаете каждую четвёртую.
…
Этот процесс продолжается 1000 раз, пока на последнем проходе вы не переключите только 1000-ю лампочку.

Сколько лампочек останется гореть?

Решение задачи про лампочки: делители

Каждую лампочку мы переключаем столько раз, сколько у неё делителей (например, лампочку #12 трогаем 6 раз – 1, 2, 3, 4, 6, 12).

Ключевая идея: почти у всех чисел количество делителей чётное (каждый делитель имеет пару). Это значит, что все такие лампочки в конечном итоге будут выключены.

Почему горят именно квадраты

Но есть исключение – числа, у которых количество делителей нечётное. А это возможно только у совершенных квадратов! Например:

• 16 делится на 1, 2, 4, 8, 16, и 4 здесь без пары.

Ответ: сколько лампочек останется гореть

Ответ: Лампочки, оставшиеся гореть, соответствуют совершенным квадратам от 1 до 1000.

Считаем:
1², 2², 3², …, 31² = 31 таких числа.

Итог: 31 лампочка останется включённой!