Условие

В коридоре 100 лампочек, все выключены. Затем приходят 100 человек:

1-й щёлкает каждую 1-ю лампу (то есть все).
2-й — каждую 2-ю (2, 4, 6, …).
3-й — каждую 3-ю (3, 6, 9, …).
…
100-й — только 100-ю.

Какие лампочки в итоге останутся включёнными?

Решение

Подход

Лампа k переключается человеком i, если i делит k. Итоговое состояние = «включена», если число делителей k нечётно (изначально все выключены).

Когда число делителей нечётно

Делители обычно идут парами: (d, k/d). Например, 12 = 1·12 = 2·6 = 3·4 — пары (1,12), (2,6), (3,4) — всего 6 делителей (чётное).

Пара (d, k/d) «склеивается» только когда d = k/d, то есть d² = k — k полный квадрат.

`k`	Делители	Кол-во
12	1, 2, 3, 4, 6, 12	6 (чётное)
16	1, 2, 4, 8, 16	5 (нечётное) — квадрат
25	1, 5, 25	3 (нечётное) — квадрат

Ответ

Включёнными останутся лампы с номерами полных квадратов ≤ 100:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100

— 10 ламп.

Проверка на лампе 16

Делители 16: 1, 2, 4, 8, 16. Человек 1 → включил, 2 → выключил, 4 → включил, 8 → выключил, 16 → включил. Итого: включена. ✓

Проверка на лампе 12

Делители: 1, 2, 3, 4, 6, 12. Шесть переключений → выключена. ✓

Код

state = [False] * 101
for i in range(1, 101):
    for k in range(i, 101, i):
        state[k] = not state[k]
on = [k for k in range(1, 101) if state[k]]
print(on)
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Подводные камни

«Ответ — простые числа» — нет, у простого числа ровно 2 делителя (1 и само), нечётное число делителей только у квадратов.
Запутаться в чётности — изначально все выключены, нужно нечётное переключение, чтобы стать включённой. Если бы изначально были включены, ответ был бы «не-квадраты».
Считать вручную делители — медленно. Используйте свойство квадратов.

Эталонный ответ

Лампы с номерами полных квадратов: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 — 10 ламп. Причина: число делителей нечётно только у квадратов (один из делителей — квадратный корень — не имеет пары).

Логика — 100 лампочек и 100 человек: какие останутся включёнными