Где ошибка?

[Rusit8800]

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

Она уже встречалась на форуме в данной теме topic11719.html. Но то решение оказалось куда сложнее моего, да и еще использовало понятия из вычислительной геометрии(я уж не говорю о том, что ответ не совпал). Моя идея состоит в следующем: игра заканчивается, если многоугольник триангулирован, значит побеждает тот, кто завершил его триангуляцию. Но количество проведенных сторон - нечетное число, поэтому побеждает всегда второй игрок.

[Slav-27]

Какой ещё многоугольник?

[Rusit8800]

Slav-27 в сообщении #1204424 писал(а):

Какой ещё многоугольник?

Образованный точками

[AV_77]

Здесь побеждает первый

$$ \xymatrix{ \circ \ar@{-}[rr]_1 \ar@{-}[rd]_2 & & \circ \ar@{-}[ld]_1 \\ & \circ & } $$

а здесь - второй

$$ \xymatrix{\circ \ar@{-}[dd]_1 \ar@{-}[rr]_2 \ar@{-}[dr]_1 & & \circ \ar@{-}[ld]_2 \ar@{-}[dd]_1 \\ & \circ & \\ \circ \ar@{-}[ru]_2 \ar@{-}[rr]_1 & & \circ \ar@{-}[lu]_2 } $$

[Rusit8800]

1) В каком порядке делались ходы?
2) Я рассматривал случай, когда точек больше 3, так как треугольник триангулировать нельзя

(Оффтоп)

3) Как вы сделали этот рисунок?

[Slav-27]

Rusit8800 в сообщении #1204427 писал(а):

Образованный точками

Ну хорошо, предположим, что имеется в виду выпуклая оболочка нарисованных точек. Но ведь может быть, что не все нарисованные точки оказались вершинами этого многоугольника: смотрите 2-й пример AV_77. Проведённых отрезков там чётное число.

[AV_77]

Rusit8800 в сообщении #1204438 писал(а):

1) В каком порядке делались ходы?

Порядок ходов (проведения ребер) здесь не важен. Около каждого ребра стоит номер игрока, который его проводит.

Rusit8800 в сообщении #1204438 писал(а):

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

Если нужно больше трех, то такой вариант с победой первого игрока подойдет:

$$ \xymatrix{ \circ \ar@{-}[r]_1 \ar@{-}[d]_2 \ar@{-}[rd]_1 & \circ \ar@{-}[d]_2 \\ \circ \ar@{-}[r]_1 & \circ } $$

А чтобы посмотреть как делался можно нажать на кнопку "цитата" и посмотреть код. Окружение xymatrix

[Rusit8800]

AV_77 в сообщении #1204450 писал(а):

Порядок ходов (проведения ребер) здесь не важен

Как же? Если в первом случае начинает первый, то он выигрывает, иначе, второй

[Someone]

(Rusit8800)

Rusit8800 в сообщении #1204438 писал(а):

3) Как вы сделали этот рисунок?

Объяснения: http://dxdy.ru/post169421.html#p169421.
Подробнее: http://dxdy.ru/topic35475.html.

[arseniiv]

Rusit8800 в сообщении #1204467 писал(а):

Если в первом случае начинает первый, то он выигрывает, иначе, второй

Тогда он будет уже не вторым, а первым.

[AV_77]

Rusit8800 в сообщении #1204467 писал(а):

Если в первом случае начинает первый, то он выигрывает, иначе, второй

А, вот вы о чем. Мне казалось понятным, что первый игрок потому и называется "первым", что он первым ходит. Так что если второй будет ходить первым, то, как справедливо было сказано,

arseniiv в сообщении #1204477 писал(а):

он будет уже не вторым, а первым.

[Rusit8800]

Похоже я не правильно подсчитал количество сторон для триангуляции. Я хоть прав, что побеждает тот, кто ее завершает?

[Rusit8800]

То есть, если $P$ - количество сторон триангуляции, то первый игрок побеждает только в том случае, если $P$ нечетно. Так?

[slavav]

Пусть $N$ - число точек в множестве $S$. Пусть $K$ - число точек множества $S$ на границе выпуклой оболочки $S$. Тогда число рёбер в любой триангуляции $S$ равно $3N - K - 3$. Это первое.
Второе: если вы на этом множестве точек построили планарный граф, и число рёбер в этом графе меньше $3N - K - 3$, то к нему можно добавить ребро сохраняя планарность.
Отсюда следует что исход игры не зависит от порядка ходов игроков и определяется только парой $(N, K)$.

[Rusit8800]

Получается, что если $3N - K - 3$ нечетно, то выигрывает первый, а если четно, то он проигрывает?