Question

В тюрьме 500 камер, пронумерованных натуральными числами от 1 до 500. Безумный надзиратель за ночь совершает 500 обходов следующим образом: в первый обход он открывает все камеры, во второй — закрывает каждую вторую, в третий — поворачивает ключ в замке каждой третьей камеры, открывая её, если она была закрыта и закрывая, если была открыта. Действуя аналогично, он заканчивает 500 обходом, поворачивая ключ в каждой 500 камере. Сколько камер осталось открытыми после завершения им всех обходов?

Answer 1

Камера останется открытой, если ключ в ее замке повернули нечетное число раз. Поскольку на шаге номер i надзиратель поворачивает ключ в замке тех камер, номер которых делится на i, это равносильно тому, что у номера этой камеры нечетное количество натуральных делителей.
Далее, если число N делится на А, то N также делится и на (N/A), то есть делители любого натурального числа образуют пары, и у большинства чисел четное число делителей. Единственный случай, когда количество делителей нечетно - это когда в одной из пар два делителя равны, и должны считаться один раз. А раз A=N/A, то N является полным квадратом.
Поэтому открытыми останутся камеры с номерами 1, 4, 9, 16... 484, всего 22 камеры