Два игрока

[lexus c.]

Предложу ещё одну задачку олимпиадного толка, которую пока не решил сам (подозреваю, что решаться она должна довольно просто в техническом, но чуть сложнее в идейном плане):

На плоскости нарисовано несколько точек. Двое по очереди соединяют их отрезками. Отрезки могут выходить из одной точки, но не должны пересекаться. Кто не может сделать ход, проигрывает. Доказать, что при любых ходах игроков победителем будет один и тот же, а кто именно - определяется лишь начальной позицией.

[maxal]

Эта задача справедлива как для прямолинейных отрезков, так и для криволинейных. Только требуются некоторые уточнения: нельзя проводить отрезок проходящий через какую-то из нарисованных точек; в криволинейном случае каждые две точки разрешается соединять только одним отрезком (иначе можно играть до бесконечности уже с двумя точками), а также нельзя соединять точку саму с собой.

Решение.

Случаи одной и двух точек очевидны, предположим, что нарисовано как минимум 3 точки.

Назовем гранью область (в том числе неограниченную), границей которой являются проведенными игроками отрезками, внутри которой нет других отрезков. Понятно, что внутри грани не может быть нарисованных точек, так как в противном случае игра неокончена. Понятно также, что каждая грань представляет собой (прямолинейный или криволинейный) треугольник, так как в противном случае какие-то две из его вершин не будут соединены, и их можно соединить, то есть игра опять же неокончена.

Пусть $n$ - число заданных точек, $m$ - число проведенных игроками отрезков и $f$ - число всех граней.

Криволинейный случай: Так как каждая грань ограничена тремя криволинейными отрезками, в то время как каждый отрезок является границей в точности двух граней, то $3f=2m$ или $f=\frac{2m}{3}$. Согласно эйлеровой характеристике плоскости, имеем: $n-m+f=2$, откуда следует, что $m=3(n-1)-6$. Таким образом, первый игрок выигрывает, если $n$ четно, и проигрывает, если $n$ нечетно.

Прямолинейный случай: Рассмотрим выпуклую оболочку нарисованных точек. Понятно, что она состоит из отрезков, которые будут нарисованы при любой игре. Пусть $k$ - число точек на границе выпуклой оболочки. Так как каждая грань, за исключением внешней для выпуклой оболочки, ограничена тремя отрезками, в то время как каждый отрезок является границей в точности двух граней, то $3(f-1)+k=2m$ или $f=\frac{2m-k}{3}+1$. Согласно эйлеровой характеристике плоскости, имеем: $n-m+f=2$, откуда следует, что $m=3n-k-3$. Таким образом, первый игрок выигрывает, если $n+k$ четно, и проигрывает, если $n+k$ нечетно.

[lexus c.]

maxal, отрезки - обязательно прямолинейные. И в этом случае их кол-во изменяется по сравнению с "криволинейным случаем": взять хотя бы точки, расположенные в вершинах квадрата. В прямолинейном случае отрезков будет 5, а в криволинейном - 6, при этом для трёх точек, не лежащих на одной прямой, в обоих случаях получаем 3 отрезка.

[maxal]

Добавил решение для прямолинейного случая.

[lexus c.]

Понятно, большое спасибо )

[незваный гость]

Вам может быть интересно посмотреть игру Бюссельская капуста (описана в одной из книжек Мартина Гарднера)

[lexus c.]

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

[maxal]

Вот, кстати, популярная брошюрка об эйлеровой характеристике:
Шашкин Ю. А. "Эйлерова характеристика."

[lexus c.]

maxal писал(а):

Вот, кстати, популярная брошюрка об эйлеровой характеристике:
Шашкин Ю. А. "Эйлерова характеристика."

Спасибо, будем читать )

[lexus c.]

maxal, кстати, в криволинейом случае внешняя грань будет ограничена двумя отрезками, а не тремя )

[maxal]

lexus c. писал(а):

maxal, кстати, в криволинейом случае внешняя грань будет ограничена двумя отрезками, а не тремя )

Как вы себе это представляете? У двух отрезков не может быть меньше трех различных концов - в противном случае либо отрезки соединяют одни и те же точки, либо какую-то точку саму с собой, а это все запрещено правилами.

[lexus c.]

Простите, да, я забыл об оговорке, согласно которой, две точки соединяются только одним отрезком.