¿Cuántos caminos de movimiento [matemático] 6 [/ matemático] puede hacer un rey del ajedrez usando solo sus cuadrados originalmente adyacentes, terminando donde comenzó?

Answer 1

Definiciones:

La limitación introducida por el tablero de ajedrez [math] 3 \ times 3 [/ math] hace que sea difícil escribir una fórmula simple para el número de caminos posibles, ya que los movimientos del rey desde un cuadrado central ([math] 8 [/ math] son ​​posibles movimientos) son diferentes de los de un cuadrado de borde ([matemática] 5 [/ matemática] movimientos posibles) y diferentes de los de un cuadrado de esquina ([matemática] 3 [/ matemática] posibles movimientos). Contestaré varias versiones de esta pregunta para demostrar diferentes formas de pensar sobre este problema.

A : Tu pregunta exacta. En un tablero de ajedrez [math] 3 \ times 3 [/ math] (con al menos [math] x [/ math] y [math] y [/ math] coordenadas de [math] (1,1) [/ math]), encuentre el número de [math] 6 [/ math] -move caminos que el rey puede hacer, tanto comenzando como terminando en el cuadrado [math] (2,2) [/ math].

B : En un tablero de ajedrez infinito, encuentre el número de [math] k [/ math] -move caminos ([math] k \ in \ mathbb {N} \ cup \ {0 \} [/ math]) que el rey puede hacer , comenzando en el cuadrado [math] (a, b) \ in \ mathbb {Z} ^ 2 [/ math] y terminando en el cuadrado [math] (c, d) \ in \ mathbb {Z} ^ 2 [/ math] .

C : En un tablero de ajedrez [matemático] p \ veces q [/ matemático] (con al menos [matemática] x [/ matemático] y [matemático] y [/ matemático] coordenadas de [matemático] (1,1) [/ matemático] ), encuentre el número de [math] k [/ math] -mover caminos que el rey puede hacer, comenzando en el cuadrado [math] (a, b) \ in \ mathbb {N} ^ 2 [/ math] y terminando en el cuadrado [matemáticas] (c, d) \ in \ mathbb {N} ^ 2 [/ matemáticas].

Responder:

A :

La respuesta sería ([matemáticas] 4 \ veces [/ matemáticas] {el número de [matemáticas] 3 [/ matemáticas] -mover caminos desde el centro a una esquina específica} [matemáticas] \ veces [/ matemáticas] {el número de [math] 3 [/ math] -mover rutas de una esquina específica al centro}) + ([math] 4 \ times [/ math] {el número de [math] 3 [/ math] -mover rutas de la centro a un borde específico} [matemáticas] \ veces [/ matemáticas] {el número de [matemáticas] 3 [/ matemáticas] -mover rutas desde un borde específico al centro}) + ({el número de [matemáticas] 3 [ / math] -mover rutas del centro al centro} [math] \ times [/ math] {el número de [math] 3 [/ math] -mover rutas del centro al centro}). La [matemática] 4 \ veces [/ matemática] para los dos primeros términos es porque hay [matemática] 4 [/ matemática] cada una de las esquinas y bordes en el tablero. Dado que este es un problema con números pequeños, simplemente enumerar estos casos en papel da la respuesta: [matemáticas] 4 (16) (16) +4 (20) (20) +24 (24) = \ boxed {3200} [/ matemáticas].

B :

Modele los movimientos inmediatos del rey de la siguiente manera: moverse a la derecha es [matemáticas] x [/ matemáticas], moverse a la izquierda es [matemáticas] x ^ {- 1} [/ matemáticas], avanzar es [matemáticas] y [/ matemáticas], mover hacia abajo es [matemática] y ^ {- 1} [/ matemática], y los movimientos diagonales son [matemática] xy [/ matemática], [matemática] x ^ {- 1} y [/ matemática], [matemática] x ^ {- 1} y ^ {- 1} [/ math], y [math] xy ^ {- 1} [/ math], de la misma manera. Entonces el conjunto de todos los movimientos posibles de rey es [matemática] \ {x ^ {m} y ^ {n} | m, n \ in \ mathbb {Z} \} [/ math], que es un grupo abeliano infinito bajo multiplicación . El número de formas en que el rey puede alcanzar el cuadrado [matemática] (c, d) [/ matemática] desde [matemática] (a, b) [/ matemática] en [matemática] k [/ matemática] movimientos es el coeficiente de [matemáticas] x ^ {ca} y ^ {db} [/ matemáticas] en [matemáticas] (x ^ {- 1} y ^ {- 1} + x ^ {- 1} + x ^ {- 1} y + y ^ {- 1} + y + xy ^ {- 1} + x + xy) ^ k [/ matemáticas]. Por ejemplo, cuando [matemática] (a, b) = (0,0) [/ matemática] y [matemática] k = 6 [/ matemática] ((x ^ (- 1) * y ^ (- 1) + x ^ (- 1) + x ^ (- 1) * y + y ^ (- 1) + y + x * y ^ (- 1) + x + x * y) ^ 6 – Wolfram | Alpha), fuera de [math] 8 ^ {6} = 262144 [/ math] total de rutas posibles, el destino más común es [math] (0,0) [/ math] (con [math] 8840 [/ math] rutas posibles), mientras que destino [matemática] (3,3) [/ matemática] tiene [matemática] 1370 [/ matemática] rutas posibles y destino [matemática] (- 6,6) [/ matemática] tiene [matemática] 1 [/ matemática] ruta posible .

C :

Esta es la versión más genérica del problema y también puede responder a los otros dos casos. La única forma en que sé responder a este caso general es enumerando todas las rutas utilizando un programa recursivo. El siguiente script de Python maneja el caso A ; el código puede manejar el caso B tanto {haciendo tanto gridHeight como gridWidth mayor que [math] 2 \ times [/ math] numMoves} y {haciendo el startSquare en el medio de la cuadrícula}.

def main ():
numMoves = 6
gridWidth = 3
gridHeight = 3
startSquare = (2,2)
endSquare = (2,2)
caminos = findPaths (numMoves,
gridWidth,
gridHeight,
startSquare,
endSquare)
print str (len (caminos))

# #
# Encuentre todas las rutas de desplazamiento “numMoves” desde “startSquare” hasta “endSquare”.
# Suponga que la cuadrícula definida por “gridWidth” y “gridHeight” tiene
# menos coordenada x de 1 y menos coordenada y de 1.
# #
def findPaths (numMoves,
gridWidth,
gridHeight,
startSquare,
endSquare):
respuestas = set ()
si startSquare [0] gridWidth o \
startSquare [1] gridHeight o \
endSquare [0] gridWidth o \
endSquare [1] gridHeight:
devolver respuestas
return helpFindPaths (numMoves,
gridWidth,
gridHeight,
[startSquare],
endSquare,
respuestas)

# #
# Encuentra todas las rutas de movimiento “numMoves” que continúan desde “currentPath” que
# termina en “endSquare”, agrégalos a “respuestas” y devuelve “respuestas”.
# Asumir la cuadrícula definida por “gridWidth” y “gridHeight”
# tiene la coordenada x menor de 1 y la coordenada y menor de 1.
# #
def helpFindPaths (numMoves,
gridWidth,
gridHeight,
trayectoria de corriente,
endSquare,
respuestas):
currentSquare = currentPath [len (currentPath) – 1]
si numMoves == 0:
si currentSquare == endSquare:
answers.add (tupla (currentPath))
elif minMovesNeeded (currentSquare, endSquare) <= numMoves:
for possibleMove in possibleMoves (currentSquare,
gridWidth,
gridHeight):
currentPath.append (possibleMove)
helpFindPaths (numMoves – 1,
gridWidth,
gridHeight,
trayectoria de corriente,
endSquare,
respuestas)
currentPath.pop ()
devolver respuestas

# #
# Obtenga el número mínimo de movimientos necesarios para mover al rey de
# “currentSquare” a “targetSquare”.
# #
def minMovesNeeded (currentSquare, targetSquare):
horizontalDistance = abs (currentSquare [0] – targetSquare [0])
verticalDistance = abs (currentSquare [1] – targetSquare [1])
retorno máximo (horizontalDistance, verticalDistance)

# #
# Obtenga los próximos movimientos posibles del rey dado su “currentSquare”.
# Asumir la cuadrícula definida por “gridWidth” y “gridHeight”
# tiene la coordenada x menor de 1 y la coordenada y menor de 1.
# #
def possibleMoves (currentSquare,
gridWidth,
gridHeight):
toReturn = list ()
para moveHorizontal en rango (-1, 2):
newHorizontal = currentSquare [0] + moveHorizontal
si newHorizontal> = 1 y newHorizontal <= gridWidth:
para moveVertical en rango (-1, 2):
if moveHorizontal! = 0 o moveVertical! = 0:
newVertical = currentSquare [1] + moveVertical
si newVertical> = 1 y newVertical <= gridHeight:
toReturn.append ((newHorizontal, newVertical))
volver a Regresar

if __name__ == ‘__main__’:
principal()