Давайте рассмотрим следующую задачу из раздела теории чисел.
Есть 100 гномов и 100 фонарей с кнопкой, у которого есть положения вкл. и выкл.
С наступление темноты каждый гном идёт и нажимает на кнопки фонаря, причем первый гном нажимает на каждую первую кнопку, второй - каждую вторую, третий - каждую третью и т.д.
Вопрос: "какие фонари будут гореть после того, как 100-ый гном нажмет на последнюю кнопку?"
Рассмотрим вариант, когда 10 гномов проходят 10 фонарей.
1 фонарь включит только 1 гном и больше никто не сможет нажать на кнопку.
Второй фонарь будет включен 1 гномом и выключен вторым. Не сложно понять: если номер фонаря простое число, то он будет включен первым и выключен гномом с порядковым номером, соответствующий данному фонарю, т.е. фонари 3,5,7 тоже будут выключены.
Рассмотрим остальные фонари, порядковые номера которых составное число.
4 фонарь будет включен 1 гномом, выключен вторым, и снова включен 4 гномом.
Фонари 6 и 8 будут выключены т.к на кнопку нажали 1,2,3,6 и 1,2,4,8 гномы соответственно.
Для 9 фонаря имеем 1,4,9.
Мы нашли 3 фонаря, которые будут включены, после обхода гномов. Заметим, что это квадраты натуральных чисел:1,2,3 соответственно.
Возникает предположение, что будут включены фонари, порядковые номера которых квадраты натуральных чисел.
Мы уже выяснили, что фонари с простым номерами 2,3,5,7и т.д будут выключены т.к. на их кнопку нажмут 1-ый и n-ый(номер фонаря) гном.
Всплывает теория делимости чисел: нужно найти такой фонарь количество делителей которого будет нечетным числом(вкл, выкл, вкл, выкл, вкл...)
Понятно, что номера фонарей, являющиеся квадратами натуральных чисел будут включены, потому что количество их делителей нечетное число(25={1,5,25})
Давайте докажем, что для всех остальных составных чисел, количество делителей чётное число: возьмем число n - составное, т.е имеющее как минимум 2 делителя отличных от 1 и n, пусть а и b делители n.
Если a и b простые, то у числа n - четное число делителей(1, a, b, n)
Если а и b составные, то их можно разложить на 2 делителя a1, a2 и b1, b2, где a1, a2, b1, b2 - простые(если нет, повторяем разложение), получим делители числа n: 1, a1*a2=a, a1*b1, a1*b2, a2*b1, a2*b2, b1*b2=b, n. Получили четное количество делителей. Причем, если a1=a2 или b1=b2, мы всë равно получим четное число делителей(подумайте почему).
Если а - простое, b - составное, тогда у числа b - 2 простых делителя b1, b2 (если нет продолжаем разложение). Получим следующие делители числа n: 1, a, b1, b2, a*b1, a*b2, b1*b2=b, n – четное число делителей. Получаем, что для любого составного числа, кроме квадратов, будем получать четное число делителей.
Задача решена (Ответ: 1,4,9,16,25,36,49,64,81)