Получить из числа 22 число 2001

[Ktina]

Натуральное число $n$ разрешается заменить на число $ab$, если $a+b=n$ и числа $a$ и $b$ натуральные.
Можно ли с помощью таких замен получить из числа 22 число 2001?

(Автор: Клепцын В.А., источник: http://problems.ru/view_problem_details ... p?id=98508)

Мне показалось подозрительным, что автор решения называет два предложенных им пути (в 4 и в 7 ходов) короткими.
Странно, почему товарищ Клепцын не заметил красивейший мат в три хода, да ещё и возможность дать его двумя способами:

$$22=21+1 \rightarrow 21=10+11 \rightarrow 110=87+23 \rightarrow 2001$$

или

$$22=21+1 \rightarrow 21=14+7 \rightarrow 98=69+29 \rightarrow 2001$$

Любопытно, а можно ли эту задачу в два хода решить?
Пожалуйста, помогите решить.
Заранее спасибо!

[svv]

Попробуйте идти в обратную сторону. $2001=3\cdot 23\cdot 29$.

[iou]

Кажется, нельзя.
$2001=3\cdot23\cdot29=ab$
То есть нам нужно, чтобы $a$ и $b$ в сумме давали $22$, а как не группируй, любой множитель больше, чем $22..$

[Ktina]

iou
Так это Вы доказали, что в один ход нельзя.

-- 12.05.2016, 23:53 --

svv
Вы правы, несложный перебор с конца доказывает, что нельзя.
Действительно, 2001 можно получить либо из 2002 или 670, что слишком много (так как из 22 нельзя получить больше, чем 121), либо из 110 или 98, но ни 110, ни 98 нельзя получить из 22 (там несложный перебор).

[StaticZero]

Ktina в сообщении #1123228 писал(а):

Странно, почему товарищ Клепцын не заметил красивейший мат в три хода, да ещё и возможность дать его двумя способами:

(Оффтоп)

Задачи олимпиадного характера зачастую подразумевают множество разных решений. Ваше решение мне кажется более красивым, но решение автора тоже несложное и ведёт к требуемому. Излишний лоск тут, пожалуй, искать смысла немного.

[Ktina]

StaticZero
И Вы тоже правы.
Вообще, несложно доказать, что из любого натурального $k>4$ можно получить любое натуральное $m$, имея в запасе достаточно большое (но конечное!) число ходов.
Действительно, из любого числа, большего 4, можно получить ещё большее число. С другой стороны, из любого натурального $c>1$ можно получить $c-1$.

[StaticZero]

Ktina в сообщении #1123243 писал(а):

Вообще, несложно доказать, что из любого натурального $k>4$ можно получить любое натуральное $m$, имея в запасе достаточно большое (но конечное!) число ходов.

А вот вам и задачка on-the-spot: докажите, что любое натуральное число получается указанным преобразованием из $k > 4$ и попробуйте оценить количество шагов, чтобы из заданного $n$ получить заданное $m$, $m > n$.

[Ktina]

(Оффтоп)

StaticZero в сообщении #1123245 писал(а):

А вот вам и задачка on-the-spot ...

Это как? На прыще?

[StaticZero]

Ktina в сообщении #1123249 писал(а):

Это как? На прыще?

(Оффтоп)

Не отходя от кассы в вольном переводе.