15-я Международная Жаутыковская олимпиада по математике, 2019 год

Докажите, что существует по крайней мере $100!$ способов разбить число $100!$ на сумму слагаемых из множества $\{1!, 2!, 3!, \ldots, 99! \}$. (Разбиения, отличающиеся порядком слагаемых, считаются одинаковыми; любое слагаемое можно использовать несколько раз. Напомним, что $n!=1 \cdot 2 \cdot \ldots \cdot n.$) ( Д. Елиусизов )

Комментарий/решение

Решение: Рассмотрим уравнение $a_1\cdot 1!+a_2\cdot 2!+a_3\cdot 3!=100!,$ где $a_1,a_2,a_3\in\mathbb Z _{\ge 0}.$

Рассмотрим пару чисел $(a_2,a_3),$ что $1\le a_2\le \dfrac{100!}{2\cdot 2!}$ и $1\le a_3\le \dfrac{100!}{2\cdot 3!}.$

Ясно, что таких пар $C=\dfrac{100!^2}{2^2\cdot 2!\cdot 3!}.$ Заметим, что $a_2\cdot 2!+a_3\cdot 3!\le \dfrac{100!}{2}+\dfrac{100!}{2}=100!,$ поэтому можно выбрать $a_1\in\mathbb Z_{\ge 0},$ что $$a_1\cdot 1!+a_2\cdot 2!+a_3\cdot 3!=100!$$

Очевидно, что $C>100!,$ откуда следует требуеомое.

Индукция. Утверждение: $\forall k\geq4 \in N, \exists k!$ вариантов таких представлении числа больше чем $k!$

База $k=4.$ $2*x+1*y - 12$ вариантов. $6*x+1*y - 4$ варианта. $6*x+2*y - 4$ варианта. $6+2+1+...+1, 6+2+2+1+...+1$

Переход $k ---> k+1$

Пусть некоторые (возможно все) варианты представления $k!$ это множество $M$ с $k! $элементами тогда представлении $(k+1)!$ должно быть больше чем$ (k+1)!$.

Действительно рассмотрим:

$0)M+0*k!+1+1...+1$

$1)M+1*k!+1...+1$

$...$

$k)M+k*k!$

Очевидно $i), j)$ не повторяются из-за количества $ k!, $ а ведь в $M$ тоже нет $ k!. $Значит $i) $ на самом деле содержит больше чем $k!$ вариантов, ведь прибавляем мы одно и то же количество $k!$ и единиц, в итоге у нас больше $k!*(k+1)$ вариантов