Categories

Fun with Hex (Cont.)

In the previous post Fun with Hex, I asserted without proof that the Hex Game will never result a draw. In Jiri Matousek’s An Invitation to Discrete Mathematics, I found an elegant proof for the assertion, which requires only a little bit of elementary graph theory. The idea of the proof can also prove Sperner’s Lemma. Moreover, I will present later how to extrapolate this idea to discover something new. The only bit of elementary graph theory we are going to use is the Handshaking lemma.

Lemma (handshaking). Every finite undirected graph has an even number of vertices with odd degree.

To prove the lemma, simply observe that the sum of the degrees of all vertices is equal to twice the number of the edges, which should be even.

Now let us review the Hex Game. Recall two versions of the Hex Game.

The original version of the game is to color the hexagons of the game board (illustrated in black) and each player tries to link the opposite sides of the board with a connected series of hexagons with the same color.

Alternatively, one can play with the Voronoi dual of the hexagon game board (illustrated in red). This time, two players color the vertices and compete to link the opposite sides with a path of vertices of their own color. For instance, player one would try to form a red path from the northwest side to the southeast side, while player two would strive to build a blue one from the northeast side to the southwest side.

We can tilt and rescale the dual graph without changing the game as follows.

In this new graph, the first player wants to build a red path from the west to the east and the second player wants to build a blue path from the north to the south. Furthermore, for purpose of the proof, we add four auxiliary vertices on each side and color them according to which player it belongs to.

As are shown in the above graph, the vertices on the west and the east are red and the ones on the north and the south are blue. Our goal is to prove that no matter how you color the remaining vertices with red and blue, there is always a monochromatic path connecting two of the four auxiliary points. For the coloring below, there is a red path from W to E.

Proof.Assume, for the sake of contradiction, that some coloring does not form any red path from W to E or blue path from N to S. First, for every red vertex unreachable by any red path starting from W, we change it to green. Similarly, for every blue vertex unreachable by any blue path starting from N, we change it to green, too.

Under the assumption that there is no red path from W to E and no blue path from N to S, the vertices E and S are both changed to green. Now we have a triangulated planar graph whose four vertices on the external face, W, N, E, S are colored by red, blue, green, green respectively.

Lemma. Given a 3-coloring on a triangulated planar graph whose four vertices on the external face, say W, N, E, S, are colored by red, blue, green, green respectively. There is an internal triangular face whose vertices are of different color.

By this lemma, we can conclude that there exists an internal triangular face, say ABC, such that A is red, B blue and C green. This implies that there are a red path from W to A and a blue path from N to B. If the vertex C is originally red, then it should still be red because there is an edge between A and C. By the same reason, if it is originally blue, then it should still be blue. This gives a contradiction! To finish the proof for the Hex Game, we only need to prove the lemma.

Proof of Lemma. For each face of the triangulated planar graph, we put a vertex in it. Two vertices are adjacent if and only if their corresponding faces share a common edge whose endpoints are colored red and blue.

Note that the degree of the vertex in the external face is 1. By the handshaking lemma, there is a vertex, say $v$ in the internal face, say $F$, whose degree is odd. It is easy to see the only possible coloring of the vertices of $F$ to get an odd degree of $v$ is to color them by 3 different colors.

Now I am going to show something new. The idea to consider another game board which looks like:

The idea is to get a symmetric board. To build such a game board, one can start with a hexagon in the center and then add several layers of hexagons around it. In the picture above, the hexagon labeled by 1 is the one we start with. We call it the 1st layer. Then we can add 6 hexagons labeled by 2 around it to form the 2nd layer and another 12 hexagons labeled by 3 around the 2nd layer. In general, to build a symmetric Hex of size $n$, one only needs to repeat the process $n$ times.

For this symmetric Hex game board, we have three pairs of opposite sides. One reasonable goal, which is analogous to the goal of the Hex Game, is to build a monochromatic path that links two opposite sides. However two players can cooperate to tie the game in this case.

Therefore, for the symmetric Hex, the goal is to build a monochromatic connected component that touches two opposite sides or three nonadjacent sides. For simplicity, we can such a monochromatic connected component a winning component. In other words, if we label six sides by 1 through 6, both players want to use their own colors to connect side 1 and 4, or side 2 and 5, or side 3 and 6, or side 1, 3 and 5, or side 2, 4 and 6. Again, we will only consider its dual variant in the sense that each player colors the vertex of the following graph.

Proposition. The Symmetric Hex Game can never end in a tie.

Proof. Assume, for the sake of contradiction, that there is a 2-coloring of the symmetric Hex that contains no winning component. Consider the graph with 4 extra vertices W, E, N, S which connect to the vertices of the original graph as follows.

To be specific, W connects to all the vertices on side 5, E the vertices on side 2, N the vertices on side 1 and 6, S the vertices on side 3 and 4.

By the same argument we used in the proof of the Hex Game, there is either a red path from W to E or a blue path from N to S. In other words, we should have one of the following schematic pictures.

By our assumption, it must look like the pictures on the second row. Without loss of generality, assume that we have the first picture on the second row and the blue path connects vertices $a$ and $b$.

Now we change the way the extra 4 vertices connect to the vertices on the boundary as follows.

Again, there is either a blue path from W to E or a red path from N to S. If there is a blue path from W to E, then this path combined with the blue path from $a$ to $b$ gives us a connected component that touches two opposite sides or 3 nonadjacent sides. Therefore it has to be the case that a red path connects N to S.

To summarize, whenever we have a blue path $P_1$ that connects side 4 and 6, there is be a red path $P_2$ connecting the same sides on its right side. By symmetry, there is a blue path $P_3$ connecting side 4 and 6 on $P_2$‘s right side. We can keep going and get an infinite sequence of paths connecting side 4 and 6 with alternating colors, which is impossible!

Corollary. For any 2-coloring of the symmetric Hex board of size $n$, there is a monochromatic connected component of size at least $2n+1$.

Proof. By the symmetric Hex theorem, there is a monochromatic connected component that touches 2 opposite sides or 3 nonadjacent sides. In either case, the size of the component is at least $2n+1$.

Categories

Fun with Hex

According to the folklore,

The Hex game was invented by the Danish mathematician Piet Hein, who introduced it in 1942 at the Niels Bohr Institute. It was independently re-invented in 1947 by the mathematician John Nash at Princeton University. The rules are really simple. Each player has an allocated color, Red and Blue being conventional. Players take turns placing a stone of their color on a single cell within the overall playing board. The goal is to form a connected path of your stones linking the opposing sides of the board marked by your colors, before your opponent connects his or her sides in a similar fashion. The first player to complete his or her connection wins the game. The four corner hexagons each belong to both adjacent sides… The game can never end in a tie, a fact proved by John Nash: the only way to prevent your opponent from forming a connecting path is to form a path yourself. In other words, Hex is a determined game.
– Hex (board game), Wikipedia

For instance, in the following 2 by 2 board, player 1 should intend to build a connected path linking $x_1=0, x_1=2$, while player 2 should intend to build a connected path linking $x_2=0, x_2=2$.

Now, we would like to play Hex game in higher dimensions. The first question is: how can we set up the game board in the $n$ dimensional space? The answer all depends on your point of view. If we visualize the game board in 2 dimension as follows, we can view each cell as a cube in 3 dimensional space.

Here is a rework of the 2 dimensional board which can be easily generalized to higher dimension. Consider all unit cubes in $\mathbb{R}^3$ who are translation of the canonical unit cube (whose vertices are $(0,0,0), (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1),(1,1,1)$) along the vector $(x,y,z)$, where $(x,y,z)\in[n]\times[n]\times\mathbb{Z}$ ($[n]=\{1,2,\ldots, n\}$) and $x+y+z=0$. Basically, those unit cubes are the ones illustrated above. Now project all those cubes to the 2-dimensional plane $x+y+z=0$. This gives us the hexagon board.

For higher dimension, say $d$ dimension, just project all unit cubes in $\mathbb{R}^{d+1}$ who are translation of the $d+1$-dimensional canonical unit cube along the vector $(x_0, \ldots, x_n)$, where where $(x_0,\ldots, x_d)\in\mathbb{Z}^{d+1}$ and $x_0+\ldots+x_d=0$, to the $d$-dimensional hyperplane given by the equation $x_0+\ldots+x_d=0$.
With the help of Mathematica, each cell of 3D Hex board looks like the following.

Source code is attached here for those who want to play with it a little bit in Mathematica.

v = Orthogonalize[{{1, -1, 0, 0}, {0, 1, -1, 0}, {0, 0, 1, -1}}];
data = Flatten[Table[{{x, y, z, t}.v[[1]], {x, y, z, t}.v[[2]], {x, y, z, t}.v[[3]]}, {x, 0, 1}, {y, 0, 1}, {z, 0, 1}, {t, 0, 1}], 3];
`
I forgot to mention, in the $d$-dimensional Hex game, we have at most $d$ players. Again, the game will never tie. For those who are interested beyond this mere fact, please refer to David Gale’s great exposition on this topic [DG] ((David Gale, The Game of Hex and the Brouwer Fixed-Point Theorem, The American Mathematical Monthly, vol. 86, 1979, pp. 818-827)).
Indeed, mathematically speaking, this is the dual diagram of the original board. Its generalization in higher dimension is easy to imagine. Define a graph whose vertex set $V=[n]^d$. Two distinct vertices $u, v\in V$ are adjacent if $u_i-v_i\in\{0,1\}$ for all $i\in[d]$ or the other way around $v_i-u_i\in\{0,1\}$ for all $i\in[d]$.