theJam.ru

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

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

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

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

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

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

  1. nogard пишет:

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

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

  2. SoVictor пишет:

    Достаточно было последнего абзаца.

  3. Китана пишет:

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

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать