Разбиение натуральных чисел на множества

Question

Как мне доказать следующий вопрос

Докажите, что в любом разбиении N9 (первых девяти натуральных чисел) на три набора будет хотя бы один набор, произведение чисел которого больше или равно 72.

Answer 1

Я бы пошел на доказательство от противоречия.

Обратите внимание, что произведение первых девяти натуральных чисел равно 9! = 362880. Более того, если мы умножим произведения разных множеств, мы должны прийти к одному и тому же ответу.

Теперь предположим, что каждое произведение наборов в разделе меньше 72. Т.е. продуктов может быть не более 71. Даже если все три продукта имеют максимально допустимое значение, произведение всех чисел будет не более 71 * 71 * 71 = 357911.

Это не соответствует известному значению 362880. Таким образом, мы находим противоречие.

Противоречие возникает из-за нашего предположения, то есть, что все множества в разбиении имеют произведение меньше 72. Следовательно, это предположение не может быть верным. Следовательно, должен быть хотя бы один набор с произведением, равным или превышающим 72.