Всесиб 2021, 10 класс, задача 4
( баллов) Пусть - натуральные числа. Доказать, что среди произвольных последовательных натуральных чисел всегда найдутся два, произведение которых делится на .
Доказательство. Рассмотрим произвольные последовательных натуральных чисел, назовём их множеством . Остатки от деления последовательных натуральных чисел на принимают, в некотором циклическом порядке, все значения , поэтому среди них всегда найдётся число, делящееся на . Поскольку , то среди тех же чисел найдётся число, делящееся на . Если первое и второе найденные числа различны, то их произведение делится на .
Предположим, что оба найденных числа совпадают и равны . Обозначим наибольший общий делитель и за , тогда , , причём и взаимно просты. Ввиду того, что делится на и , оно делится и на их наименьшее общее кратное, равное . Чтобы получить произведение, делящееся на , достаточно найти среди чисел множества второй сомножитель, делящийся на .
Числа и делятся на , поэтому, если одно из них лежит в , его можно взять в качестве второго сомножителя для . Если же оба они не лежат в , то первое меньше всех чисел из , а второе - больше всех чисел из , поэтому их разность, равная , не меньше . Тогда , что невозможно, так как - собственный делитель и не может превосходить - противоречие.
Верно рассмотрен только случай, когда первое и второе найденные числа различны