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

Васяның тақтасында қатар келген 999 натурал сан жазылған. Сонымен қатар, Васяда «Бұл сан 2-ге бөлінбейді», «Бұл сан 3-ке бөлінбейді», $\dots$, «Бұл сан 1000-ға бөлінбейді» деген мәлімдемелерімен 999 карта бар. Вася тақтада жазылған әр санға өзінің бір картасын жабыстырады. Барлық карталарды жабыстырып болған соң, әр мәлімдемесі дұрыс болған карта үшін Вася бір кәмпит алады. Тақтада қандай сандар жазылғанына қарамастан, Вася ең көбі қанша кәмпит ала алады? ( А. Голованов )

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

Пойдем по индукции и докажем что для любых 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 конфет