Connected path of diagonals across an $n\times n$ grid, and Lemma of Sperner

Question

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

Does anyone know how to prove this using the Lemma of Sperner?

In the original question post on MathOverflow, the author says there is such a proof using Sperner's Lemma. I tried but could not find it or get it.

But I would really be grateful to see a proof using Sperner. I am especially interested how the Sperner coloring is applied here, and would be grateful for any hint.

Just for background, in the original post, I have seen two proofs in the answers, not using Sperner's Lemma (and tried myself to give a proof). Here is the link to the original post https://mathoverflow.net/questions/112067/sperners-lemma-and-paths-from-one-side-to-the-opposite-one-in-a-grid/359066#359066

Answer 1

Just to close the loop on this one. In the meantime, I found a proof by contradiction. It makes repeated use of the Lemma of Sperner.

For those who are interested in it, the proof goes in three steps, assuming for contradiction that no such path exists. Just as a sketch:

(1) Label one side of the grid boundary with 1, the neighboring side with 2, the other two sides with 3. Inside the grid, label the vertices with 1, 2, 3 depending on the boundary with which they connect. In case of a tie, give priority to the lower number (this is critical for the proof and "drives" the location of the Sperner triangle).

Apply the Lemma of Sperner for the first time to conclude there must be a path from one side A to the neighboring side B.

(2) Change the labeling of the grid boundary: extend the 2-labeling to "destroy" the first Sperner triangle and such that a new one is created at the opposite side of A.

(3) Change the labeling of the grid boundary again: extend the 1-labeling to "destroy" the Sperner triangle from step (2) and create a new one next to it, that finally connects opposite sides of the grid along diagonals, which contradicts the assumption.

Answer 2

this will be merely an idea of a proof (so it is not very organized) and i'm posting it as an answer only because it is too long for a comment.

First assume that there are two corners of the grid such that their inner diagonal is the same (I mean that their diagonals point in the same direction, i.e. \and\ or /and/) and also such that there is a another corner of the grid with different diagonal direction (think how to fix it if this is not the case). we assign the first two corners the colors: R and B, and the third corner with color G. now for any square which is in the same row or column with a corner colored x and a corner colored y (where x and y are different colors among R,B,G and the corresponding squares have different diagonals) we may color the square by x or y depending on it's diagonal (for example if it has the same diagonal as the square colored x we color it x as well). after doing this process we have ended up coloring 2n-1 squares (that is a part of the "frame" of the grid). so by coloring the 3 corners of the (n-1)x(n-1) uncolored grid, we may continue in the same way until all of the n x n grid is colored by {R,B,G}.

Now we may take a triangle and assign to its corners, the corners of our grid colored by {R,G,B} and then add points corresponding to squares (a point that is corresponding to a square between the corner colored R and the corner colored G will be placed on the edge who's endpoints are colored R and G). you may now try and think how we will define a triangulation, such that by sperner's lemma there is a 3-colored triangle which corresponds to a 3 adjacent squares in the grid with different pointing diagonals.

then we may delete the 2 rows and 2 columns of this three squares and (think why) it is enough to find such a path in the smaller (n-2)x(n-2) grid. Now we may use inductive argument to prove the statement.