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$