Сим

Сим, как и многие другие игры, о которых рассказывается в этой книге, очень молодая игра. Изобрел ее во время работы над своей диссертацией Г. Симмонс, специалист по теории графов, от имени которого и происходит ее название. Как и "рассада", сим - игра с очень простыми правилами. Для того чтобы играть в нее, не требуется ничего, кроме листа бумаги и двух карандашей разных цветов.

Сначала на бумаге рисуется окружность, на которой расставляется несколько точек. Это исходная позиция игры. Играют двое, делая ходы по очереди. Ход состоит в том, что игрок соединяет какие-нибудь две еще не соединенные точки отрезком своего цвета. Если в результате какого-то хода образовался треугольник, все стороны которого имеют один цвет, то игроку, сделавшему этот ход, засчитывается поражение. Если проведены всевозможные отрезки, соединяющие исходные точки (их, очевидно, ровно N×(N-1)/2, где N - число исходных точек), и при этом одноцветных треугольников не возникло, партия считается закончившейся вничью.

Очевидно, игра имеет смысл только при числе точек на окружности больше двух. При трех точках игра тривиальным образом заканчивается вничью. Легко видеть, что и при четырех исходных точках правильный результат партии (т. е. результат при отсутствии ошибок игроков) ничейный. При пяти точках ничья возможна (пример приведен на рис. 19, где отрезки, проведенные первым игроком, выделены пунктиром), но не доказано, что она достигается, если оба игрока будут действовать наилучшим образом. При более чем пяти точках ничья уже невозможна, что легко доказывается при помощи теории графов. Симмонсу удалось показать (при помощи ЭВМ), что если число исходных точек равно шести, то второй игрок может добиться победы независимо от действий противника (т. е. он имеет выигрывающую стратегию, как говорят специалисты по теории игр). Если число исходных точек больше шести, правильный результат партии неизвестен.

Рис. 19