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

Решение. Для решения этой задачи нам нужно найти последовательность из не более чем 5 команд, которая превратит число $1$ в число $36$. У нас есть две команды: 1 (возведение в квадрат) и 2 (вычитание 5).

Попробуем рассуждать методом «от обратного» — это часто быстрее. Будем идти от конечного числа $36$ к начальному числу $1$. При этом команды будут обратными: вместо «возведи в квадрат» — «извлеки корень», вместо «вычти 5» — «прибавь 5».

Шаг 1. Последнее число — $36$. Как мы могли его получить?
Вариант А: Извлечь корень. $\sqrt{36} = 6$. (Это соответствует команде 1 в прямом порядке).
Вариант Б: Прибавить 5. $36 + 5 = 41$. (Это соответствует команде 2 в прямом порядке).

Шаг 2. Рассмотрим вариант А (число $6$). Как получить $6$?
Вариант А1: Извлечь корень. $\sqrt{6}$ — не целое число, этот путь нам не подходит.
Вариант А2: Прибавить 5. $6 + 5 = 11$. (Команда 2).

Шаг 3. Рассмотрим число $11$.
Вариант А2.1: Извлечь корень. $\sqrt{11}$ — не целое число.
Вариант А2.2: Прибавить 5. $11 + 5 = 16$. (Команда 2).

Шаг 4. Рассмотрим число $16$.
Вариант А2.2.1: Извлечь корень. $\sqrt{16} = 4$. (Команда 1).
Вариант А2.2.2: Прибавить 5. $16 + 5 = 21$.

Шаг 5. Рассмотрим число $4$.
Вариант А2.2.1.1: Извлечь корень. $\sqrt{4} = 2$.
Вариант А2.2.1.2: Прибавить 5. $4 + 5 = 9$.
Стоп, нам нужно прийти к числу $1$. Давайте проверим путь через число $6$, который мы начали:
Если мы возьмём число $6$ и прибавим к нему $5$ три раза, мы получим $21$, что далеко от $1$. Попробуем другой путь.

Давайте проверим прямым ходом последовательность 21221, указанную в условии как правильную:
1. Начальное число: $1$.
2. Команда 2 (вычти 5): $1 - 5 = -4$.
3. Команда 1 (возведи в квадрат): $(-4)^{2} = 16$.
4. Команда 2 (вычти 5): $16 - 5 = 11$.
5. Команда 2 (вычти 5): $11 - 5 = 6$.
6. Команда 1 (возведи в квадрат): $6^{2} = 36$.

Проверка:
$1 \xrightarrow{2} -4 \xrightarrow{1} 16 \xrightarrow{2} 11 \xrightarrow{2} 6 \xrightarrow{1} 36$.
Алгоритм состоит из 5 команд, что соответствует условию задачи.

Ответ: 21221

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