Loading [MathJax]/extensions/TeX/mathchoice.js

9 votos

Dominar un tablero de cuatro dimensiones con torres

Existe una familia de problemas de ajedrez en la que se intenta dominar un tablero con el menor número posible de copias de una pieza determinada. El tablero está dominado si cada casilla contiene una pieza o es atacada por una.

Por ejemplo, para dominar un tablero de ajedrez habitual con 8 torres, simplemente coloca una torre en cada casilla de una diagonal. Se puede comprobar fácilmente que esto es óptimo, es decir, no 7 las torres pueden dominar un tablero de ajedrez. Este resultado se extiende fácilmente a un n×n de la junta, para cualquier n .

También puedes preguntar por el dominio de las torres en tres dimensiones, donde las torres pueden deslizarse a la izquierda/derecha, atrás/adelante o arriba/abajo. Este problema es más difícil, pero tiene una buena solución: n2/2 Las torres son necesarias y suficientes para dominar un n×n×n tablero. Ver aquí para una prueba.

Mi pregunta es sobre el caso de cuatro dimensiones. Aquí, hay cuatro ejes, y las torres pueden deslizarse a lo largo de cualquier eje. Específicamente,

¿Cuántas torres se necesitan para dominar un 4×4×4×4 ¿pizarra?

Me preguntaba si alguien había estudiado este problema antes, o tenía alguna buena idea de ataque.

Sé que 32 las torres son suficientes, mientras que 22 las torres son insuficientes. He llenado páginas tratando de tener éxito con 31 torres, en vano. Si tienes curiosidad, el número óptimo para un tablero de 2 x 2 x 2 x 2 es de 4 torres, y para un tablero de 3 x 3 x 3 x 3 es de 9 torres.

0 votos

Probablemente escribiría un simple programa de ordenador. Dadas las posiciones de las torres, comprobaría cada una de las 256 cuadrados si está controlado por 0 , 1 o varias torres. Esto ayuda a evitar errores y puede indicar qué posiciones de torre pueden mejorarse.

0 votos

Esta es una buena idea, pero para comprobar si 31 torres es suficiente, el programa tendría que comprobar todas \binom{256}{31}\approx 2^{132} posibles colocaciones de 31 torres. Incluso usando el control de simetría del tablero (4^!)^5 casos a la vez, esto es demasiado grande para la fuerza bruta.

0 votos

Claro que sí. Pero no me refiero a un programa inteligente que optimice la configuración. Sólo un programa muy básico donde tú, el usuario, introduces una configuración y el ordenador te dice el resultado. Entonces puedes mover una torre a otra casilla y ver si mejora la dominación o no.

2voto

Mike Earnest Puntos 4610

Hice esta pregunta en Math Overflow también y obtuve una respuesta que puede ser de interés. Una de las respuestas proporciona una 24 solución de la torre, y el otro proporciona una fuente que dice que 24 es el número mínimo requerido.

Ver el hipercubo como el conjunto de puntos (x,y,z,t) con 0\le x,y,z,t \le 3 todos los enteros, a continuación se muestran las ubicaciones de las torres en un 24 solución de la torre.

(0, 0, 0, 0)   (0, 0, 0, 1)   (0, 1, 1, 2)   (0, 2, 2, 3)   (0, 2, 3, 3)   (0, 3, 1, 2)
(1, 0, 1, 3)   (1, 1, 2, 0)   (1, 1, 3, 1)   (1, 2, 0, 2)   (1, 3, 2, 1)   (1, 3, 3, 0)
(2, 0, 2, 2)   (2, 0, 3, 2)   (2, 1, 0, 3)   (2, 2, 1, 0)   (2, 2, 1, 1)   (2, 3, 0, 3)
(3, 0, 1, 3)   (3, 1, 2, 1)   (3, 1, 3, 0)   (3, 2, 0, 2)   (3, 3, 2, 0)   (3, 3, 3, 1)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X