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

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

Попробуем рассуждать «от обратного» — от конечного числа $51$ к исходному числу $1$. Это часто быстрее, так как выбор действий становится более ограниченным.

Шаг 1. Последнее число — $51$. Число $51$ не является квадратом целого числа, поэтому последней командой не могло быть возведение в квадрат (команда 1). Значит, последней была команда 2 (прибавление $2$). Выполним обратное действие: $51 - 2 = 49$. (Команда 2)

Шаг 2. Теперь у нас число $49$. Число $49$ является квадратом числа $7$ ($7^{2} = 49$). Значит, мы могли получить его возведением в квадрат. Выполним обратное действие: $\sqrt{49} = 7$. (Команда 1)

Шаг 3. Теперь у нас число $7$. Число $7$ не является квадратом целого числа. Значит, на этом этапе была команда 2. Выполним обратное действие: $7 - 2 = 5$. (Команда 2)

Шаг 4. Теперь у нас число $5$. Число $5$ не является квадратом целого числа. Значит, снова была команда 2. Выполним обратное действие: $5 - 2 = 3$. (Команда 2)

Шаг 5. Теперь у нас число $3$. Число $3$ не является квадратом целого числа. Значит, снова была команда 2. Выполним обратное действие: $3 - 2 = 1$. (Команда 2)

Мы пришли к исходному числу $1$. Теперь запишем команды в прямом порядке (от шага 5 к шагу 1): 1. Прибавить 2: $1 + 2 = 3$ (Команда 2) 2. Прибавить 2: $3 + 2 = 5$ (Команда 2) 3. Прибавить 2: $5 + 2 = 7$ (Команда 2) 4. Возвести в квадрат: $7^{2} = 49$ (Команда 1) 5. Прибавить 2: $49 + 2 = 51$ (Команда 2)

Полученная последовательность команд: 22212. Она содержит ровно 5 команд, что соответствует условию задачи.

Ответ: 22212

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