21
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Do you mean to say that each square gets exactly one diagonal? $\endgroup$ Nov 11, 2012 at 12:47
  • $\begingroup$ Yes; arbitrarily chosen (edited) $\endgroup$ Nov 11, 2012 at 18:09
  • 5
    $\begingroup$ Computationally speaking, it is PPAD-complete to find a three-colored simplex per Sperner's Lemma. en.wikipedia.org/wiki/PPAD_(complexity) $\endgroup$
    – user21816
    Nov 11, 2012 at 18:23
  • 2
    $\begingroup$ My first thought - likely irrelevant but recorded for posterity - is David Gale's proof of the Brouwer Fixed Point Theorem using the Game of Hex. $\endgroup$ Nov 11, 2012 at 18:27
  • 1
    $\begingroup$ If the left-to-right path does not exist, the constraint is the up-to-down cut set: a curve from the up side to the down side not intersected by the diagonals. We may go along this curve by our diagonals (this has to be checked carefully). And what is the Sperner solution? $\endgroup$ May 1, 2020 at 13:19

6 Answers 6

8
$\begingroup$

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":
    Random Diagonals 50x50

$\endgroup$
2
  • $\begingroup$ Thanks! Any chance of drawing it without the horizontal and vertical lines? $\endgroup$ Nov 11, 2012 at 20:32
  • 1
    $\begingroup$ @Brendan: Good suggestion: Done! A nice maze design, isn't it? $\endgroup$ Nov 11, 2012 at 22:39
6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ If I understand the question correctly, we are looking for a path on the blue lines in Joseph O'Rourke's picture. At first I thought this solution can be turned into such a solution in the following way: The exploration paths essentially walk along the the white corridors. So if we walk along an exploration path,we get a path in the walls by looking at the wall theat our right hand touches. however, that jumps, whenever we leave at the bottom so that we make a left turn. $\endgroup$ May 18, 2020 at 10:27
  • $\begingroup$ edit at I see, in this case we simply choose the point where we exited as the new starting point, so that it doesn't matter that there was a jump. $\endgroup$ May 18, 2020 at 10:30
  • $\begingroup$ @Kostya_I, thanks a lot for providing such a proof by exploration. In your last sentence you say ".. by induction, ..". Does this mean the last statement should follow from a (separate) inductive proof, or does it mean something different? I might simply misunderstand this part of your conclusion as I am not a native English speaker. $\endgroup$
    – Claus
    May 20, 2020 at 17:57
  • 1
    $\begingroup$ @Claus, I added an explanation $\endgroup$
    – Kostya_I
    May 20, 2020 at 18:24
  • 1
    $\begingroup$ @Kostya_I I just wanted to share with you, in case you are interested in this: a nice proof from user Oliver Clarke that there is more than 1 crossing path (along diagonals in the grid) math.stackexchange.com/q/3689297/782412 $\endgroup$
    – Claus
    May 24, 2020 at 14:38
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The link in the post no longer works - here is a snapshot from Wayback Machine. $\endgroup$ May 13, 2020 at 4:43
  • $\begingroup$ I used fpp/dimension theory to show that with the right strategy the first player must win (loooong years ago). I used to play this game and enjoyed it (I would often win as a second player :) ). $\endgroup$
    – Wlod AA
    May 18, 2020 at 12:30
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for providing a graph theoretic proof! I am very interested in it. In your answer, you offer to provide a graphic representation of this, I would be grateful if you could do that. I am really interested in your proof argument, and the way it uses the dual graph. $\endgroup$
    – Claus
    May 20, 2020 at 18:08
1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ The central notion which combines the FPP and dimension theory is hardly known at all, it is the notion of universal function -- it is a common generalization of the two theories. It could be applied to differential equations, functional analysis, homotopy theory of manifolds. The general notion of the universal morphisms (and its dual notion) could be applied usefully to several categories, even to algebra (which was already done anyway). $\endgroup$
    – Wlod AA
    May 18, 2020 at 20:55
  • 1
    $\begingroup$ this is very impressive! So in fact you have established the equivalence of the crossing-along-diagonals lemma (puzzle theorem) and the topological theorem about separators. I find this quite spectacular and feel this should be made prominent! One would now suspect the crossing-along-diagonals lemma is a simple, powerful tool like the Sperner lemma, but unknown. $\endgroup$
    – Claus
    May 19, 2020 at 6:22
  • $\begingroup$ I just wanted to point you to this new post. I think it is great that the grid with the diagonal is getting more and more attention. mathoverflow.net/q/360785/156936 $\endgroup$
    – Claus
    May 19, 2020 at 17:09
1
$\begingroup$

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).

$\endgroup$
10
  • 1
    $\begingroup$ thanks a thousand times for this proof. I think your idea to relate it to the classical topological dimension theorem is very powerful. Please let me know your opinion, do you think this crossing-along-diagonals lemma (puzzle) could also be used to prove the topological dimension theorem? This would create a fascinating equivalence of theorems. $\endgroup$
    – Claus
    May 18, 2020 at 5:09
  • $\begingroup$ please let me also know if you think the crossing-along-diagonals lemma can prove the No Retraction Theorem. As I mentioned earlier, I failed to use it to prove Brouwer's FPT. $\endgroup$
    – Claus
    May 18, 2020 at 5:13
  • 1
    $\begingroup$ @Claus, a classical argument: let continuous $\ f:B\to B\ $ was such that $\ \forall_{x\in B} f(x)\ne x,\ $ where $\ B\ $ is the unit Euclidean (rounded) n-ball. Then $\ r:B\to S\ $ (where $\ S\ $ is the boundary sphere) such that from $\ f(x)\ $ you shoot at $\ r(x)\ $ through $\ x\in B\ $ is a continuous retraction of $\ B\ $ onto $S$. Thus the non-retraction theorem implies the fpp theorem. $\endgroup$
    – Wlod AA
    May 18, 2020 at 7:10
  • 1
    $\begingroup$ The opposite implication is even easier. If you had a said retraction then compose it with the antipodal map of $\ S,\ $ and you get a map of the ball into itself free of any fixed points (the image would even reside in $\ S$). $\endgroup$
    – Wlod AA
    May 18, 2020 at 7:18
  • 1
    $\begingroup$ @Claus, "whether you feel the crossing-along-diagonals lemma could prove the No Retraction Theorem?" #### Oh, yes, from the first moment (I should write it down), as many others would do. Hex and other games were mentioned in this thread, the intuition is clear (at one moment, I made a wrong argument, then my view temporary has switched for a wrong reason). ### With XX century patience, you may enjoy a lot of classic "Dimension Theory" by Witold Hurewicz and Henry Wallman. And more up to date are texts by Ryszard Engelking. $\endgroup$
    – Wlod AA
    May 18, 2020 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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