Question

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

Answer 1

4048 обходов. Ну у меня так получилось.

Answer 2

Для каждой камеры $i$, мы можем посчитать, сколько раз она была открыта. Это равно количеству делителей числа $i$. Например, для камеры 12 это будут обходы номер 1, 2, 3, 4, 6 и 12, то есть 6 раз.

Чтобы определить, была ли камера закрыта или открыта после всех обходов, нужно посмотреть на количество обходов, в которых она была открыта. Если это количество четное, то камера закрыта, а если нечетное, то открыта.

Таким образом, нам нужно вычислить количество камер с нечетным количеством делителей. Обратимся к теории чисел: у числа $n$ количество делителей равно количеству его простых множителей плюс единица, все это умноженное друг на друга. Например, у числа 12 есть три простых множителя (2, 3 и 5), поэтому оно имеет $(1+1)(1+1)(1+1) = 2 \cdot 2 \cdot 2 = 8$ делителей.

Теперь посчитаем количество камер с нечетным количеством делителей. Число имеет нечетное количество делителей только если оно — квадрат некоторого простого числа. Таким образом, нам нужно найти количество квадратов простых чисел, которые меньше или равны 2014.

Наибольшее простое число, меньшее 2014, равно 1999, и его квадрат равен 3 996 001, что больше 2014. Следовательно, нам нужно найти количество простых чисел, меньших или равных 44. Это можно сделать, перебрав все простые числа от 2 до 43 и вычислив их квадраты.

Получается, что всего есть 9 камер с нечетным количеством делителей, то есть открытыми остаются 9 камер.