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


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

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

  0
2021-05-04 12:47:20.0 #

Решение: Рассмотрим уравнение $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!,$ откуда следует требуеомое.