100 лампочек

Есть 100 пронумерованных лампочек с выключателями. Сначала некто зажёг все лампочки. После этого он переключил состояние каждой второй лампочки (т.е. лампочек с номерами 2,4,6...), затем переключил состояние каждой третьей, каждой четвёртой и так далее. Остановился он только после того как переключил состояние сотой лампочки.

Сколько лампочек осталось гореть после всей процедуры?

Решение
Останутся гореть только лампочки, номера которых - полные квадраты, т.е. лампочки 1,4,9,16,...,100. Всего таких лампочек 10.

Доказательство.

Для того, чтобы лампочка осталась гореть после всей процедуры, она должна поменять своё состояние нечётное число раз. В самом деле, если изначально лампочка была выключена, то чётное число переключений оставляет её выключенной.

По условию задачи, на i-м шаге лампочка N поменяет своё состояние тогда и только тогда, когда N делится на i без остатка. Таким образом, лампочка N останется гореть тогда и только тогда, когда у числа N нечётное число делителей (включая единицу и само число).

Покажем, что нечётное число делителей может быть только у полных квадратов, и у каждого полного квадрата число делителей - нечётное.

Для N=1 утверждение тривиально.

Пусть натуральное число N, большее единицы, имеет нечётное число делителей. Это число может быть разложено на простые множители и представлено в виде N = d₁^p₁d₂^p₂...d_n^p_n, где d_i - простые числа, p_i - натуральные числа.

Всего у этого числа будет (p₁+1)(p₂+1)...(p_n+1) делителей. В самом деле, любой делитель числа можно получить, взяв делители d_i в произвольной степени от 0 до p_i. Если все степени положить равными 0, мы получим единицу, а если для всех степеней взять максимальное значение, мы получим само число N.

Число (p₁+1)(p₂+1)...(p_n+1) будет нечётным тогда и только тогда, когда все множители будут нечётными. Следовательно, все p_i должны быть чётными и представимы в виде p_i=2q_i, где q_i - натуральные числа.

Отсюда следует, что число N представимо в виде произведения N = d₁^2q₁d₂^2q₂...d_n^2q_n = (d₁^q₁d₂^q₂...d_n^q_n)², т.е. является полным квадратом.

Теперь покажем, что у полного квадрата нечётное число делителей. Пусть число N, большее единицы, является полным квадратом и представимо в виде N=K², где К - натуральное число. Поскольку К представимо в виде K = d₁^q₁d₂^q₂...d_n^q_n, то N можно записать как N = d₁^2q₁d₂^2q₂...d_n^2q_n, где q_i - натуральные числа.

Как мы выяснили выше, в этом случае число делителей числа N будет равно (2q₁+1)(2q₂+1)...(2q_n+1). Поскольку все сомножители нечётные, то и всё произведение будет, в свою очередь, нечётным.