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

Решение.

Нам необходимо составить алгоритм получения из числа $2$ числа $100$, используя не более пяти команд. Доступны две команды:
1. Возведи в квадрат ($x^2$);
2. Вычти 3 ($x - 3$).

Для решения таких задач удобнее идти от конечного числа к начальному, используя обратные операции. Обратными операциями будут:
1. Извлечение квадратного корня ($\sqrt{x}$);
2. Прибавление 3 ($x + 3$).

Шаг 1. Начнём с числа $100$. Можно ли применить обратную команду №1? Да, из $100$ извлекается целый корень: $\sqrt{100} = 10$.
Это соответствует прямой команде №1 (возведение в квадрат).
Текущее состояние: $100 \leftarrow 10$ (команда 1 в прямом порядке).

Шаг 2. Теперь работаем с числом $10$. Извлечь корень (обратная команда №1) нельзя, так как $\sqrt{10}$ не является натуральным числом. Применим обратную команду №2: $10 + 3 = 13$.
Текущее состояние: $10 \leftarrow 13$ (команда 2 в прямом порядке).

Однако, если мы продолжим прибавлять по $3$, мы быстро превысим лимит в 5 команд. Попробуем другой путь на Шаге 1.

Шаг 1 (повторно). Снова начнём с $100$. Применим обратную команду №2: $100 + 3 = 103$. Из $103$ корень не извлекается. Это тупиковый путь, так как число будет только расти.

Шаг 2 (повторно). Вернёмся к числу $10$. Мы уже поняли, что из $10$ нужно получить число, из которого извлекается корень, или которое можно получить из $2$.
Попробуем применить обратную команду №2 ещё раз: $10 + 3 = 13$. Снова не подходит.
Применим обратную команду №2 к числу $10$ еще раз: $13 + 3 = 16$.
О! Из числа $16$ извлекается корень: $\sqrt{16} = 4$.
Текущее состояние: $10 \leftarrow 13 \leftarrow 16$ (две команды №2 в прямом порядке).

Шаг 3. Работаем с числом $16$. Применим обратную команду №1: $\sqrt{16} = 4$.
Текущее состояние: $16 \leftarrow 4$ (команда 1 в прямом порядке).

Шаг 4. Работаем с числом $4$. Применим обратную команду №1: $\sqrt{4} = 2$.
Мы пришли к исходному числу $2$!
Текущее состояние: $4 \leftarrow 2$ (команда 1 в прямом порядке).

Проверим полученный алгоритм в прямом порядке:
1. Число $2$. Команда 1: $2^2 = 4$.
2. Число $4$. Команда 1: $4^2 = 16$.
3. Число $16$. Команда 2: $16 - 3 = 13$.
4. Число $13$. Команда 2: $13 - 3 = 10$.
5. Число $10$. Команда 1: $10^2 = 100$.
Итого последовательность команд: 11221. Всего 5 команд, что соответствует условию.

Ответ: 11221

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