Задача 116217

Тема:    [ Примеры и контрпримеры. Конструкции ]

Сложность: 4- Классы: 8,9,10

Условие

Авторы: Клепцын В.А., Голенищева-Кутузова Т.И.

На доске написаны три натуральных числа, не превосходящих 40. За один ход можно увеличить любое из написанных чисел на число процентов, равное одному из двух оставшихся чисел, если в результате получится целое число. Существуют ли такие исходные числа, что за несколько ходов одно из чисел на доске можно сделать больше 2011?

Решение

Приведём два примера возможных изначальных чисел и последовательностей преобразований (разумеется, для полного решения задачи достаточно привести всего один пример).

Рис. а

На рисунке а мы получили число 100. Заметим, что при увеличении на 100% число удваивается. Следовательно, увеличив, например, число 25 на 100% семь раз, мы получим число 25·2⁷ = 3200 > 2011.

На рисунке б за приведённые три операции число 16 увеличилось в два раза. Продолжая увеличивать третье число таким же образом (два раза на 25%, затем один раз на 28%), мы можем получить сколь угодно большое число.

Рис. б

Комментарий. Покажем (хотя это и не требуется для решения), из каких соображений можно придумать второй из этих примеров. Заметим для начала, что увеличить число на n% — всё равно что умножить его на . Поэтому результат увеличения числа x на n% будет целым, если и только если произведение x(100 + n) будет делиться на 100.

Допустим, что мы будем всё время увеличивать только одно из чисел. При каждом таком увеличении мы умножаем число на дробь со знаменателем 100; поэтому нам нужно позаботиться о том, чтобы итоговое число продолжало делиться на достаточно большие степени двойки и пятёрки. Значит, на достаточно большие степени двойки и пятёрки должны делиться числители дробей, на которые мы умножаем. Поскольку каждая отдельная дробь (соответствующая значениям n ≤ 40) целой быть не может, естественно возникает идея "разделения обязанностей": у части дробей числители будут делиться на большую степень двойки (но на недостаточную — пятёрки), а у части — наоборот.

На большую степень двойки делится, например, число 128 = 2⁷, а на большую степень пятёрки — число 125 = 5³. Используя дроби и , уже несложно подобрать последовательность операций, приводящую к умножению на целое число:
Осталось выбрать начальное значение третьего числа таким, чтобы первые два шага не привели к дробным числам, и мы можем повторять увеличения на 25%, 25% и 28% циклически.

Ответ

да, существуют.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2011
Номер	74
класс
Класс	9
задача
Номер	4