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)! Будет всегда иметь не правильное удтверждение

Доказано

Ответ:999

Оценка:

Вася не сможет получить больше 999 конфет, так как иначе ему нужно хотя 1000 верных утверждений а утверждений всего 999.

Пример:

На первой доске написано число равное 1000!+1,на второй 1000!+2 ,....,на 999ой 1000!+999.Тогда приклеим на первую доску первую бумажку(там где написано что не делится на 2),на вторую доску вторую бумажку и так со всеми досками. Тогда на iой доске будет написано 1000!+i и с бумажкой где написано что это число не делится на i+1.1000! делится на i+1 так как i+1<=1000 ,а i не делится на i+1 так как 0<i<i+1 =>1000!+i не делится на i+1 =>утверждение на бумажке верное ,а i может быть любым из 999 досок=>к каждой из 999 досок было приклеено верное утверждение=> вася получит 999 конфет