3 votos

La teoría de grafos en el tablero de ajedrez

En un 8×8 tablero de ajedrez, se elige al azar dos plazas S y C. Tenemos una clavija que se le permite moverse siempre por 1 metros horizontalmente o verticalmente en cada movimiento. ¿Cuál es el número esperado de movimientos a la hora de iniciar a S y va a C, cuando hemos de seguir siempre el camino más corto posible? ¿Cuál es la gráfica que describe este problema?

He creado un programa para evaluar el número esperado de movimientos así que tengo 4, pero no sé cómo probar y describir con un gráfico. Una sugerencia será muy bueno para mí.

2voto

Technophile Puntos 101

El gráfico de la pregunta es simplemente la de 8 x 8 rejilla gráfica, pero no le importa nada de la derivación que sigue.

Voy a seguir el enfoque descrito en el apartado de comentarios. Suponiendo primero que S y C puede ser el mismo, el promedio de Manhattan (la más corta) de distancia entre ellos es la suma de la distancia promedio entre sus filas y la distancia media entre sus archivos, que por simetría puede ser llevado a ser el doble de la distancia media entre sus filas.

Con una probabilidad de $\frac18$, los dos extremos tienen el mismo rango. Con una probabilidad de $\frac7{32}$, son un rango aparte, con una probabilidad de $\frac3{16}$ dos filas y así sucesivamente. El número esperado de filas de la separación de ellos funciona como $$0\cdot\frac8{64}+\sum_{n=1}^7n\cdot\frac{2n}{64}=\frac{21}8$$ La media de Manhattan distancia entre S y C es $\frac{21}4=5.25$.

Si S no es igual a C, el 64 prohibido configuraciones contribuyen en nada a el total de Manhattan distancia a través de todas las configuraciones. Desde allí se $64^2$ configuraciones en todos, el promedio de la distancia se convierte en $$\frac{21}4\cdot\frac{64^2}{64^2-64}=\frac{16}3=5.333\dots$$

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