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

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.

-
Do you mean to say that each square gets exactly one diagonal? –  Dima Pasechnik Nov 11 '12 at 12:47
Yes; arbitrarily chosen (edited) –  Cosmin Pohoata Nov 11 '12 at 18:09
Computationally speaking, it is PPAD-complete to find a three-colored simplex per Sperner's Lemma. en.wikipedia.org/wiki/PPAD_(complexity) –  user21816 Nov 11 '12 at 18:23
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. –  Benjamin Dickman Nov 11 '12 at 18:27
Also of interest is how many paths there are, on average. For square arrangements I expect any number achievable from 1 to O(2^n). Gerhard "Ask Me About System Design" Paseman, 2012.11.11 –  Gerhard Paseman Nov 11 '12 at 21:12

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":

-
Thanks! Any chance of drawing it without the horizontal and vertical lines? –  Brendan McKay Nov 11 '12 at 20:32
@Brendan: Good suggestion: Done! A nice maze design, isn't it? –  Joseph O'Rourke Nov 11 '12 at 22:39
Wonderful, thanks! –  Brendan McKay Nov 12 '12 at 11:47

This looks very similar to a 45 degree rotated board of the Bridg-it game: http://www.sites4all.co.uk/bridjit/ (About the winning strategy, see also http://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.

-

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.

-