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
Best Answer
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.