«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М1098

Условие задачи (1988, № 4) Задача М1098 // Квант. — 1988. — № 4. — Стр. 27; 1988. — № 8. — Стр. 36—37.

На окружности расставлены $n$‍‍ точек, занумерованных подряд числами 1, 2, $\ldots$‍,$n$‍.‍ Двое играют в следующую игру. Каждый по очереди проводит хорду, соединяющую две точки с номерами одной чётности. Любая хорда не должна иметь общих точек (даже концов) с проведёнными ранее. Побеждает тот, кто делает последний ход. При каждом $n=4$‍,‍ 5, 6, $\ldots$‍‍ выясните, кто из игроков имеет выигрышную стратегию: начинающий или его партнёр.

В. Г. Чванов


Решение задачи (1988, № 8) Задача М1098 // Квант. — 1988. — № 4. — Стр. 27; 1988. — № 8. — Стр. 36—37.

Ответ: при $n$‍‍ кратном 4, а также при нечётном $n$‍‍ выигрывает первый (начинающий) игрок, а при $n=4k+2$‍($k$‍‍ целое) — второй.

Удобно считать, что точки с чётными и нечётными номерами изображены разными цветами — скажем, белым и чёрным, — и что точки делят окружность на равные части.

Во всех случаях основная идея выигрышной стратегии — использовать симметрию.

Стратегия 1-го игрока при $n=4k$‍‍ — провести первым ходом диаметр, а затем на каждый ход 2-го отвечать проведением симметричной относительно этого диаметра хорды — см. рис. 1. (Такой ход возможен, поскольку после каждого хода 1-го игрока позиция будет симметрична относительно диаметра. Здесь важно, что диаметрально противоположные точки имеют один и тот же цвет, и симметричные относительно диаметра точки — тоже.)

При $n=4k+2$‍‍ выигрышная стратегия 2-го игрока — на каждый ход 1-го игрока отвечать проведением хорды, симметричной относительно центра окружности. Здесь существенно, что диаметрально противоположные точки имеют разный цвет — ниже мы воспользуемся тем, что уже при одном этом условии игра проигрышна для начинающего.

Рис. 1
Рис. 1
Рис. 2
Рис. 2
Рис. 3
Рис. 3

Пусть $n$‍‍ — нечётно (тогда на окружности оказываются две соседние чёрные точки, с номерами 1 и $n$‍).‍ При $n=4k+1$‍‍ 1-й игрок обеспечит себе выигрыш, если первым ходом соединит, например, чёрные точки с номерами 1 и 3 (рис. 2), тем самым сведя дело к аналогичной игре с $n=4(k-1)+2$‍,‍ где начинающий проигрывает. Похожий, но ещё более хитрый ход есть у 1-го игрока и при $n=4k+3$‍.‍ Здесь он может отрезать три точки так, чтобы сохранилась симметрия относительно оси — для этого достаточно соединить чёрные точки с номерами $2k+1$‍‍ и $2k+3$‍‍ (рис. 3).

Если мысленно сдвинуть оставшиеся $4k$‍‍ точек так, чтобы они расположились по окружности на равных расстояниях, то диаметрально противоположные точки будут разного цвета (хотя белые и чёрные точки и не чередуются), и потому начинающий здесь (т. е. 2-й игрок) проигрывает.

Более тонких соображений требует тот вариант игры, в котором игрок, делающий последний ход, проигрывает. Разбор этого варианта мы предоставляем читателям.

В. Г. Чванов


Метаданные Задача М1098 // Квант. — 1988. — № 4. — Стр. 27; 1988. — № 8. — Стр. 36—37.

Предмет
Математика
Условие
Решение
Номера

1988. — № 4. — Стр.  [условие]

1988. — № 8. — Стр.  [решение]

Описание
Задача М1098 // Квант. — 1988. — № 4. — Стр. 27; 1988. — № 8. — Стр. 36‍—‍37.
Ссылка
https://www.kvant.digital/problems/m1098/