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

У Васи есть доска, на которой написано 999 последовательных натуральных чисел, а также 999 бумажек с надписями «Это число не делится на 2», «Это число не делится на 3», $\dots$, «Это число не делится на 1000». Вася приклеит по одной из своих бумажек к каждому из чисел на доске, а затем ему дадут по конфете за каждую бумажку, на которой окажется верное утверждение. Какое наибольшее количество конфет Вася сможет заработать, каковы бы ни были числа на доске? ( А. Голованов )

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

Пойдем по индукции и докажем что для любых n последовательных чисел, если взять n карточек которые гласят

Не делится на 2, не делится на 3, ..., Не делится на n+1

То Вася сможет добиться того, чтобы хотя бы на n-1 из чисел, утверждение было верным.

База для 2 довольно очевидна, среди двух чисел максимум одно делится на 2, значит хотя бы одно утверждение будет верно. Причем есть случаи когда ровно 1 верно - 6, 7

Тогда рассмотрим для k+1, при этом оно верно для k

Тогда если есть числа

x, x+1, ..., x+k

И карточки: Не делится на 2, не делится на 3, ..., не делится на k+2

x, x+k, хотя бы одно из них не делится на k+2, тогда просто туда ставим эту карточку и +1 конфета. При этом осталось k последовательных чисел и карты не делится на 2, не делится на 3, ..., не делится на k+1, а для них верно по индукции что хотя бы k-1 из них будут верными

Причем есть случаи когда ровно k будут верными

(k+1)!, (k+1)!+1, ..., (k+1)!+k, среди этих чисел (k+1)! Будет всегда иметь не правильное удтверждение

Доказано