Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the board game Hex, players take turns coloring hexagons either red or blue. One player tries to connect the top and bottom edges of the board, colored red; the other tries to connect the left and right edges, colored blue. It is known that a game of Hex will never end in a tie: no matter how it is played, there will always be either a blue path connecting the blue edges, or a red path connecting the red edges.

My question is, if this fact always holds for a finite grid of hexagons, does it also hold on the plane? If the top and bottom edges of a square are colored red, the left and right edges are colored blue, and the interior of the square is colored arbitrarily, must there be either a red path connecting the red edges, or a blue path connecting the blue edges?

More formally, let $S$ be any subset of $[0, 1]^2$. $S$ will represent the points that are red. Must there be either a path within $S$ whose endpoints are of the form $(x, 0)$ and $(x, 1)$, or a path within $[0, 1]^2 - S$ whose endpoints are of the form $(0, y)$ and $(1, y)$?

share|improve this question
add comment

3 Answers

up vote 15 down vote accepted

If the path is required to be continuous, the answer is no.

Since $[0,1]$ is separable, there are only $2^\omega$ continuous functions from $[0,1]$ into $[0,1]^2$; enumerate those that yield paths connecting opposite sides of the square as $\{\varphi_\xi:\xi < 2^\omega\}$. For $\xi < 2^\omega$ recursively choose points $p_\xi,q_\xi \in [0,1]^2$ as follows. Suppose that $\eta < 2^\omega$, and points $p_\xi$ and $q_\xi$, all distinct, have been chosen for all $\xi<\eta$. Clearly $$|\{p_\xi:\xi<\eta\}\cup\{q_\xi:\xi<\eta\}| < 2^\omega,$$ but $|\operatorname{ran}\varphi_\eta| = 2^\omega$, so we may choose distinct points $$p_\eta,q_\eta \in \operatorname{ran}\varphi_\eta \setminus \left(\{p_\xi:\xi<\eta\}\cup\{q_\xi:\xi<\eta\}\right),$$ and the construction goes through to $2^\omega$.

Now color the points of the set $\{p_\xi:\xi < 2^\omega\}$ blue and those of the set $\{q_\xi:\xi < 2^\omega\}$ red; any remaining points of $[0,1]$ may be colored either blue or red. Then every continuous path in the unit square passes through at least one point of each color.

share|improve this answer
You meant: Now color the points of the set $\{p_\xi:\xi<2^ω\}$ blue and those of the set $\{q_\xi:\xi<2^ω\}$ red. –  Álvaro Lozano-Robledo Aug 22 '11 at 1:51
@Álvaro: I sure did. Thanks. –  Brian M. Scott Aug 22 '11 at 1:54
@Tanner: Your understanding of the idea of the proof is basically right, except that it’s not as simple as countable versus uncountable: unless one assumes the Continuum Hypothesis, there may be many uncountable cardinalities less than $2^\omega$. It’s simply the difference between less than $2^\omega$ and $2^\omega$. (And it now occurs to me that you may be more familiar with $2^\omega$ under its alias $\mathfrak{c}$.) –  Brian M. Scott Aug 22 '11 at 3:09
@Brian, I guess my confusion about $2^\omega$ is one of notation. In the notation Wikipedia uses, $2^\omega$ is an ordinal number (equal to $\omega$), not a cardinal number. I know the cardinal number as $2^{\aleph_0}$. But yes, I can see that I was mistaken in assuming the Continuum hypothesis, and that it is just about the difference between less-than-$2^\omega$ and $2^\omega$. –  Tanner Swett Aug 22 '11 at 3:24
@Brian: This relies heavily on the axiom of choice. What if we assume the axiom of determinacy instead? –  Asaf Karagila Aug 22 '11 at 6:09
show 7 more comments

An answer to this came to me today as I was thinking about how I might describe connectedness to a layperson. Path-connectedness is easy enough: a set is path-connected if, given two points in the set, you can get from one to the other by following a path within the set. If I'm not mistaken, connectedness in the plane can be defined like so: a set is connected if you can't draw a curve separating the set into two parts, such that the curve lies entirely outside the set.

So, if we have an example of a set that is connected but not path-connected, we ought to be able to make it into a counterexample. And sure enough, the topologist's sine curve seems to do the trick. Let $S$ be the graph of the function

$$f(x) =\frac12 + \frac14 \sin \left (\frac{1}{x - 1/2} \right), \text{ if $x \ne 1/2$}; \qquad 1/2, \text{ otherwise}.$$

Since this function is not continuous (and its graph is not path-connected), it is impossible to go from the left edge to the right edge while staying inside $S$. But since the function's graph is connected, it is impossible to go from the top edge to the bottom edge while staying outside the function—if this were possible, we would be able to separate the graph into the part to the left of the curve, and the part to the right of the curve, showing that the graph is disconnected.

share|improve this answer
add comment

It is even true that $I^{2}$ may be represented as an union of two closed sets $S_{1}$ and $S_{2}$ none of them containing a topological arc connecting two opposite sides of the square. Here is a possible example.

Let $D$ be a closed disk in the interior of $I^{2}$ , take 4 disjoint topological spirals $J_{i}$ lying in $I^{2}$ and homeomorphic to $[0,\infty)$, each of them beginning from a different side of the square and spiralling around $D$ in such a way that $\overline{J_{i}}=J_{i}\cup\partial D$. Now thicken slightly each $J_{i}$ to get some $J_{i}^{\prime}\supset J_{i}$ homeomorphic to a closed half-plane so that the $J_{i}^{\prime}$ are still disjoint and spiralling around $D$. [$\overline{J_{i}^{\prime}}=J_{i}^{\prime }\cup\partial D$.] To get the claimed representation of the square, it suffices to set $S_{1}=(\cup_{i=1}^{4}J_{i}^{\prime})\cup D$ and $S_{2}=\overline {I^{2}\backslash S_{1}}$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.