![]() ![]() Hex’s board can be considered a graph in many ways. Therefore graph Gₖ, where every vertex has degree 2 with k edges and for all k, 0 ≤ k ≤ N, is a union of disjoint components of isolated vertices, simple cycles, and simple paths. Adding the edge ( x, y) back in will keep the graph as a set of disjoint vertices, simple cycles, and simple paths. Since every vertex in Gₙ₊₁ had at most 2 edges initially, the vertices x and y now have at most 1 edge. Given graph Gₙ₊₁, with n + 1 vertices of degree at most 2, we randomly choose an edge ( x, y) to remove, thereby creating a graph Gₙ, which meets the definition from Lemma 1. By assumption, Gₙ is a union of disjoint vertices, simple cycles, and simple paths. With the base case, G₀, there are N vertices and 0 edges, meaning it is a graph of only isolated vertices. Let k be the number of edges in a graph Gₖ. Given a graph G with N vertices, where each vertex has degree at most 2, the maximum number of edges is N by Lemma 1. We can use a proof by induction for this. Lemma 2: Any finite graph where a vertex has a degree of at most 2 is a union of disjoint components, and each component is either (A) an isolated vertex, (B) a simple cycle, or (C) a simple path.By summing the edges (a sequence of N terms), we have 2 + 1 + 1 + … + 0 = N. These added edges to the 2 connected vertices will force one edge in two more vertices and will repeat until the Nth vertex, which must already be connected by 2 edges. From the two vertices now connected by edges to the starting vertex, only one edge can be added so that the degree remains at most 2. Given any arbitrary set of N vertices, in order to have the maximum number of edges where each vertex had a degree of at most 2, the starting vertex would first be given two edges. Lemma 1: A graph with N vertices, each with degree at most 2, will have at most N edges.First, we must prove some lemmas about graphs: This is the Hex Theorem, and can be proved by thinking of Hex as a planar graph, in which a vertex is a corner of a cell’s border. The corner cells are considered parts of both sides and can be used to complete a chain for either color.įigure 1: A partially-filled 11×11 Hex board Proving the Hex TheoremĪ game of Hex cannot end in a draw. The winner of the game is the first person to connect their corresponding ends of the board in an unbroken chain of their colored tiles. They alternate turns placing their respectively colored tile into an empty hexagonal slot. Opposite pairs of the sides of the board are colored white and black, denoting the starting and ending sides for the two players, who are also labeled as player “A” (white) or “B” (black). The most common sized board is 11×11 (Figure 1), but other sizes such as 13×13 are also popular. ![]() The game of Hex is traditionally played on an n× n parallelogram-shaped board of hexagons. We also showed why the first player always has a distinct advantage during perfect play, using logic and graph theory. We investigated one defining feature of Hex: that a win is forced, meaning one player is guaranteed to win. The game became referred to as either “Nash” (from John Nash’s name) or “John” (because it was commonly played on the school’s hexagonal bathroom tiles a john is another name for a toilet) at Princeton, but it soon became widely known as “Hex” when marketed by Parker Brothers, Inc. After discussing the game with one of his instructors, the two revised it into the version Hein had invented. His first version of the game used squares, where a cell is adjacent to another cell if it shares an edge or corner with it. ![]() John Nash reinvented the game while studying at Princeton University. After lecturing on it at the Institute for Theoretical Physics in Denmark, the newspaper Politiken popularized the game by publishing an article about it with the name “Polygon.” Hein initially came up with the game while thinking about the four-color theorem of topology (where any map on a plane can be colored with at least 4 colors such that no countries with a common border have the same color). Image by Galen on Unsplash What is Hex, and where did it come from?įirst invented in 1942 by Piet Hein and independently reinvented in 1948 by John Nash, Hex is a two-player strategy board game that has interested mathematicians for a long time. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |