Сим (игра)
Из Википедии, свободной энциклопедии
Из Википедии, свободной энциклопедии
Сим — топологическая игра, заключающаяся в том, что два игрока по определённым правилам проводят линии на плоскости.
Перед началом игры на окружности (нарисованной или воображаемой) ставят несколько (обычно 6) точек.
Затем игроки по очереди ходят.
Каждый ход игрока состоит в том, что он проводит отрезок, соединяющий две из поставленных на окружности точек. Отрезки, проводимые разными игроками, различаются между собой: например, один игрок проводит красные, а другой — синие. Повторно соединять уже соединённые одним из игроков точки нельзя.
Проигрывает тот игрок, после хода которого образуется треугольник со сторонами, проведёнными этим игроком (треугольники, образовавшиеся в результате пересечения отрезков не в точках, поставленных перед игрой на окружности, не учитываются).
Пусть на поле с 6 точками оба игрока сделали по 7 ходов (не важно, в каком порядке): красные — AB, AE, AF, BD, CD, CE, CF; синие — AC, AD, BC, BE, BF, DE, DF (см. рис.). Остался единственный возможный ход — EF, который вынужден сделать игрок, ходивший первым, и которым он проигрывает, так как если ход красных, то будут построены треугольники AEF и CEF, а если синих — BEF и DEF.
Собственно, располагать соединяемые игроками точки по окружности не обязательно, так как ни взаимное расположение точек, ни прямолинейность соединяющих их отрезков не имеют значения, поэтому можно рассматривать игру на полном графе: проводимые игроками отрезки — его рёбра, а соединяемые точки — его вершины. Игроки по очереди выбирают (окрашивают в свой цвет) рёбра, ещё не выбранные ни одним из игроков с начала игры. Проигрывает игрок, после хода которого образуется цикл длины 3, состоящий из рёбер, выбранных этим игроком.
Например, в Hexi[1] — компьютерной реализации игры Сим с 6 вершинами — после каждого хода вершины полного графа, на котором происходит игра, перемешиваются (такое поведение можно отключить в настройках), что показывает несущественность способа вложения графа в плоскость или пространство.
Игра изобретена и описана в 1969 году Густавом Симмонсом[2], от его фамилии и произошло название игры.
При раскраске рёбер полного графа с n вершинами в k цветов треугольник (цикл длины 3, полный подграф с тремя вершинами) с рёбрами одного цвета может отсутствовать, только если число Рамсея .
Поэтому при игре двух участников с 6 и более точками ничейный исход невозможен, так как .
Сим является детерминированной игрой с полной информацией. Исследование игры с 6 точками, проведённое с помощью ЭВМ её изобретателем, показало, что у второго игрока имеется выигрывающая стратегия[3]. В статье Сергея Мельникова в журнале «Наука и жизнь» сообщается, что проведённое автором подобное исследование игры с 7 точками показало, что и в этом случае у второго игрока есть выигрывающая стратегия[4].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
