Editing Sim (game)

{{Short description|Two-player paper-and-pencil game}}
{{distinguish|The Sims}}
[[File:Complete graph K6.svg|thumb|The playing area]]
'''Sim''' is a two-player [[paper-and-pencil game]].

==Gameplay==
Six dots ([[Vertex_(graph_theory)|vertices]]) are drawn.  Each dot is connected to every other dot by a line ([[Edge_(graph_theory)|edge]]).

Two players take turns coloring any uncolored lines.  One player colors in one color, and the other colors in another color, with each player trying to avoid the creation of a triangle made solely of their color (only triangles with the dots as all corners count; intersections of lines are not relevant); the player who completes such a triangle loses immediately.

==Analysis==
[[Ramsey theory]] can also be used to show that no game of Sim can end in a tie.  Specifically, since the ''[[Ramsey number]]'' ''R''(3, 3) is equal to 6, any two-coloring of the [[complete graph]] on 6 vertices (''K''<sub>6</sub>) must contain a monochromatic triangle, and therefore is not a tied position.  This will also apply to any super-graph of ''K''<sub>6</sub>. For another proof that there must eventually be a triangle of either color, see the [[Theorem on friends and strangers]].

Computer search techniques verified in 1974 that the second player can win Sim with perfect play.<ref>{{Cite journal|last1=Mead|first1=Ernest|last2=Rosa|first2=Alexander|last3=Huang|first3=Charlotte|date=1974-11-01|title=The Game of Sim: A Winning Strategy for the Second Player|url=http://dx.doi.org/10.2307/2688046|journal=Mathematics Magazine|volume=47|issue=5|pages=243|doi=10.2307/2688046|jstor=2688046 |issn=0025-570X|url-access=subscription}}</ref> A strategy that could be easily implemented by human players was found in 2020.<ref>{{Cite arXiv|last1=Wrzos-Kaminska|first1=Weronika|date=2020-09-01|title=A simpler winning strategy for Sim|eprint=2001.04024}}</ref>

The game of Sim is one example of a Ramsey game. Other Ramsey games are possible. For instance, the players can be allowed to color more than one line during their turns. Another Ramsey game similar to Sim and related to the Ramsey number ''R''(4, 4) = 18 is played on 18 vertices and the 153 edges between them. The two players must avoid to color all six edges connecting four vertices.

Because the Ramsey number ''R''(3, 3, 3) is equal to 17, any three-coloring of the complete graph on 17 vertices must contain a [[monochromatic]] triangle. A corresponding Ramsey game uses pencils of three colors. One approach can have three players compete, while another would allow two players to alternately select any of the three colors to paint an edge of the graph, until a player loses by completing a monochromatic triangle. Finding perfect winning strategies for these variants is most likely out of reach.

A technical report<ref name="sim-technical-report">{{Cite arXiv|last=Slany|first=Wolfgang|date=1999-11-10|title=Graph Ramsey games|eprint=cs/9911004 }}</ref> by Wolfgang Slany is available online, with many references to literature on Sim, going back to the game's introduction by [[Gustavus Simmons]] in 1969,<ref>Simmons, Gustavus J. "The game of SIM," ''J. Recreational Mathematics'', 2(2), 1969, pp. 66.</ref> including proofs and estimates of the difficulty as well as [[Computational complexity theory|computational complexity]] of Sim and other Ramsey games.

==Software==

An app including its source code in the visual multi-platform [[Catrobat]] programming language is available<ref name="sim-smartphone-app">{{Cite web|title=Catrobat community|url=https://share.catrob.at/pocketcode/program/1478|access-date=2023-02-18|website=share.catrob.at|language=en}}</ref> for playing it against one's smartphone.

==References==
{{reflist}}



[[Category:Ramsey theory]]
[[Category:Mathematical games]]
[[Category:Combinatorics]]
[[Category:Combinatorial game theory]]
[[Category:Paper-and-pencil games]]
[[Category:Solved games]]
[[Category:Positional games]]