ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116217
Тема:    [ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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

Рис. а

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

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

Рис. б

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

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

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


Ответ

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .