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 конфет

Решение не верно тк оценка должна основыватся на любых последовательных n-1 чисел, а вы основываетесь только на 1 примере

Если среди данных чисел есть число $n \times 1000!$, то понятно, что для него все утверждения неверны. Покажем, что для $998$ верно. Пусть Вася будет по очереди выбирать числа, не кратные $2,3,\dots,999$. Если он выбирает число не кратное $q$, то он выбрал до этого $q-2$ числа, т.е. осталось $1001 - q$. Кратных $q$ среди них не меньше чем $\frac{999}{q} + 1$, и достаточно доказать, что

1001 - q \ge \frac{999}{q} + 1 \iff q + \frac{999}{q} \le 1000 \iff q^2 + 999 - 1000q \ge 0 \iff (q-1)(q-999) \ge 0.

При $2 \le q \le 999$ обе скобки положительные, значит, утверждение верно.