Sperner's lemma and paths from one side to the opposite one in a grid

Question

I recently found this nice puzzle:

Given an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares, then we can always find a path using these small diagonals that goes from one side to the opposite one in a grid (up to down or left to right).

First, I would be eager to hear some new approaches. I myself know how to do it using Sperner's Lemma (the triangulations one, of course); however, I'm pretty sure simpler solutions are possible (maybe some induction).

Now, my second question is actually what I'm really interested about: given the existence of a constructive proof of Sperner, we can probably implement an algorithm to get this path that's better than the brute-force one of checking each path manually... so, it's natural to ask what would the best one? (say for the shortest path or something)

If this is known, some references would be great! Thanks.

Answer 1

I have nothing substantive to say, but I thought it might be helpful to include an example of random diagonals, which I have drawn from an earlier MO question, "Shortest grid-graph paths with random diagonal shortcuts":
   

Answer 2

There is an easy proof by exploration. To fix notation, let our grid be $\Lambda=\{k+is:k,s\in \{0,\dots,n-1\}\}$. Given a configuration, define its exploration path to be a nearest-neighbor path on the dual grid $\frac{1}{2}+\frac{i}{2}+\mathbb{Z}^2$, by the following rules:

• We start at the lower left corner; the first step is from $-\frac{1}{2}+\frac{i}{2}$ to $\frac{1}{2}+\frac{i}{2}$;
• At each step, we turn by $90^\circ$ left or right, always bouncing from the corresponding diagonal (i. e., never crossing it transversally).
• if we exit $\Lambda$ through left (respectively, lower) side, we make two right turns (respectively, two left turns) in a row to re-enter it.

Since the procedure is reversible, and there is no way the exploration path can arrive at its starting edge, it never passes the same edge twice. Therefore, it must at some point exit $\Lambda$ either thorough top or right side. On the other hand, if $l_n$ and $r_n$ are the vertices on the left (resp, right) of the $n$-th edge of the exploration process, then we can see by induction on $n$ that they are connected to the left (resp. bottom) side by a diagonal path. The induction step is trivial: either $l_{n+1}=l_n$ and $r_{n+1}$ is connected to $r_n$ by the diagonal we've bounced off, or the other way around. It is easy to see that the induction does not break down when we exit and re-enter through left or bottom side.

Answer 3

This looks very similar to a 45 degree rotated board of the so-called Bridg-it game. About the winning strategy, see https://en.wikipedia.org/wiki/Shannon_switching_game.

But I really don't see how the existence of no draw (<=> there is a through path) would imply the same in your case. Of course in your example there can also be two through paths.

Answer 4

If you know the path exists, you can pick a vertex at random (from a side) and find all the vertices reachable from it pretty quickly. If you don't reach the other side, just color those vertices (and whatever part you closed off).

Then try again. This process will terminate after finitely many steps.

---

Then to show such a path exists in the first place. In the dual graph you get a lamination of the disk. Contract all the inner "stuff" to a point. The boundary is divided into two arcs colored black or white and the an the innermost region must touch two points of the same color. The only exception is when there's a from one pt on the black-white boundary to the other.

I can try to draw a graphic of this... the connected regions must have interesting shapes within the graph of diagonals as well.

---

This is very similar to how you prove that Hex has a winning strategy and it depends on the lattice.

Answer 5

I am using my coloring notation from my previous answer.

In topological dimension theory, there are several equivalent theorems:

1.   n-dim FPP for $\ \Bbb I^n;$

2.   $ \dim(\Bbb I^n)\ \ge\ n;$

3.   there exists a completely regular Hausdorff space $\ X\ $ such that $ \dim(\Bbb X)\ \ge\ n\ $ (where $\ \dim\ $ stands for the covering dimension);
4.   the intersection of the closed separations between the walls of $\ \Bbb I^n\ $ is always non-empty;
5.   6. 7. 8. 9. ...

We may assume that $$ \Bbb I:=[0;1]. $$

The detailed formulation of statement 4 is as follows:

THEOREM (about separators):   Let $\ n\ $ be a positive integer. Let sets $\ G_{-k}\ S_k\ G_k\ \subseteq\ \Bbb I^n\ $ be such that $$\ G_{-k}\cap G_k=\emptyset\qquad\text{and}\qquad S_k\ :=\ \Bbb I^n\setminus(G_{-k}\cup G_k) $$ and

$$ \forall_{k=1}^n\ ( \{x\in\Bbb I^n: x_k=0\}\subseteq G_{-k}\quad \text{and}\quad\{x\in\Bbb I^n: x_k=1\}\subseteq G_{k} ) $$

and $\,\ G_{-k}\,\ G_k\,\ $ are open in $\ \Bbb I^n\ $ (hence $\ S_k\ $ is closed and compact), for every $\ k=1\ldots n.\ $ Then $$ \bigcap_{k=1}^n\,S_k\ \ne\ \emptyset $$ End of separation Theorem

The 2-dimensional case of this theorem about separators is an easy consequence of the statement that all diagonal configurations OP's puzzle admit paths across the discrete square $0..m\times 0..m.$ But this puzzle-theorem has to be formulated in the following precise way:

The Puzzle Theorem:   Every diagonal configuration admits a West-East path of color $\ 0\ $ (black)  or a South-North path of color 1 (white).

End of the puzzle Theorem

Thus let me prove that the above puzzle theorem implies the $2$-dimensional separation theorem.

==========================================

Let $\ (G_{-k}\ S_k\ G_k)\,\ \text{for}\ k=1\ldots n,\ $ be as assumed by the theorem about separators while (proof by contradiction) let

$$ \bigcap_{k=1}^n\,S_k\ =\ \emptyset $$

Let $\ \epsilon>0\ $ be such that also

$$ \bigcap_{k=1}^n\,U_\epsilon(S_k)\ =\ \emptyset $$

where $\ U_\epsilon(A)\ :=\ \bigcup_{a\in A}\,\{p\in\Bbb I^n\,: \ d(p\ a)<\epsilon\} $ for arbitrary non-empty $\ A\subseteq\Bbb I^n,\ $ where $\ d\ $ is the Euclidean distance. Such $\ \epsilon\ $ exists by compactness. Thus $$ \epsilon\ >\ \frac {3\sqrt 2}m\ $$ for certain positive integer $\ m.\ $ Let's enlarge the picture $\ m\ $ times. Now we have cube $\ \Bbb J^n,\ $ where $\ \Bbb J:= [0;m]\ $ in place of the unit $n$-cube. We will keep the same notation $\ (G_{-k}\ S_k\ G_k)\,\ \text{for}\ k=1\ldots n\ $ -- and by the way: $$ n=2 $$ for the present theorem about the puzzle. Anyway, now, for the enlarged picture

$$ \bigcap_{k=1}^n\,U_\epsilon(S_k)\ =\ \emptyset\qquad\text{where} \quad \epsilon > 3\cdot\sqrt 2 $$

Now, paint each grid cell (small closed square) white -- in color 1 -- when it intersects $\ S_1;\ $ and color it black -- in color 0 -- when it intersects $\ S_1;\ $ Because of the starting contrary assumption, there is no contradiction yet now since the intersection of the separators is empty. However, there is no configuration, despite the puzzle-theorem, which extends the given partial configuration over the whole grid. Indeed, as it is now, there is no W-E black path (it would run and be broken by separator $\ S_1)\ $ nor S_N white path (it would run and be broken by separator $\ S_2.$ Remember that such paths would have to touch (to intersect) each of the opposite sides of the grid but the separators don't let it, they would break the path into disjoint portions.

DONE

Answer 6

I'll use the theorem on intersecting separations known from the topological dimension theory.

Consider rectangular $\ (m\!\times\! n)$-grid $\,\ 0..m\times 0..n\ $ -- here, I am applying Perl notation:

$$ x..y\,\ :=\,\ \{k\in\Bbb Z:\, x\le k\le y\} $$

An unordered pair, $\ (v\ w)\ $ and $\ (x\ y),\ $ of points of this grid, forms a small diagonal $\ (v\ w;\ x\ y),\ $, or a smad for short, $\ \Leftarrow:\Rightarrow\ $

$$ \forall_{(v\ w;\ x\ y)\,\in\,D}\quad |v-x|=|w-y|=1 $$

Let $\ D:=D_{mn}\ $ be the set of all smads. There is the direction function $\ d:D\to\{0\ 1\}\ $ defined as follows:

$$ d(v\ w;\ x\ y)\ :=\ \frac 12\cdot|x+y - v-w| $$

Each grid cell has two smads, say $\ \gamma\,$ and $\,\delta,\ $ and they have different directions, say $ d(\gamma)=0\ $ and $\ d(\delta)=1,\ $ or vice versa, $\ d(\gamma)=1\ $ and $\ d(\delta)=0.$

Furthermore, each smad $\ \delta:=(v\ w;\ x\ y)\ $ has its color $\ C(\delta)\in \Bbb Z/2:$

$$ C(\delta)\ :=\ x+y+d(\delta)\ \mod 2 $$

A smad configuration is any function $\ f:1..m\times 1..n\to D\ $ such that

$$ f(x\ y)\ =\ (x\!-\!1\,\ y\!-\!1;\ \ x\ y)\qquad\text{or} \qquad f(x\ y)\ =\ (x\!-\!1\,\ y;\ \ x\,\ y\!-\!1) $$

for every $\ (x\ y)\ \in\ 1..m\times1..n.\ $

Remark  It helps (psychologically) to identify $\ (x\ y)\ $ with the square which has $$ (x\ y)\qquad (x\!-\!1\,\ y)\qquad(x\,\ y\!-\!1) \qquad (x\!-\!1\,\ y\!-\!1) $$ as its vertices.

Each configuration $\ f\ $ induces a 2-coloring of the Euclidean rectangle $[0;m]\times[0;n].\ $ Let Black/White color be $\ 0/1\ (\!\!\!\mod 2)\ $ respectively; the colored areas are closures of $\ \overline {\mathcal B}\ $ and $\ \overline{\mathcal W},\ $ and they slightly overlap:

$$ \mathcal B\ :=\ \{0\,\ m\}\times [0;n]\ \cup \ \{(s\ t)\in (0;m]\times(0;n] \,\ (C\circ f)(\lceil s\rceil\ \lceil t\rceil)\ =\ 0\} $$ and $$ \mathcal W\ :=\ [0;m]\times \{0\,\ n\}\ \cup \ \{(s\ t)\in (0;m]\times(0;n] \,\ (C\circ f)(\lceil s\rceil\ \lceil t\rceil)\ =\ 1\} $$

Now is the time to define the West/East and South/North four areas, $\ M_0\ M_m\,\ N_0\ N_n:$

• $\ M_0\ $ is the connected component of $\ \{0\}\!\times\![0;n]\ $ of color $\ \overline{\mathcal B};$
• $\ M_m\ :=\ \overline{\mathcal B}\setminus M_0\quad $ (yes, $\ M_m\ $ is closed);
• $\ N_0\ $ is the connected component of $\ [0;n]\!\times\!\{0\}\ $ of color $\ \overline{\mathcal W};$
• $\ N_n\ :=\ \overline{\mathcal W}\setminus N_0\quad $ (yes, $\ N_n\ $ is closed);

If $\ M_0\cap M_m\ne\emptyset\ $ or $\ N_0\cap N_n\ne\emptyset\ $ then the theorem holds -- there exists the respective required paths.

And this is actually the case. Otherwise, there would be closed sets $\ V\ H\ $ which are the (vertical and horizontal respectively) separators between $\ M_0\ $ and $\ M_m\ $ as well as between $\ N_0\ $ and $\ N_n\ $ respectively. This means (by a classical topological dimension theory) that $\ V\cap H\ne\emptyset.\ $

Thus, let certain $\ (s\ t)\in V\cap H.\ $ Since $\ (s\ t)\in V $ we get $\ f(\lceil s\rceil\ \lceil t\rceil)\ \ne\ 0\ $ (is not Black); Since $\ (s\ t)\in H $ we get $\ f(\lceil s\rceil\ \lceil t\rceil)\ \ne\ 1\ $ (is not White). A contradiction. End of proof.

I have proved above a more precise version of the puzzle-theorem proposed by OP, namely:

THEOREM  For every configuration of cell diagonals, there is a West-East path across the grid of color black or a South-North path across the grid of color 1.

End of Theorem

This leads to a game similar to a game by Shannon (except that it is less natural than Shannon's game). Two players alternatively select cells of one color or another. The one who connects two opposite sides -- East and West by the first player or North and South by the second player -- wins. My precise formulation shows that there is always a winner -- this is due to 2-dim FPP. Then it follows that the winner can be always the first player -- this theorem is achieved by the borrowing strategy approach (both stages are just like in the case of Shannon's game).