Решение. Шкафчики (#159)
Шкаф открыт, если его состояние меняли нечётное число раз. Заметим, что шкаф с номером n меняет состояение столько раз, сколько делителей у числа n. Таким образом, шкаф открыт, если его номер имеет нечётное количество делителей.
Посчитаем количество делитей n в терминах его разложения на простые множители.
Пусть n = p₁ⁱ¹ p₂ⁱ² … pₙⁱⁿ, где pₖ – простые числа, iₖ ≥ 0, k = 1..n
Из формулы выше следует, что количество делителей d(n) числа n равно:
Очевидно, что d(n) нечётно тогда и только тогда, когда iₖ чётно для каждого k. Другими словами, d(n) нечётно тогда и только тогда, когда n – полный квадрат.
Применительно к задаче, 1 ≤ n ≤ 100, поэтому имеется 10 номеров, являющихся полными квадратами: 1, 4, …, 81, 100.
В итоге останется 10 открытых шкафов после сотого обхода.