An unrigorous idea: Consider the $m\times n$ table as a labirent which its unit diagonals are walls of the labirent. Suppose that a man can't go from left side to the right side on this labirent.Then if this man paints all points which he can go from any door on the left side, then there should be a diagonal way from up to down side which is on the perimeter of this painted area. Similarly, if a man can't go from up to down on this labirent, then there should be a diagonal way from left to right side. If a man can go from both left to right and up to down on this labirent, then since these two ways must be intersect, there should be a $1\times 1$ square which don't have a drawned diagonal, which is a contradiction.

Color the corners of the $1 \times 1$ squares alternatively white and black. The board with its diagonals is a triangulation. Augment this triangulation with four points, at the four cardinal $N, W, S, E$ positions, and connect them to the nodes of their corresponding sides -- it still remains a triangulation. Color $N, S$ white and $W,E$ black. Now assign to each white node the label $1$ if it can be reached from $N$ passing through white nodes only, assign to each black node the label $2$ if it can be reached from $W$ passing through black nodes only, and assign label $3$ to all other nodes. Assume there is no white path from $N$ to $S$, nor a black path from $W$ to $E$. Then the labels for $N,W,S$, respectively $E$ will be $1,2,3$, respectively $3$. The $NW$ corner of the board will be labeled $1$ or $2$, the $SW$ corner of the board will be labeled $2$ or $3$, the $NE$ corner of the board will be labeled $1$ or $3$, while the $SE$ corner of the board will be labeled $3$, We are in a proper configuration where to apply Sperner's Lemma: there exists (at least) a triangle whose vertices are labeled $1,2$ and $3$, so the label-$1$ vertex is white and the label-$2$ vertex is black. But if the third vertex, labeled $3$, were white, it should have been labeled $1$, while if it were black, it should have been labeled $2$. This contradiction shows our assumption was wrong, so there must exist either a (white) path connecting the top and bottom sides of the board, or a (black) path connecting the left and right sides of the board, all made by (some of) the diagonals drawn on the board. This problem is topologically equivalent to the famous Chess King's Theorem, or to the theorem according with which the game of Hex cannot end in a tie. This problem can also be turned into a game. Two people, one with sides $N,S$, the other with sides $W,E$, in turn draw diagonals, one per cell. The one player who connect his sides of the board wins. Prove the game cannot end up in a tie.

Is it clear which player has a winning strategy in the game version (even assuming $m=n$?). It seems like the usual strategy-stealing argument doesn't go through anymore because player 2 can use player 1's first move to his advantage.

mavropnevma wrote: Now assign to each white node the label $1$ if it can be reached from $N$ passing through white nodes only, assign to each black node the label $2$ if it can be reached from $W$ passing through black nodes only, and assign label $3$ to all other nodes. Assume there is no white path from $N$ to $S$, nor a black path from $W$ to $E$. Then the labels for $N,W,S$, respectively $E$ will be $1,2,3$, respectively $3$. The $NW$ corner of the board will be labeled $1$ or $2$, the $SW$ corner of the board will be labeled $2$ or $3$, the $NE$ corner of the board will be labeled $1$ or $3$, while the $SE$ corner of the board will be labeled $3$, We are in a proper configuration where to apply Sperner's Lemma: there exists (at least) a triangle whose vertices are labeled $1,2$ and $3$, so the label-$1$ vertex is white and the label-$2$ vertex is black. But if the third vertex, labeled $3$, were white, it should have been labeled $1$, while if it were black, it should have been labeled $2$. [/color] I think in the way that you number the nodes maybe a node can get at least two numbers and in the triangle you get from the Sperner Lemma a node with number 3 can have number 2, it's not a contradiction. Could you explain this?

A white node can only get label $1$ - if reachable from $N$ through whites only, or $3$ - if not reachable. Tertium non datur, and as these labels exclude each other, there can never be any conflict, nor ambiguity. Same goes for black nodes. Maybe you think a white node could get label $2$ (or a black node could get label $1$) - but that is prohibited, by the very argument explained above.

I am curious as to if there is a solution that doesn't rely on Sperner's Lemma.

Induction kills it!

Hmm another solution: Again, imagine the grid as a labyrinth with the diagonals as walls. It is easy to see that each boundary segment is mapped to a different one. Let the segments on the South side be labeled $1, 2, \ldots, n$, and WLOG $n \ge m$. If the North and South sides are not connected by the walls, then no path exists from any of the segments on the South side to any segments on the North side or the segments on the lateral sides immediately adjacent to the North side. Assuming this, there must be at least one segment on the South side connected to one on the East side and one on the West side. Let $x$ and $y$ be segments such that $x$ is maximal and $y$ is minimal with $x$ connected to the West side and $y$ to the East. Every segment $x < a < y$ must then be connected to some other $x < b < y$ on the South side. One can then go from the West side to the right of $x$, go along the wall on the left of $x+1$, etc., until the left of $y$ is reached, then go from there to the East side. So, the East and West side are connected by diagonals if the North and South sides are not, which implies the problem statement. Wow this is really not rigorous... diagrams help

Actually, a marginally stronger result can be shown. If $a$ is the number of left-right paths and $b$ top-bottom ones, then $a+b \ge 2$ (note that a path from the bottom left to the top right would be counted twice).

mavropnevma wrote: Color the corners of the $1 \times 1$ squares alternatively white and black. The board with its diagonals is a triangulation. Augment this triangulation with four points, at the four cardinal $N, W, S, E$ positions, and connect them to the nodes of their corresponding sides -- it still remains a triangulation. Color $N, S$ white and $W,E$ black. Now assign to each white node the label $1$ if it can be reached from $N$ passing through white nodes only, assign to each black node the label $2$ if it can be reached from $W$ passing through black nodes only, and assign label $3$ to all other nodes. Assume there is no white path from $N$ to $S$, nor a black path from $W$ to $E$. Then the labels for $N,W,S$, respectively $E$ will be $1,2,3$, respectively $3$. The $NW$ corner of the board will be labeled $1$ or $2$, the $SW$ corner of the board will be labeled $2$ or $3$, the $NE$ corner of the board will be labeled $1$ or $3$, while the $SE$ corner of the board will be labeled $3$, We are in a proper configuration where to apply Sperner's Lemma: there exists (at least) a triangle whose vertices are labeled $1,2$ and $3$, so the label-$1$ vertex is white and the label-$2$ vertex is black. But if the third vertex, labeled $3$, were white, it should have been labeled $1$, while if it were black, it should have been labeled $2$. This contradiction shows our assumption was wrong, so there must exist either a (white) path connecting the top and bottom sides of the board, or a (black) path connecting the left and right sides of the board, all made by (some of) the diagonals drawn on the board. This problem is topologically equivalent to the famous Chess King's Theorem, or to the theorem according with which the game of Hex cannot end in a tie. This problem can also be turned into a game. Two people, one with sides $N,S$, the other with sides $W,E$, in turn draw diagonals, one per cell. The one player who connect his sides of the board wins. Prove the game cannot end up in a tie. Why if the third vertex, labeled 3, were white, it should have been labeled 1?

Cool problem! Situate the board in the Cartesian plane so that the sides are parallel to the axes. Suppose that there is no path from the left side to the right side. Consider the set $S$ of edges which are "connected" to the left side, meaning that we can get from them to the left side by travelling on the drawn diagonals. By assumption, the edges in $S$ are entirely contained in the leftmost $m \times (n-1)$ subgrid of the board. Define the taxicab distance between $P_1 = (a, b), P_2 = (c, d)$ to be $|a-c| + |b-d|$. Denote this by $f(P_1, P_2).$ Define the taxicab distance between a point $P$ and a set $T$ of points to be $\min_{t \in T} f(P, t).$ Consider the set $X$ of points in the board which have a taxicab distance to the set $S$ of at least $1.$ By assumption, the entire rightmost edge of the board is contained in $X.$ Notice that $X$ is a collection of regions, which are delineated by diagonals of the board (not necessarily ones which are drawn) and the edges of the board. Consider the region $R$ which contains the rightmost edge. We claim that its sides which are diagonals are all drawn. Indeed, suppose for contradiction, that $AB$ was a diagonal which was a diagonal of the board of length $\sqrt2$, contained on a side of $R$, and isn't drawn. Then, if we let $A_1, B_1$ be so that $AA_1BB_1$ is a square, we know that $A_1B_1$ must be drawn. However, since the center of the square is on the boundary of $X$, there is some point on the diagonals of $S$ which is of taxicab distance exactly $1$ from the center of the square. Because $A, B$ are clearly not in $S$ (they are of taxicab distance $1$ from $S$), it's clear that one of $A_1, B_1$ is the endpoint of a diagonal in $S.$ Since $A_1B_1$ is drawn, this means that $B_1$ is also in $S.$ But then all point on the interior of segment $AB$ are of taxicab distance $<1$ from $S$ (because $A_1B_1$ is contained in $S$). This contradicts the fact that $AB$ was an edge of $R.$ Hence, our assumption was wrong, and all sides of $R$ are either drawn or are on the perimeter of the board. Now, all that remains is to notice that the perimeter of $R$ must contain diagonals which form a path from the top side to the bottom side. Indeed, this is pretty easy to prove. $\square$