Sim - это игра с карандашом и бумагой, в которую играют два игрока.
Геймплей [ править ]
Нарисовано шесть точек («вершин»). Каждая точка соединена с каждой другой точкой линией («краем»).
Два игрока по очереди раскрашивают неокрашенные линии. Один игрок окрашивает в один цвет, а другой - в другой, при этом каждый игрок пытается избежать создания треугольника, состоящего исключительно из его цвета (учитываются только треугольники с точками в качестве углов; пересечения линий не имеют значения); игрок, завершивший такой треугольник, немедленно проигрывает.
Анализ [ править ]
Теорию Рэмси также можно использовать, чтобы показать, что ни одна игра Сима не может закончиться ничьей. В частности, поскольку число Рамсея R (3,3) = 6, любая двукратная раскраска полного графа на 6 вершинах (K 6 ) должна содержать монохроматический треугольник и, следовательно, не является связанной позицией. Это также применимо к любому суперграфу K 6 . Еще одно доказательство того, что в конечном итоге должен быть треугольник любого цвета, можно найти в Теореме о друзьях и незнакомцах .
Компьютерный поиск подтвердил, что второй игрок может выиграть Сима безупречной игрой, но найти идеальную стратегию, которую люди могут легко запомнить, - открытая проблема. [1]
Игра Сима - один из примеров игры Рэмси. Возможны и другие игры Рэмси. Например, игрокам может быть разрешено раскрашивать более одной линии во время своего хода. Другая игра Рэмси, похожая на Сима и связанная с числом Рэмси R (4,4) = 18, которая снова не может закончиться ничьей, проводится на 18 вершинах и 153 ребрах между ними. Двое игроков должны избегать раскрашивания монохроматического тетраэдра (трехмерной пирамиды с четырьмя треугольными гранями).
Из числа Рамсея R (3,3,3) = 17 следует, что любая трехцветная раскраска полного графа на 17 вершинах должна содержать одноцветный треугольник. В соответствующей игре Рамсея используются карандаши трех цветов. В одном подходе могут соревноваться три игрока, в то время как другой позволяет двум игрокам поочередно выбирать любой из трех цветов, чтобы нарисовать край графа, пока игрок не проиграет, завершив монохроматический треугольник. Найти идеальные выигрышные стратегии для этих вариантов, скорее всего, невозможно.
Технический отчет [2] Вольфганга Слэни доступен в Интернете, со многими ссылками на литературу по Sim, начиная с введения в игру Густавом Симмонсом в 1969 году, [3] включая доказательства и оценки сложности, а также вычислительной сложности Sim. и другие игры Рэмси.
Программное обеспечение [ править ]
Самоулучшающийся Java-апплет, включая его исходный код, доступен [4] для онлайн-игры с компьютерной программой.
Доступно приложение, включающее его исходный код на визуальном мультиплатформенном языке программирования Catrobat [5], для игры в него против своего смартфона.
Электронная версия доступна по адресу: https://wideaperture.net/sim/
Ссылки [ править ]
- ^ Мид, Эрнест; Роза, Александр; Хуанг, Шарлотта (1974-11-01). «Игра Сима: выигрышная стратегия для второго игрока» . Математический журнал . 47 (5): 243. DOI : 10,2307 / 2688046 . ISSN 0025-570X .
- ^ Graph Ramsey Games от Вольфганга Слэни на arXiv
- ^ Симмонс, Густав Дж. «Игра SIM», J. Развлекательная математика , 2 (2), 1969, стр. 66.
- ^ Страница Java-апплета, включая исходный код
- ^ Приложение для смартфонов, включая исходный код
