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