Teorema del tablero de ajedrez de Steinhaus

El teorema del tablero de ajedrez de Steinhaus es el siguiente teorema, debido a Hugo Steinhaus : ^[1]

Consideremos un tablero de ajedrez en el que algunas casillas contienen minas terrestres . En ese caso, el rey puede cruzar el tablero de izquierda a derecha sin pasar por ninguna casilla minada, o la torre puede cruzar el tablero de arriba a abajo moviéndose solo por las casillas minadas.

Variantes bidimensionales

Gale ^[2] demostró una variante del teorema en la que las piezas del tablero de ajedrez son hexágonos, como en el juego Hex . En esta variante, no hay diferencia entre los movimientos del rey y los de la torre.

Kulpa, Socha y Turzanski ^[1] demuestran una variante generalizada del teorema del tablero de ajedrez, en el que el tablero se puede dividir en polígonos arbitrarios, en lugar de solo cuadrados. También ofrecen un algoritmo para encontrar una ruta para el rey o una ruta para la torre.

variantes n-dimensionales

Tkacz y Turzanski ^[3] generalizan el teorema del tablero de ajedrez a un tablero n-dimensional:

Considere una cuadrícula de cubos de dimensión n. Coloree cada cubo con uno de los n colores 1,..., n . Entonces, existe un conjunto de cubos todos coloreados i , que conectan los lados opuestos de la cuadrícula en dimensión i .

Ahlbach ^[4] presenta la prueba de Tkacz y Turzanski para el teorema del tablero de ajedrez de n dimensiones, y la usa para demostrar el teorema de Poincaré-Miranda . La idea intuitiva es la siguiente. Supóngase por contradicción que una función n -dimensional f , que satisface las condiciones del teorema de Miranda, no tiene un cero. En otras palabras, para cada punto x , hay al menos una coordenada i para la cual f _i ( x ) es distinto de cero. Coloreemos cada punto x con algún color i para el cual f _i ( x ) es distinto de cero. Por el teorema del tablero de ajedrez de Steinhaus, existe algún i para el cual hay un camino de puntos coloreados i que conectan los dos lados opuestos en la dimensión i . Por las condiciones de Poincaré-Miranda, f _i ( x )<0 al inicio del camino y f _i ( x )>0 al final del camino, y la función es continua a lo largo del camino. Por lo tanto, debe haber un punto en el camino en el que f _i ( x )=0 - una contradicción.

Véase también

• Un teorema diferente de Steinhaus, relacionado con la disposición de las torres en un tablero de ajedrez, que se puede demostrar utilizando el teorema del matrimonio de Hall . ^[5]

Referencias

1. Kulpa, Władysław; Socha, Lesƚaw; Turzański, Marian (2000). "Teorema del tablero de ajedrez de Steinhaus". Acta Universitatis Carolinae. Matemática y Física . 041 (2): 47–50. ISSN  0001-7140.
2. Gale, David (diciembre de 1979). "El juego de Hex y el teorema del punto fijo de Brouwer". The American Mathematical Monthly . 86 (10): 818–827. doi :10.1080/00029890.1979.11994922. ISSN  0002-9890.
3. Tkacz, Przemysław; Turzański, Marian (1 de enero de 2008). "Una versión n-dimensional del teorema del tablero de ajedrez de Steinhaus". Topología y sus aplicaciones . Actas del Décimo Simposio de Praga sobre Topología General y sus Relaciones con el Análisis Moderno y el Álgebra. 155 (4): 354–361. doi : 10.1016/j.topol.2007.07.005 . ISSN  0166-8641.
4. Ahlbach, Connor (12 de mayo de 2013). "Un enfoque discreto del teorema de Poincaré-Miranda". Tesis de grado de HMC .
5. Morawiec, Adam (1 de marzo de 2019). "Sobre torres, matrimonios y emparejamientos o Steinhaus a través de Hall". Gráficos y combinatoria . 35 (2): 503–511. doi : 10.1007/s00373-019-02015-4 . ISSN  1435-5914.