Задание №5 — Алгоритмы и программирование

Решение.

Нам необходимо из числа $8$ получить число $56$, используя не более 5 команд. У нас есть две операции:
1. Зачеркни слева — удаляет первую цифру числа.
2. Возведи в квадрат — возводит текущее число во вторую степень.

Проанализируем конечный результат. Чтобы получить число $56$, на последнем шаге мы могли либо применить команду 1 к какому-то числу (например, к $156$, $256$, $356$ и т.д.), либо применить команду 2. Но $56$ не является полным квадратом целого числа, значит, последней командой точно была команда 1.

Попробуем построить цепочку вычислений от начального числа $8$:

Шаг 1. У нас есть число $8$. Если мы применим команду 1, число исчезнет (останется пустота или 0), что не приведет нас к цели. Применим команду 2:
$8^{2} = 64$.
(Команда: 2)

Шаг 2. Из числа $64$ нам нужно двигаться дальше. Если применить команду 1, останется $4$. Если применить команду 2, получим $64^{2} = 4096$. Попробуем убрать лишнюю цифру:
Зачеркиваем слева цифру $6$, остается $4$.
(Команда: 1)

Шаг 3. Теперь у нас есть число $4$. Чтобы приблизиться к большим числам (в составе которых может быть $56$), возведем его в квадрат:
$4^{2} = 16$.
(Команда: 2)

Шаг 4. Снова возведем полученное число в квадрат, чтобы получить четырехзначное число, из которого можно будет "вырезать" $56$:
$16^{2} = 256$.
(Команда: 2)

Шаг 5. У нас на экране число $256$. Нам нужно получить $56$. Применяем команду 1 (зачеркнуть слева):
Убираем цифру $2$, остается $56$.
(Команда: 1)

Проверим полученный алгоритм: $8 \xrightarrow{2} 64 \xrightarrow{1} 4 \xrightarrow{2} 16 \xrightarrow{2} 256 \xrightarrow{1} 56$.
Последовательность команд: 21221. Длина алгоритма — 5 команд, что соответствует условию задачи.

Ответ: 21221

Источник: ФИПИ