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

Маша мен Витя дұрыс $1001$-бұрыш пішіндес тақтада ойын ойнауда. Бастапқыда тақтаның барлық төбелері ақ түске боялған, және қандай да бір төбеде бір дойбы орналасқан. Әр жүрісте Маша өз еркімен кез келген натурал $k$ санын таңдайды, содан кейін Витя бағытты таңдап (сағат бағытымен немесе сағат бағытына қарсы), сол бағытта дойбыны $k$ төбеге жылжытады. Жүріс соңында дойбы ақ төбеге түссе, сол төбе қызыл түске боялады. Егер ойында жүрістер саны шектеусіз болса, онда Витяның әрекеттеріне қарамастан, Маша ең көбі неше төбенің қызыл түске боялуын қамтамасыз ете алады? ( М. Карпук )

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

Ответ: $858$

Ради удобства, будем считать, что номера вершин - вычеты $\mod{1001}$.

Стратегия Вити: Если в начале фишка стоит на вершине $1$, то не даём Маше заходить в вершины, дающие остаток $2$ при делении на $1001$. Это всегда можно сделать, если мы не находимся в одной из таких вершин.

Стратегия Маши: Пусть, сейчас меньше $858$ красных вершин, т.е. есть хотя бы $144$ белых. Докажем, что для любых $144$ вершин, Маша может гарантированно попасть в одну из них за конечное число ходов.

Пусть, $S_0$ - эти $144$ вершины, $S_{n+1}=\left\{\frac{x+y}{2} \mid x,y \in S_n \right\}$, $S$ - максимальное по включению из всех $S_n$. Заметим, что если Маша сейчас находится в какой-то вершине из $S_{n+1}$, то она за один ход может попасть в какую-то вершину из $S_n$. Тогда, за конечное число ходов Маша может попасть из $S$ в $S_0$. Докажем, что в $S$ будут все вершины.

По максимальности $S$, для любых $x$, $y \in S: \frac{x+y}{2} \in S$. Ради удобства, сдвинем индексы так, что $0 \in S$. Тогда, подставив $y=0$, мы знаем, что для любого $x \in S$ вершины $\frac x2, \frac x4, \frac x8, \dots, \frac x{2^{\varphi(1001)-1}} \equiv 2x$ тоже будут в $S$. Применив для $\frac{x+y}2$, в $S$ находится сумма любых двух элементов. Следовательно, в $S$ также будет $xy$ для всех $x$, $y \in S$. Значит, $S$ - идеал в $\mathbb{Z}/1001\mathbb{Z}$. Поскольку мощность идеала делит мощность кольца, а $143$ - наибольший собственный делитель $1001$, мы получаем, что в $S$ есть все вершины. $\square$

Решение: переведем задачу на числа по $mod$ $1001$

Давайте Маша будет ходить и в какой то момент оказалось что как бы не ходила Маша она больше не сможет попасть в следующие фишки:

$x_1<x_2<...<x_s$. Тогда поймем следующее:

1) $x_{i}+x_{i+1}$ не делится на 2, иначе мы можем попасть ходами в $\frac{x_{i}+x_{i+1}}{2}$, и тогда гарантировано сможем попасть в одно из двух чисел, а значит это число - одно из тех в которое мы не могли попасть, но тогда оно зажато между $x_i$ и $x_{i+1}$, противоречие, между ними не было чисел

2) из 1), у нас есть число $\frac{x_i+x_{i+2}}{2}$, но мы не могли в него попасть а значит оно может быть равно только $x_{i+1}$

3) У нас возникает арифметическая прогрессия данных чисел, с нечетной разностью.

Тогда поймем вот что:

По $mod$ $1001$, у любых двух чисел есть число которое равноудалено от них, так как $x$, $y$ это либо $\frac{x+y}{2}$ либо $\frac{1001+x+y}{2}$ в зависимости от того, делится $x+y$ на 2 или нет

Значит рассмотрим разные d

$d=1$

Тогда у нас числа $x, x+1, ..., x+k$.

Если k - нечетное то:

Берем середину $x$ и $x+k$. Она тоже должна быть не достигаемой но при этом так как k - нечетное то она равна $\frac{1001+x+x+k}{2}=x+\frac{1001+k}{2}$.

$\frac{1001+k}{2}>k>...>0$, и если даже $k=1001$, то противоречие.

$k$- четное тогда берем $k-1$ и для него работает все тоже самое как и для k. Но тогда единственное число которое могло стать серединой - число $x+k$

$x+k=x+\frac{1001+k-1}{2}$ по $mod$ $1001$

$k=1000$ по $mod$ $1001$

Противоречие, у нас $1001$ чисел в которые мы не можем попасть.

На самом деле, аналогично для $d=3, 5$:

$d=3$

Если $3k$ - нечетное то:

Берем середину $x$ и $x+3k$. Это $\frac{1001+x+x+3k}{2}=x+\frac{1001+3k}{2}$.

$\frac{1001+3k}{2}>3k>...>0$, и если даже $3k=1001$ по $mod$ $1001$, то $k=1001$ противоречие

$3k$- четное тогда берем $3k-3$ и для него работает все тоже самое как и для $3k$. Но тогда единственное число которое могло стать серединой - число $x+3k$

$x+3k=x+\frac{1001+3k-3}{2}$

$3k=998$

$k=1000$ по $mod$ $1001$

Противоречие.

$d=5$

Если $5k$ - нечетное то:

Берем середину $x$ и $x+5k$ это $\frac{1001+x+x+5k}{2}=x+\frac{1001+5k}{2}$.

$\frac{1001+5k}{2}>5k>...>0$, и если даже $5k=1001$ по $mod$ $1001$, то $k=1001$ противоречие.

$5k$- четное тогда берем $5k-5$ и для него работает все тоже самое как и для $5k$. Но тогда единственное число которое могло стать серединой - число $x+5k$

$x+5k=x+\frac{1001+5k-5}{2}$ по $mod$ $1001$

$5k=996$

$k=1000$ по $mod$ $1001$

Противоречие.

Значит $d\geq7$

Поймем следующее:

У нас кол во белых $\leq s$. Но тогда при $d>7$, кол во чисел в прогрессии уменьшится соответственно $max$ кол во белых достигается при $d=7$

И тут, их может быть только $143$:

$x, x+7, ..., x+994$

Ну тогда белых максимум могло быть 143. Соответственно Маша гарантированно может окрасить в красный 858 фишек

Стратегия для Вити по защите 143 фишек:

Берем фишки $1, 8, ..., 995$. Тогда Витя способен сохранить их все, потому что:

Пусть изначально мы были на 0. Тогда возьмем ход в который мы первый раз попадаем на фишку $7k+1$. Заметим, что мы гарантировано попадем на эту фишку то есть мы попадем либо на $7a+1$ либо на $7b+1$. Тогда рассмотрим наше местоположение сейчас:

Либо мы на $\frac{7a+1+7b+1}{2}=7\frac{a+b}{2}+1$(если $a+b$ делится на 2) Либо мы на $\frac{1001+7a+1+7b+1}{2}=7\frac{143+a+b}{2}+1$(если$a+b$ не делится на 2). Но в любом случае мы должны были быть на некотором $7c+1$. Противоречие, так как это был первый ход на котором мы оказывались на фишке $7k+1$.То есть Витя с одной стороны может сохранить $143$ фишки, а Маша гарантировано сможет покрасить в красный хотя бы $1001-143=858$ фишек. Значит ответ - $858$ фишек Маша гарантировано красит в красный и при этом есть случаи в которых она может покрасить ровно $858$ фишек - где Витя защищает $7k+1$