Теория чисел на Межведе

Поскольку произведение первых 6 натуральных чисел равно то искомое число не больше

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел делится на . Поделим:

и получим натуральное число способов выбрать шестёрку из элементов. Действительно, делится.

Вычислим

То есть нужно найти остаток по модулю Рассмотрим первое слагаемое.

Раскрывая скобки, как минимум два раза выберется из скобок, что дает в сравнении по модулю Это верно, кроме случаев, когда были выбраны все единицы или когда было выбрано одно из всех скобок. Тогда, используя бином Ньютона, получаем, что первое слагаемое сравнимо с

Аналогично получаем, что второе слагаемое сравнимо с

Тогда получаем

Следовательно, остаток равен

Предположим, что Преобразуем уравнение:

Тогда, так как то число целое и не кратно трем. Значит, тоже целое, но число не может быть степенью тройки (нулевой быть не может, так как оно больше а ненулевой - так как оно не кратно Таким образом, В силу симметрии относительно перестановки получим, что Пусть Тогда:

Домножим на

Пусть Если то Значит, тогда Получим что, или Откуда получим ответ.

Первое решение.

Заметим, что Далее проверкой до целой части от соответствующего арифметического корня проверяем оба множителя на простоту. Разложение получено.

Второе решение.

Заметим, что Тогда

Следовательно, пары чисел или имеют общие делители, отличные от 1. Найдём наибольший общий делитель чисел по алгоритму Евклида:

Следовательно, – простое число. Остаётся разделить на

Чтобы понять сколько цифр содержится в записи натурального числа , надо найти такое неотрицательное целое число что будет справедливым неравенство Такое число очевидно, единственно. (Например, поэтому в записи числа 992 три цифры.)

Итак, надо найти такое целое неотрицательное что По условию Возведя обе части в степень получим Значит, в десятичной записи числа содержится 31 цифра.

Рассмотрим числа вида , где — нечётное. Так как чисел указанного вида бесконечно много, то среди них найдутся два числа и имеющие одинаковые остатки от деления на Тогда разность делится нацело на При этом и число является чётным. Так как и числа и взаимно просты, то число делится нацело на а следовательно, и на

Пусть пара натуральных чисел удовлетворяет исходному уравнению

(1)

Тогда

1.

Положив и подставив в получим

Очевидно, что . Поэтому . Без ограничения общности можно считать, что в этой паре . Будем это записывать как

2.

По условию, число является корнем многочлена

(2)

По теореме Виета, этот многочлен еще имеет корень причем

Отсюда следует, что и Поэтому уравнение имеет еще одно решение в натуральных числах

Это означает, что для многочлена справедливы равенства

Заметим, что

Поэтому число лежит между корнями многочлена а именно:

Следовательно,

Итак, для любого решения существует другое решение, у которого максимальный элемент окажется меньше. Таким образом, мы можем строить новые решения, у которых максимальный элемент становится все меньше. Но при этом этот максимальный элемент, постоянно уменьшаясь, остается натуральным числом, что невозможно. Пришли к противоречию. Значит, исходное уравнение решений в натуральных числах не имеет.

Пусть

Тогда является положительным корнем уравнения

Отсюда находим .

_________________________________________________________________________________________________________________________________________________________________________________

В официальных решениях на сайте олимпиады доказывается, почему выражение для определено и на самом деле является действительным числом через критерий существования предела у монотонной последовательности. Но тогда корректнее было бы переформулировать условие задачи (и в идеале ещё не давать задачу 9-классникам), а при данной формулировке получается, что достаточно показать невозможность другого значения, кроме как 43.

Если то

Если то правая часть кратна трём, а левая — нет. Значит, Если то вновь придём к противоречию : кратное трём число не может быть никакой степенью двойки, в том числе нулевой. Остаётся только вариант в котором есть решение

Рассмотрим теперь случай Не умаляя общности будем считать Тогда можно записать Исходное уравнение запишется в виде

Если то в равенстве левая часть делится на а правая нет. Поэтому может быть только Но тогда ведь иначе в равенстве справа стоит натуральное число, а слева деление нечётного натурального числа на степень двойки (то есть в итоге получается дробь, а не натуральное число).

В итоге обе части равенства

являются натуральными числами, поэтому по основной теореме арифметики должны быть равными степени вхождения простых множителей, откуда

Очевидные решения . Получаем тройки , которые дают решения в силу симметрии . Пусть теперь , тогда , то есть . Отсюда чётно. Но если кратно двум, то и . Если , то хотя бы одно из этих чисел не является степенью двойки, что невозможно. Тогда , откуда в этом случае решений нет.

Все делители числа разбиваются на пары Заметим, что поскольку Но тогда понятно, что количество таких пар не превосходит а количество делителей — не больше В данном случае нам хватит оценки

По условию количество делителей равно Следовательно, получим неравенство Решая его в натуральных числах, получаем, что Перебирая чётные находим подходящие и

Если — делитель числа , то — тоже делитель числа . Хотя бы одно из этих двух чисел не превосходит Поэтому число делителей не превосходит

По условию число делителей равно Следовательно,

Разложим число на возможные простые множители:

Из условия на количество делителей

следует, что при правая часть строго больше левой:

Поэтому и каждая из скобок в левой части меньше 5, так что остаётся перебрать три случая в равенстве

• быть не может, так как тогда левая часть чётна, а правая часть нечётна.
• при единственным решением является
• при единственным решением является

Заметим, что из этого неравенства следует, что

Пусть . Тогда . Мы знаем, что не может давать остаток 3 при делении на 9, так как тогда делится на 3, но не делится на 9. Значит, может быть равно только . Заметим, что и . Число не равно 135 и 136 , так как . Значит, и подходит.