Steinhaus chessboard theorem

The Steinhaus chessboard theorem is the following theorem, due to Hugo Steinhaus:[1]

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

Gale[2] 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[1] 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[3] 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[4] 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(x) is nonzero. Let us color each point x with some color i for which fi(x) 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(x)<0 at the start of the path and fi(x)>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(x)=0 - a contradiction.

See also

  • A different theorem of Steinhaus, related to arranging rooks on a chessboard, that can be proved using Hall's marriage theorem.[5]

References

  1. ^ a b Kulpa, Władysław; Socha, Lesƚaw; Turzański, Marian (2000). "Steinhaus chessboard theorem". Acta Universitatis Carolinae. Mathematica et Physica. 041 (2): 47–50. ISSN 0001-7140.
  2. ^ Gale, David (December 1979). "The Game of Hex and the Brouwer Fixed-Point Theorem". The American Mathematical Monthly. 86 (10): 818–827. doi:10.1080/00029890.1979.11994922. ISSN 0002-9890.
  3. ^ Tkacz, Przemysław; Turzański, Marian (2008-01-01). "An n-dimensional version of Steinhaus' chessboard theorem". Topology and its Applications. Proceedings of the Tenth Prague Symposium on General Topology and its Relations to Modern Analysis and Algebra. 155 (4): 354–361. doi:10.1016/j.topol.2007.07.005. ISSN 0166-8641.
  4. ^ Ahlbach, Connor (2013-05-12). "A Discrete Approach to the Poincare-Miranda Theorem". HMC Senior Theses.
  5. ^ Morawiec, Adam (2019-03-01). "On Rooks, Marriages, and Matchings or Steinhaus via Hall". Graphs and Combinatorics. 35 (2): 503–511. doi:10.1007/s00373-019-02015-4. ISSN 1435-5914.