Задача 79482
|
|
 |
Условие
Назовём "сложностью" данного числа наименьшую длину числовой последовательности (если такая найдётся), которая начинается с нуля и заканчивается этим числом, причём каждый следующий член последовательности либо равен половине предыдущего, либо в сумме с предыдущим составляет 1. Среди всех чисел вида m/250, где m = 1, 3, 5,..., 250 − 1, найти число с наибольшей "сложностью".Решение
Ответ: максимальную "сложность" имеет число ((251 + 1)/3)/250.Докажем, что среди чисел вида m/2k, где m = 1, 3, 5,..., 2k − 1, максимальную "сложность" (равную 2k) имеет число, у которого m = m0(k) = (2k + 1 + (−1)k)/3. Мы будем доказывать это утверждение индукцией по k.
База индукции. k = 1. Очевидно, "сложность" числа 1/2 равна двум.
Шаг индукции. Допустим, что наше утверждение доказано для k. Докажем его для k + 1. Заметим сначала, что сложность любого числа вида m/2k + 1 не превосходит 2(k + 1). Действительно, если m < 2k, то это число может быть получено делением пополам числа m/2k (всего не более 2k + 1 < 2(k + 1) операций), а если m > 2k, то это число может быть получено следующим образом: сначала получим число (2k+1 − m)/2k, затем разделим его пополам, затем вычтем из единицы (всего не более 2k + 1 + 1 = 2(k + 1) операций). Докажем теперь, что "сложность" числа m0(k + 1)/2(k + 1) равна 2k + 2. Действительно, так как m0(k + 1)/2(k + 1) > 1/2, то последняя операция при получении этого числа — вычитание из единицы, а предпоследняя — деление пополам. Но такой последовательностью операций оно получается именно из числа m0(k)/2k. Следовательно, "сложность" числа m0(k + 1)/2k + 1 на два больше "сложности" числа m0(k)/2k, т. е. равна 2k + 2, ч. т. д.
