Sim (pencil game)

The game of Sim is played by two players, Red and Blue, on a board consisting of six dots ('vertices'). Each dot is connected to each other with a line.

Two players take turns coloring any uncolored lines. One player colors in red, and the other colors in blue, with each player trying to avoid the creation of a triangle made solely of their color; the player who completes such a triangle loses immediately.

Ramsey theory shows that no game of Sim can end in a tie. Specifically, since the "Ramsey number" "R"(3,3;2)=6, any two-coloring of the complete graph on 6 vertices (K₆) must contain a monochromatic triangle, and therefore is not a tied position. This will also apply to any super-graph of K₆.

Computer search has verified that the second player can win Sim with perfect play, but finding a perfect strategy that humans can easily memorize is an open problem.

A Java applet [ [http://www.dbai.tuwien.ac.at/proj/ramsey/ Java applet at the Vienna University of Technology] ] is available for online play against a computer program. A technical report [ [http://arxiv.org/format/cs.CC/9911004 "Graph Ramsey Games" by Wolfgang Slany] ] by Wolfgang Slany is also available online, with many references to literature on Sim, going back to the game's introduction by Gustavus Simmons in 1969.

The game Sim is one example of a Ramsey game. Other Ramsey games are possible. For instance, according to Ramsey theory any three-coloring of the complete graph on 17 vertices must contain a monochromatic triangle. The corresponding Ramsey game uses pencils of three colors. The two players alternately color an edge of the graph, using any color they want to, until a player loses by completing a mono-chromatic triangle. It is unknown whether this game is a first or a second player win.

External links