ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 116217
УсловиеНа доске написаны три натуральных числа, не превосходящих 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. Используя дроби и
, уже несложно подобрать последовательность
операций, приводящую к умножению на целое число:
Ответда, существуют.Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|