Сим (игра)

Sim — это игра для двух игроков, в которую можно играть карандашом и бумагой .

Нарисовано шесть точек ( вершин ). Каждая точка соединена с каждой другой точкой линией ( ребром ).

Два игрока по очереди раскрашивают любые неокрашенные линии. Один игрок раскрашивает в один цвет, а другой — в другой, при этом каждый игрок старается избежать создания треугольника, состоящего исключительно из его цвета (учитываются только треугольники с точками в качестве углов; пересечения линий не имеют значения); игрок, который завершит такой треугольник, немедленно проигрывает.

Теорию Рамсея можно также использовать для того, чтобы показать, что ни одна игра в Sim не может закончиться вничью. В частности, поскольку число Рамсея R (3, 3) равно 6, любая двухцветная раскраска полного графа на 6 вершинах ( K ₆ ) должна содержать одноцветный треугольник, и, следовательно, не является ничьей. Это также будет применимо к любому суперграфу K ₆ . Для другого доказательства того, что в конечном итоге должен быть треугольник любого цвета, см. Теорему о друзьях и незнакомцах .

Компьютерный поиск подтвердил, что второй игрок может выиграть Sim при идеальной игре, но поиск идеальной стратегии, которую люди могут легко запомнить, остается открытой проблемой. ^[1]

Игра Sim является одним из примеров игры Ramsey. Возможны и другие игры Ramsey. Например, игрокам может быть разрешено раскрашивать более одной линии во время своих ходов. Другая игра Ramsey, похожая на Sim и связанная с числом Ramsey R (4, 4) = 18, играется на 18 вершинах и 153 ребрах между ними. Два игрока должны избегать раскрашивания всех шести ребер, соединяющих четыре вершины.

Поскольку число Рамсея R (3, 3, 3) равно 17, любая трехцветная раскраска полного графа на 17 вершинах должна содержать одноцветный треугольник. Соответствующая игра Рамсея использует карандаши трех цветов. Один подход может предполагать соревнование трех игроков, в то время как другой позволит двум игрокам поочередно выбирать любой из трех цветов для раскрашивания ребра графа, пока игрок не проиграет, завершив одноцветный треугольник. Нахождение идеальных выигрышных стратегий для этих вариантов, скорее всего, недостижимо.

Технический отчет ^[2] Вольфганга Слани доступен в сети, с большим количеством ссылок на литературу по Sim, начиная с введения игры Густавуса Симмонса в 1969 году ^[3] , включая доказательства и оценки сложности, а также вычислительной сложности Sim и других игр Рэмси.

Приложение, включающее исходный код на визуальном мультиплатформенном языке программирования Catrobat, доступно ^[4] для игры на смартфоне.