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 × 1000! то понятно что для него все утверждения неверны. Покажем что для 998 верно. Пусть Вася будет по очереди выбирать числа, не кратные 2,3,...,999. Если он выбирает число не кратное q, то он выбрал до этого q - 2 числа, т.е. осталось 1001 - q. Кратных q среди них не меньше чем 999/q + 1, и достаточно доказать, что 1001 - q >= 999/q + 1 <=> q + 999/q <= 1000 <=> q² + 999 - 1000q >= 0 <=> (q-1)(q-999) >= 0. При 2 <= q <= 999 обе скобки положительные, значит, утверждение верно