Задача 4. Круг Ани и Бори

Что нужно доказать: две стратегии, а не одна

Пар соседних точек на круге ровно $100$: точка $1$ соседствует с точкой $2$, точка $2$ — с точкой $3$, …, точка $100$ — с точкой $1$. Ходов всего $100$, по $50$ у каждого: Аня делает ходы $1, 3, 5, \ldots, 99$, Боря — ходы $2, 4, \ldots, 100$.

«Аня может гарантировать $N$ пар» значит: у Ани есть способ играть так, чтобы разноцветных пар оказалось не меньше $N$, как бы ни играл Боря. «Наибольшее такое $N$» значит ещё, что больше гарантировать нельзя: у Бори есть способ играть так, чтобы разноцветных пар оказалось не больше $N$, как бы ни играла Аня. Поэтому нужны две стратегии — одна для Бори (оценка сверху) и одна для Ани (оценка снизу), и они должны дать одно и то же число.

Зачем это нужно: в задаче про игру ответ без одной из двух половин не доказан. Чтобы увидеть обе половины, удобно поиграть за каждого на маленьком круге.

Стратегия Бори: не больше 50

Боря каждым ходом красит белую точку, у которой есть уже покрашенная соседка, — и красит её в цвет этой соседки.

Почему такая точка всегда есть. Перед ходом Бори на круге есть покрашенные точки (Аня только что ходила) и есть белые (иначе игра закончена). Пойдём по кругу от покрашенной точки: когда-нибудь встретим первую белую, и точка перед ней покрашена — это и есть белая точка с покрашенной соседкой.

Что даёт один такой ход. Пара «новая точка — её покрашенная соседка» одноцветная. Раньше эту пару не считали: новая точка была белой. Значит, каждый ход Бори добавляет новую одноцветную пару, и разные ходы дают разные пары — в каждой своя новая точка (рисунок ниже).

У Бори $50$ ходов, значит, в конце не меньше $50$ одноцветных пар. Пар всего $100$, поэтому разноцветных не больше $50$, как бы ни играла Аня.

Как это заметить: Боря хочет, чтобы соседи совпадали по цвету, а самый простой способ наверняка получить совпадение — скопировать цвет соседки. В модели Боря так и играет, и после каждого его хода написано, какая пара стала одноцветной.

Стратегия Ани: хотя бы 49

Первым ходом Аня красит любую точку в любой цвет. Каждым следующим ходом она красит белую точку, у которой есть покрашенная соседка, — в цвет, отличный от цвета этой соседки. Такая точка есть по той же причине, что и у Бори.

Разберём, что получается (рисунок ниже):

• покрашена только одна соседка — пара с ней разноцветная;

• покрашены обе соседки, и они одного цвета — Аня красит в другой цвет, и обе пары разноцветные;

• покрашены обе соседки, и они разных цветов — какой цвет ни выбери, с одной из соседок пара будет разноцветной.

Во всех случаях появляется хотя бы одна новая разноцветная пара: в ней новая точка, которая только что была белой. Боря может создавать одноцветные пары, но разноцветную пару, которая уже есть, он не испортит — точки не перекрашивают.

У Ани $50$ ходов, из них $49$ — не первые. Значит, в конце разноцветных пар не меньше $49$, как бы ни играл Боря. Пока получилось $49$, а не $50$: не хватает одного наблюдения.

Чётность: 49 превращается в 50

Пусть все точки покрашены. Пойдём по кругу от какой-нибудь точки и будем следить за цветом. Проходя разноцветную пару, мы меняем цвет; проходя одноцветную — нет. Обойдя весь круг, мы вернулись в ту же точку, то есть к тому же цвету, с которого начали. Значит, цвет менялся чётное число раз: после каждой смены «красный → синий» нужна смена «синий → красный», чтобы вернуться (рисунок ниже).

Итак, число разноцветных пар всегда чётно. По шагу 3 оно не меньше $49$, а $49$ нечётно — значит, оно не меньше $50$.

Как это заметить: в модели после каждой партии число разноцветных пар чётное — и при $8$, и при $12$, и при $20$ точках. Когда что-то всегда чётно, стоит поискать причину «обошли круг и вернулись к началу».

Ответ: ровно 50

Боря умеет не давать больше $50$ (шаг 2), Аня умеет получать не меньше $50$ (шаги 3–4). Значит, наибольшее число разноцветных пар, которое Аня может гарантировать, — ровно $50$.

Где важно, что точек именно $100$: половина, $50$, — чётное число. При $6$ или $10$ точках половина нечётна, и те же рассуждения дают только «не больше половины» и «не меньше половины минус один»; перебор показывает, что там Аня гарантирует на одну пару меньше половины. Поэтому в модели круги из $8$, $12$, $16$ и $20$ точек: как и $100$, эти числа делятся на $4$, и ответ там — ровно половина.