В новогоднюю ночь Дед Мороз и Баба Яга устроили математическое соревнование. Дед Мороз написал на волшебной доске число 8 (по количеству своих оленей), а затем каждую минуту дописывал новое число, которое получалось либо удвоением какого-то из уже написанных чисел, либо сложением двух любых имеющихся на доске чисел. а) Могло ли на доске появиться число 2028 ? б) Могла ли в какой-то момент сумма всех чисел на доске равняться 96 ? в) Через какое наименьшее время (в минутах) на доске могло появиться число 896 ?

1. Заметим, что все числа на доске делятся на 8 : - Стартовое число 8 кратно 8 . - Удвоение сохраняет кратность 8 . - Сумма двух чисел, кратных 8 , кратна 8 . По индукции все числа на доске кратны 8 . Но 2028 = 8 * 253 + 4 — не делится на 8 (остаток 4 ). Значит, число 2028 появиться не может. 2. Да, сумма всех чисел могла равняться 96 . Приведём пример последовательности: - Старт: 8 , сумма равна 8 . - 1 минута: дописываем 16 = 8 + 8 . Доска: 8; 16 , сумма равна 24 . - 2 минуты: дописываем 32 = 16 + 16 . Доска: 8; 16; 32 , сумма равна 56 . - 3 минуты: дописываем 40 = 8 + 32 . Доска: 8; 16; 32; 40 , сумма равна 96 . 3. Заметим, что 896 = 8 * 112 . Все числа на доске делятся на 8 , поэтому достаточно построить минимальную цепочку сложений-удвоений от 1 до 112 . Двоичная запись числа 112 : 1110000_2 . Длина минимальной аддитивной цепочки для n снизу ограничена величиной _2 n + (n) - 1 , где (n) — количество единиц в двоичной записи. Для 112 : _2 112 = 6, (112) = 3, нижняя оценка = 6 + 3 - 1 = 8. Достижимость показывает явная цепочка длины 8 : 8 2 * 8 16 2 * 16 32 2 * 32 64 2 * 64 128 2 * 128 256 128 + 256 384 2 * 384 768 128 + 768 896. Каждая стрелка соответствует одной минуте, итого 8 минут. Докажем, что за меньшее время достичь результата нельзя. После k шагов каждое число на доске равно 8 * a_k , где a_k принадлежит аддитивной цепочке длины k от 1 . По теореме о минимальной длине аддитивной цепочки число 112 невозможно достичь менее чем за 8 шагов. Ответ: а) нет б) да в) 8

A) net; B) da; V) 8