Факторизация

[Dendr]

Дано натуральное число N>=5.
За один шаг разрешается разбить его на произвольное число слагаемых (в т.ч. одинаковых), не равных единице, и заменить N на их произведение. Конечная цель - получить в итоге факториал некоторого числа.

Надо доказать, что:
1) любое N можно привести к факториалу за 4 шага (или быстрее),
2)* на самом деле, за 2,
3) если N "достаточно велико", то и вовсе за один.

Примеры для малых N:
5=2+3 --> 2х3=6=3! - один шаг.
6=3! - ноль шагов.
7=2+5 --> 2х5=10=4+6 --> 4x6=24=4! - два шага.

[Юляша]

Нетрудно доказать, что для всех чисел, кроме чисел вида k*(k+1)/2 - 2 и k*(k+1)/2 - 3, достаточно одного шага.

[Dendr]

Подсказка к 1-му пункту: рассмотрите числа вида 3k.

[Юляша]

Доказательство для пункта 2 (пункт 1 при этом выполняется автоматически).

Рассмотрим "треугольные" числа вида 1+2+3+4+...+n = n*(n+1)/2 (6, 10, 15, 21 и т.д.). Произведение таких слагаемых равно n!. Тут правда фигурирует единичка, поэтому в лоб этот метод применим к числам вида n*(n+1)/2 - 1.

Если мы заменим сумму 2+3 на их произведение 2*3, то сумма слагаемых возрастет на единицу. Используя вместо этого 2+4, 2+5... 2+n, мы почти дойдем до следующего треугольного числа - у нас останутся неучтенными только два числа.

Пример.

20 = 2+3+4+5+6 -> 6!
21 = 6+4+5+6 -> 6!
22 = 8+3+5+6 -> 6!
23 = 10+3+4+6 -> 6!
24 = 12+3+4+5 -> 6!
25 = ?
26 = ?
27 = 2+3+4+5+6+7 -> 7!

Что касается промежуточных чисел, то у нас есть возможность попытаться привести их к треугольному виду.

Если число не делится на три, то все приводится легко.

6*n+1 = 2*n+(4*n+1) -> (4*n)*(4*n+1)/2
6*n+2 = (2*n+1)+(4*n+1) -> (4*n+2)*(4*n+1)/2
6*n+4 = (2*n+1)+(4*n+3) -> (4*n+2)*(4*n+3)/2
6*n+5 = (2*n+2)+(4*n+3) -> (4*n+4)*(4*n+3)/2

Если число делится на 3, то проведем следующее преобразование:

3*n = n + 2*n -> (2*n)*(2*n)/2 = (2*n)*(2*n-1)/2 + n
Число попадет в нужный диапазон, если (2*n)*(2*n+1))/2 - (2*n)*(2*n)/2 > 3, то есть, если n>3.

Пример: 12 = 4+8 ->32 = 14+3+4+5+6 -> 7!

Случай числа 9 приходится разбирать вручную, но 9=4+5 -> 20 также позволяет обойтись двумя шагами.

[Dendr]

Ну, это-то уже практически доказательство пункта 3. Этот ответ и приведу.

Если не говорить о "почти треугольных числах" (так долго), то можно просто ввести класс чисел Pn=2+3+...+n.

Эти числа сводятся к факториалу за один шаг.
Далее, числа Pn+1, Pn+2, ... Pn+n-2 аналогично, "одношаговые" (объяснение см. у Юляши).
Что касается Pn+n+1, то оно равно P(n+1), так что тут все в ажуре.
Остается разобраться с числами Pn+n-1 и Pn+n. (обозначим их временно Pn') Они пока "подозрительные" - могут сводиться за 1 шаг. А могут и нет.

На самом деле, не все так печально. Достаточно взять два произведения вместо одного:
Pn'=2x(n-k)+3x4+5+6+...+(n-k-1)+(n-k+1)+...+n
Как видно, произведение этих чисел точно равно n!. А само Pn'=(n-k)+12+(2+3+4)-(2+3+4)+5+6+...+n=(n-k)+3+Pn=Pn+n-(k-3)
Беря k-3=(0 или 1), то есть k=(3 или 4), и помня, что n-k>4 (чтобы не было повторов), получаем, что если n>8, то все числа между Pn и P(n+1) - "одношаговые".
Так как P9=2+3+...+9=11*8/2=44, то вывод следующий: любое N>=44 сводится к факториалу некого n за 1 шаг.
Больше того: при n=8 мы можем взять k=3, и увидеть, что P8+8=10*7/2+8=43 - одношаговое: 43=2х5+3х4+6+7+8

Вот 42 таким типовым приемом уже не определяется, но в условии этого и не требовалось - было сказано, что "N - достаточно большое". "Достаточно" достаточно определить, как ">42".

А вообще, получаем, что "подозрительных" чисел всего ничего - 11 штук:
P3+2, P3+3, P4+3, P4+4, P5+4, P5+5, P6+5, P6+6, P7+6, P7+7, P8+7
Конкретнее, 7,8, 12, 13, 18, 19, 25, 26, 33, 34, 42.

Однако, ручная проверка показывает, что и эти числа "одношаговые", кроме 7, 8, 12, 13 - они двушаговы.
Следующее, 18, уже представляется так: 18=2+6+10 --> 2x6x10=120=5! (странно, но в моем источнике оно названо в числе безнадежно двушаговых...)

Напоследок добавлю, что все пункты в задаче доказываются отдельно и независимо, так что можно говорить, что из (3) (плюс ручной перебор 11 чисел) следует (2), а из (2) - тем более (1), но так делать неинтересно.

Так что подожду доказательства пункта (1). Оно в самом деле универсально и в чем-то изящно.