Олимпиада начальной школы 2x2, 5 класс, 2017 год, 2 тур
дата проведения: 29 января 2017
Задача 2.
Гриша написал на доске число 16 и каждую минуту прибавляет к числу на доске его наибольший простой делитель (стирает старое число и записывает новое). Начав с числа 16, он получит последовательность: 16 — 18 — 21 — 28 — 35 — … Может ли на доске в какой-нибудь момент времени оказаться число вида 1000…000?
Ответ на Задачу 2.
Ответ: Не может.
Решение:
Заметим, что при описанном алгоритме наибольший простой делитель текущего числа на доске может только увеличиваться, как видно, уже после 2 шага число на доске делится на 7, то есть в числе всегда будет простой делитель не меньший 7. Но в числе 1000….000 есть только простые делители 2 и 5, которые меньше 7. Противоречие.