8
$\begingroup$

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)$.

$\endgroup$
3
  • $\begingroup$ define orthogonally adjacent explicitly please. Given a lattice point at $(m,n)$ what points are orthogonally adjacent to it? $\endgroup$
    – kodlu
    Jul 9, 2023 at 8:37
  • $\begingroup$ $(m,n+1),(m,n-1),(m+1,n),(m-1,n)$ are orthogonally adjacent points of $(m,n)$. $\endgroup$
    – user308485
    Jul 9, 2023 at 9:00
  • 1
    $\begingroup$ This seems very similar to the hex theorem $\endgroup$ Aug 21, 2023 at 5:00

2 Answers 2

2
+50
$\begingroup$

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.

enter image description here

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.

$\endgroup$
1
  • 2
    $\begingroup$ The papers linked in your answer allow only what the OP calls orthogonally adjacent moves. The OP allows one of the paths to use diagonally adjacent moves (in addition to orthogonally adjacent ones). That complicates much the problem. Notably because if both parts are allowed to take diagonally adjacent moves, the result becomes false. $\endgroup$ Aug 26, 2023 at 23:01
2
$\begingroup$

So first I show the idea for proving the first direction, if there is a land path, then there isn't a water path. Essentially, the path splits the rest of the board into two regions, which I'll call region A and region B. If there was a water path, then it would have to start in region A and end in region B, so there would have to be a point in the path where you travel from a square in region A to a square in region B, but this is impossible since no square in region A is diagonally touching a square in region B.

To prove the reverse direction, say that there is no water path. Then call the set of all water tiles accessible from the leftmost column region C:

Then, note that all of the squares marked with an asterisk must be land tiles:

And this forms a land path.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .