Steinhaus chessboard theorem


The Steinhaus chessboard theorem is the following theorem, due to Hugo Steinhaus:
Consider a chessboard on which some cells contain landmines. Then, either the king can cross the board from left to right without meeting a mined square, or the rook can cross the board from top to bottom moving only on mined squares.

Two-dimensional variants

David Gale proved a variant of the theorem in which the tiles on the chessboard are hexagons, as in the game of Hex. In this variant, there is no difference between king moves and rook moves.
Kulpa, Socha and Turzanski prove a generalized variant of the chessboard theorem, in which the board can be partitioned into arbitrary polygons, rather than just squares. They also give an algorithm for finding either a king route or a rook route.

n-dimensional variants

Tkacz and Turzanski generalize the chessboard theorem to an n-dimensional board:
Consider a grid of n-dimensional cubes. Color each cube with one of n colors 1,...,n. Then, there exists a set of cubes all colored i, which connect the opposite grid sides in dimension i.
Ahlbach present the proof of Tkacz and Turzanski to the n-dimensional chessboard theorem, and use it to prove the Poincare-Miranda theorem. The intuitive idea is as follows. Suppose by contradiction that an n-dimensional function f, satisfying the conditions to Miranda's theorem does not have a zero. In other words, for each point x, there is at least one coordinate i for which fi is nonzero. Let us color each point x with some color i for which fi is nonzero. By the Steinhaus chessboard theorem, there exists some i for which there is a path of points colored i connecting the two opposite sides on dimension i. By the Poincare-Miranda conditions, fi<0 at the start of the path and fi>0 at the end of the path, and the function is continuous along the path. Therefore, there must be a point on the path on which fi=0 - a contradiction.