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

Доказано