Всесиб 2023, отборочный этап, 8 класс, задача 5
( баллов) Вася выписал на доску набор различных натуральных чисел, каждое из которых не превосходит . Оказалось, что для любых двух написанных и число не делится нацело на число . Какое наибольшее количество чисел мог выписать Вася?
Ответ
Решение. Докажем, что ответ равен .
Оценка. Докажем, что больше чисел Вася написать не мог. Для этого рассмотрим три любых подряд идущих числа , и . Заметим, что соседние числа выписаны быть не могут (иначе их разница равна единице, а любое число делится на ). Поэтому максимум могут быть выписаны только и . Но если они выписаны, то их сумма равна , что делится на разность . Подводя итог, из любых трёх последовательных чисел может быть выписано максимум одно. Но тогда на доске может быть максимум одно число из , и ; максимум одно из , и ; ...; максимум одно из , и . То есть, из первых чисел может быть выписано максимум плюс число , итого .
Пример. Приведём пример набора из чисел. Пусть Вася выписал все числа вида для от до , то есть, . Заметим, что сумма двух таких чисел имеет вид , что не делится на , а разность равна , что кратно трём. Но число, не делящееся на , не может делиться на число, которое на делится. Поэтому условия задачи выполнены, и этот набор из чисел подходит.