Задача №17001

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

а) Могло ли на доске появиться число $2028\text{?}$
б) Могла ли в какой-то момент сумма всех чисел на доске равняться $96\text{?}$
в) Через какое наименьшее время (в минутах) на доске могло появиться число $896\text{?}$

1. Заметим, что все числа на доске делятся на $8\text{:}$

• Стартовое число $8$ кратно $8\text{.}$
• Удвоение сохраняет кратность $8\text{.}$
• Сумма двух чисел, кратных $8\text{,}$ кратна $8\text{.}$

По индукции все числа на доске кратны $8\text{.}$ Но $2028=8\cdot 253+4$ — не делится на $8$ (остаток $4$). Значит, число $2028$ появиться не может.

2. Да, сумма всех чисел могла равняться $96\text{.}$ Приведём пример последовательности:

• Старт: $\{8\}\text{,}$ сумма равна $8\text{.}$
• 1 минута: дописываем $16=8+8\text{.}$ Доска: $\{8;16\}\text{,}$ сумма равна $24\text{.}$
• 2 минуты: дописываем $32=16+16\text{.}$ Доска: $\{8;16;32\}\text{,}$ сумма равна $56\text{.}$
• 3 минуты: дописываем $40=8+32\text{.}$ Доска: $\{8;16;32;40\}\text{,}$ сумма равна $96\text{.}$

3. Заметим, что $896=8\cdot 112\text{.}$ Все числа на доске делятся на $8\text{,}$ поэтому достаточно построить минимальную цепочку сложений-удвоений от $1$ до $112\text{.}$

Двоичная запись числа $112\text{:}$ $1110000_2\text{.}$ Длина минимальной аддитивной цепочки для $n$ снизу ограничена величиной $\lfloor {\log }_{2}n\rfloor +\nu (n)-1\text{,}$ где $\nu (n)$ — количество единиц в двоичной записи. Для $112\text{:}$

$$\lfloor {\log }_{2}112\rfloor =6,\nu (112)=3,\text{нижняя оценка}=6+3-1=8.$$

Достижимость показывает явная цепочка длины $8\text{:}$

$$8\stackrel{2\cdot 8}{\to }16\stackrel{2\cdot 16}{\to }32\stackrel{2\cdot 32}{\to }64\stackrel{2\cdot 64}{\to }128\stackrel{2\cdot 128}{\to }256\stackrel{128+256}{\to }384\stackrel{2\cdot 384}{\to }768\stackrel{128+768}{\to }896.$$

Каждая стрелка соответствует одной минуте, итого $8$ минут.

Докажем, что за меньшее время достичь результата нельзя. После $k$ шагов каждое число на доске равно $8\cdot a_k\text{,}$ где $a_k$ принадлежит аддитивной цепочке длины $k$ от $1\text{.}$ По теореме о минимальной длине аддитивной цепочки число $112$ невозможно достичь менее чем за $8$ шагов.

Ответ:

а) нет

б) да

в) 8