Интересная олимпиадная задача по математике В школе есть 100 шкафчиков и 100 привидений. Все закрыты. Вылетает привидение 1 и открывает все шкафчики, затем вылетает привидение 2 и закрывает все шкафчики с четным номером. Далее вылетает привидение 3 и меняет положение шкафчиков (т.е. открывает или закрывает), у которых номер делится нацело на 3. После вылетает привидение 4 и меняет положение всех шкафчиков, у которых номер кратен 4. И так далее. Привидение 100, получается, поменяет положение только шкафчика 100. Сколько шкафчиков в конце будет закрыто?

Предыдущий
вопрос Следующий
вопрос

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

Например, для шкафчика номер 12: его номер имеет делители 1, 2, 3, 4, 6, 12, то есть он будет "затронут" привидениями с номерами 1, 2, 3, 4 и 6, то есть "влияние" для него равно 5, то есть шкафчик номер 12 будет закрыт.

Теперь мы можем посчитать, сколько шкафчиков будет закрыто в конце, рассматривая каждый шкафчик по очереди:

1 - открыт (имеет одного делителя - 1
2 - закрыт (2 делителя - 1 и 2
3 - открыт (2 делителя - 1 и 3
4 - открыт (3 делителя - 1, 2, 4
5 - открыт (2 делителя - 1 и 5
6 - закрыт (4 делителя - 1, 2, 3, 6
7 - открыт (2 делителя - 1 и 7
8 - открыт (4 делителя - 1, 2, 4, 8
9 - закрыт (3 делителя - 1, 3, 9
..
и так далее, до шкафчика номер 100.

Подсчитав количество закрытых шкафчиков для каждого номера, получим, что всего в конце будет закрыто 10 шкафчиков (поскольку у каждого числа n делителей не больше, чем sqrt(n), и, соответственно, не более 9 для чисел от 1 до 100, а также само число делителем, если не считать его самого, то всего не более 10).