Количество, сумма, произведение делителей
Ошибка.
Попробуйте повторить позже
В тюрьме находятся 100 камер, пронумерованных числами от 1 до 100. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.
Подсказка 1
Подумаем, что с точки зрения теории чисел значит, что в момент k-го прохода (когда тюремщик проходится по камерам k-й раз и поворачивает замок в каждой k-й) повернулся замок в камере с номером n? Например, в третий раз он меняет состояние 3, 6,… 99 двери, что нам это напоминает?
Подсказка 2
Верно, такое действие означает, что n является кратным числа k, или же k — делитель n. Если в конце дверь оказалась открыта, значит, замок поворачивали нечетное количество раз. Что мы получим, сопоставив эти две мысли?
Подсказка 3
Таким образом, отрыты в конце те двери, у номеров которых нечетное число делителей. У любого числа все (или почти все) делители можно поделить на пары. Подумаем, когда же реализуется это “почти”, которое нас и приведет к решению задачи!
Назовем проходом с номером 
изменение состояний каждой 
-той камеры. Рассмотрим камеру с номером 
. Найдем сколько раз она
меня свое состояние с открытой на закрытую или наоборот. Пусть камера поменяла свое состояние на проходе с номером 
, тогда номер
камеры 
делится на 
. Таким образом, камера с номером 
меняла свое состояние столько раз, сколько различных делителей она
имеет.
Заметим, что после каждой нечетной смены состояний камеры она является открытой, а после каждой четной — закрытой. Таким
образом, в конце камера будет открыта тогда и только тогда, когда количество смен ее состояний, то есть количество делителей ее номера
является нечетным числом. Докажем, что число имеет нечетное количество делитей тогда и только тогда, когда является полным
квадратом. Как известно, число делителей числа 
равно 
— нечетное число, но тогда
число 
нечетно при всех 
, следовательно, каждое из чисел 
при всех 
делится на 2, то
есть степень вхождения любого простого числа в 
четна, а значит 
является квадратом. Аналогично, если 
суть
полный квадрат, то числа 
при всех 
делятся на 2, следовательно, 
—
нечетно.
Наконец, открытыми будут те и только те камеры, номера которых есть полный квадарт, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
