Задача из теории игр — 2 | Логические задачи

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

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

Задача из теории игр — 2 | Логические задачи: 3 комментария

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *