Логические задачи → Задача из теории игр - 2

21 мая 2010 | Добавил: SoVictor

На окружности отмечено 2n >= 6 точек. Двое игроков ходят по очереди. На каждом ходе игрок должен провести хорду, соединяющую две точки и не пересекающуюся ни с одной из уже проведённых хорд. Проигрывает тот, кто не может сделать хода.

Какой игрок выигрывает при правильно игре?

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Версия для печати.
RSS комментариев записи.

Метки → логические, теория игр

Комментариев: 3

nogard пишет:
21 мая 2010 в 14:20

Рассмотрим два случая.
1) Точки лежат в местах касания данной окружности, вписанного правильного 2n угольника.
Выигрывает первый игрок. Его стратегия:
* первым ходом соединяем какой-нить диаметр (из свойст 2n угольников это можно сделать)
* на любой ход оппонента в одну из половинок отвечаем симметричным ходом в другую (думаю, что понятно, что это всегда можно сделать)
* пусть случилось так, что первый не может ходить, но в силу симметрии получается, что ходом раньше не мог сходить оппонент, а значит он проиграл.
2) Точки разбросаны рандомом.
Все равно выиграет первый игрок.
Все дело в том, что у него есть волшебный листок. "Волшебность" листка заключается в том, что там точки на круге выглядят немного подругому.
Пронумеруем точки игрового поля, начиная с любой и обозначив ее 1, и далее по часовой стрелке (можно и против, это не принципиально). На листочке эти точки расположены в местах касания данной окружности, вписанного правильного 2n угольника (точки пронумерованы аналогично). Собственно первый игрок играет по той же схеме, что и в 1 пункте, но только на листочке. Далее он свои ходы переносит на игровое поле.
Очевидно, что легитимность ходов сохраняется - это видно из соответствия номеров обоих окружностей.

Если без ухищрений объяснять, то первый игрок проводит хорду так, чтобы по обе стороны от хорды было равное количество точек, а именно (n-1). Но для такой стратегии несколько сложнее объяснять понятие симметрично и доказательство провести несколько сложнее, хотя опять-таки нумерация помогает.
SoVictor пишет:
21 мая 2010 в 21:42

Достаточно было последнего абзаца.
Китана пишет:
14 июня 2010 в 16:25

А можно n>2, и первый игрок всегда будет выигрывать, если первый ход сделает произвольно, а во всех следующих:
1) если есть два смежных ребра, между которыми нет никаких хорд, то достроить их до треугольника
2) если нет таких ребер, то соединить любые два графа