Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  3
3 года 11 месяца назад #

Решение: Рассмотрим уравнение a11!+a22!+a33!=100!, где a1,a2,a3Z0.

Рассмотрим пару чисел (a2,a3), что 1a2100!22! и 1a3100!23!.

Ясно, что таких пар C=100!2222!3!. Заметим, что a22!+a33!100!2+100!2=100!, поэтому можно выбрать a1Z0, что a11!+a22!+a33!=100!

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

  1
1 года 8 месяца назад #

Индукция. Утверждение: k4N,k! вариантов таких представлении числа больше чем k!

База k=4. 2x+1y12 вариантов. 6x+1y4 варианта. 6x+2y4 варианта. 6+2+1+...+1,6+2+2+1+...+1

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

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

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

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

1)M+1k!+1...+1

...

k)M+kk!

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