Tengo que demostrar que la fórmula $4n^2-12n+8$ da el número de aristas de un grafo de caballeros, donde n es el número de vértices horizontales y verticales y n^2 es el número de vértices.
Lo he probado para $n=4$ (el menor valor posible de $n$ con el que funciona el gráfico de los caballeros) y he supuesto que el resultado es cierto para n=k, pero ¿a dónde voy a partir de aquí? ¿Cómo puedo demostrar que funciona para $n=k+1$ ?
La idea de la inducción es que, dada tu respuesta para n=k, puedes demostrar que lo mismo es válido (en este caso que el número de aristas es igual a 4n^2-12n+8) para n=k+1.
Para demostrarlo debemos mirar el número de aristas que se añaden cuando se toma un tablero de ajedrez de k+1 x k+1 en lugar de k x k. Así que vamos a añadir una nueva fila y columna por debajo y a la izquierda del antiguo tablero de kxk. A esto lo llamo el nuevo tablero. Desde las esquinas de este tablero tienes 2 movimientos de caballo hacia el tablero antiguo (y por supuesto 2 desde el tablero antiguo hacia estas esquinas, pero como estamos contando aristas y no movimientos sólo miraremos los movimientos que empiezan en el nuevo tablero). Los espacios junto a los bordes tienen 3 opciones cada uno. Todos los demás espacios nuevos tienen 4 opciones.
Así que el número extra de aristas parece ser 3*2 (para las esquinas) + 4*3 (para los espacios junto a las esquinas) + 2*((k+1)-4)*4 (para todos los demás espacios nuevos) = 6+12+8(k-3)=8k-6.
Sin embargo, hay que tener en cuenta que desde las casillas situadas junto a la esquina inferior derecha también se puede hacer un movimiento a las casillas del nuevo tablero, es decir, las contamos doblemente. Por lo tanto, tenemos que restar 2 de la respuesta anterior.
Sumando todo esto; el nuevo tablero contiene todos los movimientos que tenía el antiguo + 8k-8 movimientos extra. Es decir, 4k^2-12k+8 + 8k-8 = 4(k+1)^2-12(k+1)+8
En lugar de resolver el problema por inducción, podemos simplemente calcular el número de aristas utilizando nuestro conocimiento de cómo se mueve el caballo. Consideramos seis casos en un tablero de ajedrez de n x n cuando $n \ge 4$ . Para facilitar la visualización, he subido una imagen de un tablero de ajedrez de 8 x 8.
a) El caballero está en la esquina. Cuando el caballo se encuentra en la esquina, puede moverse a dos casillas diferentes. Hay cuatro esquinas, por lo que tendremos $4 \cdot 2 = 8 $ bordes.
b) El caballo se sitúa en una casilla del borde del tablero junto a la esquina. Aquí, el caballo puede moverse a tres casillas. Como hay $8$ tales cuadrados (dos junto a cada esquina), tendremos $8 \cdot 3 = 24$ bordes.
c) El caballo se encuentra en el borde del tablero pero no en las casillas de a) o b). Aquí, el caballo tiene acceso a 4 casillas. Como hay $(n-4) \cdot 4$ tales cuadrados, obtenemos $(n-4) \cdot 4 \cdot 4 = 16(n-4)$ bordes.
d) El caballo está en una de las casillas adyacentes a la esquina pero no en el borde. En este caso, el caballo puede moverse a $4$ cuadrados, y hay $4$ tales cuadrados, por lo que tenemos $4 \cdot 4 = 16$ bordes.
e) El caballo está en la fila o columna que está al lado de la fila o columna que está en el borde del tablero, pero no en las casillas de d) o b). Hay $(n-4) \cdot 4$ tales casillas y en cada una de ellas el caballo puede moverse hasta 6 casillas, por lo que obtenemos $(n-4) \cdot 4 \cdot 6 = 24(n-4)$ bordes.
f) El caballo está en cualquier otra casilla, es decir, las casillas que no son las dos primeras o las dos últimas columnas o las dos filas superiores o inferiores. Hay $(n-4) \cdot (n-4)$ tales casillas y en cada una de ellas, el caballo puede moverse hasta 8 casillas, lo que nos da $8 \cdot (n-4)^2$ bordes.
Ahora sólo calculamos la suma de las aristas en a) - f). Como hemos contado cada arista dos veces, nuestra respuesta será la mitad de esta suma:
$\frac{16+24+16(n-4)+16+24(n-4)+8(n-4)^2}{2} = 4n^2 - 12n + 8$
Nota: Por cierto, la respuesta también es válida para $n \ge 1$ . Para $n=1$ y $n=2$ la fórmula nos dará la respuesta $0$ lo cual es cierto, ya que un caballo en un tablero de ajedrez de 1 x 1 y de 2 x 2 no tiene acceso a ninguna casilla, por lo que los correspondientes grafos de caballos no tienen aristas. Un gráfico de caballos para el tablero de ajedrez de 3 x 3 es un gráfico desconectado con el gráfico de círculos $C_8$ y un vértice solitario como componentes. La fórmula nos dará que este gráfico tendrá $8$ bordes, lo cual es bastante cierto.
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.
