We are given a $M \times N$ grid where each tile is either a land or water tile. We may move from a land tile to any other land tile that is orthogonally adjacent to the current land tile. We may move from a water tile to any adjacent water tile (both orthogonally or diagonally will work for water tiles). We may not move from land to water or water to land.
It seems intuitive that if there exists a land-based path from the top row to the bottom row of the grid, then there cannot exist a water-based path from the left-most column to the right-most column. Conversely, if there is no water-based path from the left-most column to the right-most column, then there is a land-based path from the top row to the bottom row.
How might one go about proving the above claim? I am not sure what techniques are appropriate for this type of problem.
Originally, I had thought that the water movement needed to be only orthogonally adjacent for the above result to hold, but I found a counterexample.
EDIT: Orthogonally adjacent points of $(m,n)$ are $(m,n+1),(m,n-1),(m+1,n),(m-1,n)$. Diagonally adjacent points of $(m,n)$ are $(m+1,n+1),(m-1,n-1),(m+1,n-1),(m-1,n+1)$.
The intuition from the first part of the claim is justified by two dimensional Poincaré–Miranda theorem. Assuming both path exist, for each of them we connect the centers of consecutive tiles along the path by segments. Now connect the centers of the first and the last tile, respectively, of the water-based path with the vertical grid sides by horizontal segments lying inside of the respective tiles. Similarly, connect the centers of the first and the last tile, respectively, of the land-based path with the horizontal grid sides by vertical segments lying inside of the respective tiles. Thus we obtained two disjoint piecewise-linear paths connecting the vertical and the horizontal grid sides. I guess that we can parameterize these paths by continuous maps from $[-1,1]$ to the rectangle and then apply Poincaré–Miranda theorem for a contradiction. But we shall follow a shorter way. Pick a point outside the grid rectangle and connect it by pairwise noncrossing paths with all four endpoints of our paths, see the picture.
Since each two endpoints of our paths are connected by pairwise noncrossing paths (either by the blue or green paths, or the paths along the grid sides) inside the grid rectangle, we obtain a planar embedding of the complete five-vertex graph $K_5$, which is impossible, for instance, by Euler formula.
The second part is the well-known problem by Hugo Steinhaus, see, for instance, [Sht, Russian version, p. 19], [Sha, Problem 7], [Sur], [TZ], and [Ahl, Theorem 6].
References
[Ahl] Connor Thomas Ahlbach, A Discrete Approach to the Poincare–Miranda Theorem, Harvey Mudd College Senior Theses, 2013.
[TZ] Marian Turzański, Grzegorz Ziajor, The game of Hex, n-dimensional chessboard and Fixed Point Theorem.
[Sha] Yuriy Shashkin, Fixed points, in Russian: Неподвижные точки, Moscow, Nauka, 1989; in English: Fixed points, Providence, AMS, 1991.
[Sha2] Juriy Shashkin, Steinhaus’ problem on the chessboard, Works of IMM UrO RAS 5 (1998) 83—84.
[Sht] Hugo Steinhaus, Mathematical kaleidoscope, in Polish: Kaleidoskop matematyczny, 2nd ed., Pańsywowe Zaklady Wydawnictw Szkolnych, Warszawa, 1954; in Russian: Математический калейдоскоп, Moscow, Nauka, 1981, ser. “Kvant” library 8.
[Sur] Wojciech Surówka, A discrete form of Jordan curve theorem, Annales Mathematicae Silesiane 7 (1993) 57—61.