martes, 17 de enero de 2012

Problema del Día: Cantidad de casillas a las que puede llegar un caballo

Supongamos que un caballo de ajedrez se encuentra en una casilla de un tablero infinito de ajedrez. Encuentra la cantidad de casillas a las que puede llegar con exactamente $n$ movimientos.

12 comentarios:

Adán dijo...

Bueno, veremos que es lo que sucede en los primeros casos para $n$.

Si $n=0$ entonces es claro que hay una única casilla a la que puede llegar el caballo $C$.

Si $n=1$, podemos verificar que el caballo puede llegar a $8$ casillas distintas.

Si $n=2$, entonces $C$ puede partir desde cualquier casilla en las que pudo haber caído cuando se movió $1$ vez, entonces se puede verificar que $C$ puede llegar a $33$ casillas distintas en este caso.

En general, usaremos el hecho de que cuando $C$ se mueve $k+1$ veces parte de una de las casillas en donde pudo haber caído tras $k$ movimientos.

Vamos también a colorear el tablero infinito tal como uno de ajedrez. Entonces podemos decir sin pérdida de la generalidad que $C$ estaba inicialmente estaba en una casilla blanca, y podemos también observar que tras una cantidad par de movimientos de $C$, éste estará en una casilla blanca, y tras una cantidad impar de movimientos, estará en una casilla negra.

Ahora, en cada movimiento, $C$ avanza $2$ casillas en una dirección, y $1$ casilla en una dirección perpendicular a la primera dirección. Entonces, vamos a ver que tras $n\geq 3$ movimientos, $C$ se encuentra dentro de un cuadrado de $\left(4n+1\right)\times \left(4n+1\right)$ casillas.

Adán dijo...

Tenemos que $C$ puede moverse máximo $2n$ casillas en una sola dirección, si da $n$ movimientos, entonces podemos encerrar a $C$ en una cuadro de lado $2n+2n+1$, por que contamos lo que puede avanzar máximo en direcciones opuestas.

Ahora, también podemos ver que hay $\frac{n\left(n+1\right)}{2}$ casillas en cada una de las $4$ esquinas de nuestro cuadro a donde $C$ no puede llegar. Esto es porque $C$ solo se mueve en total $3n$ casillas en alguna dirección, y para llegar a esas casillas mencionadas se necesitan recorrer al menos $3n+1$ casillas en total, por lo cual no son alcanzables para $C$.

Se puede verificar que para el caso $n=3$, todas las casillas negras distintas a las $\frac{n\left(n+1\right)}{2}$ casillas que acabamos de descartar, son alcanzables para $C$. Veamos que en total tenemos

$\left(4n+1\right)^{2}-2n\left(n+1\right)=14n^{2}+6n+1$ casillas.

Si tomamos cualquier diagonal, las casillas sobre esa diagonal son del mismo color. Entonces las casillas de los vértices en las diagonales que delimitan, por así decir, nuestro "octágono" que resulta de quitar los "triángulos" de las esquinas que dijimos que $C$ no puede llegar a ellos, donde puede estar $C$, son del mismo color.

Podemos notar también que para $n=3$, $C$ puede llegar a todas las casillas negras dentro o sobre el borde de nuestro octágono mencionado previamente.

Adán dijo...
Este comentario ha sido eliminado por el autor.
Adán dijo...

Entonces, veamos que en cuadrado de lado $\left(4n+1\right)^{2}$ hay exactamente $8n^{2}+4n$ casillas negras, y $8n^{2}+4n+1$ casillas blancas. Entonces, cuando quitamos las casillas en las esquinas viendo como si quitáramos diagonal por diagonal, quitamos $1$ blanca, después $2$ negras, $3$ blancas, etc.

Entonces vamos a ver en $2$ casos.

Si $n=2m$, entonces quitaremos

$1+3+\ldots+\left(2m-1\right)=m^{2}$

casillas blancas y

$2+4+\ldots+2m=m^{2}+m$

casillas negras. Esto es por cada esquina, así que quitamos en total $4m^{2}$ casillas blancas y $4m^{2}+4m$ casillas negras, por lo que nos quedan

$8\left(2m\right)^{2}+4\cdot 2m -4m^{2}-4m=28m^{2}+4m$

casillas negras y

$8\left(2m\right)^{2}+4\cdot 2m+1-4m^{2}=28m^{2}+8m+1$

casillas blancas. Como $n$ es par, nos va a interesar la cantidad de casillas blancas.

Adán dijo...

Ahora, si $n=2m+1$ entonces perdemos $m^{2}+2m+1$ casillas blancas y $m^{2}+m$ casillas negras. Entonces, perdemos en total $4m^{2}+8m+4$ casillas blancas y $4m^{2}+4m$ casillas negras. Entonces nos quedan

$8\left(2m+1\right)^{2}+4\left(2m+1\right)-4m^{2}-4m=28m^{2}+36m+12$ casillas negras, que son las que nos importan, pues $n$ es impar.

Adán dijo...

Entonces, para $n$ par tenemos que nos quedan

$28m^{2}+8m+1=7n^{2}+4n+1$

casillas blancas. Ahora, si $n$ es impar tenemos

$28m^{2}+36m+12=7n^{2}+4n+1$

casillas negras. Veremos por que esta es la respuesta buscada.

Adán dijo...

Mencionamos ya que para $n=3$ todas las casillas del color que nos interesan sobre o dentro del octágono, son posibles puntos para que caiga $C$. Entonces, como todos los puntos están coloreados, entonces, de cada casilla coloreada, se colorean las $8$ que le corresponden para la $n$ que sigue, pues todas las casillas posibles para la $n$ siguiente vienen de casillas en donde pudo haber caído $C$ en la $n$ actual. Entonces, de nuevo, todos los del color opuesto dentro del octágono en el cuadrado que corresponde quedan coloreados de nuevo, haciendo que vuelvan a ser

$7n^{2}+4n+1$

casillas. Entonces para $n=0, 1, 2$ tenemos que $C$ puede caer en $1, 8, 33$ casillas, respectivamente; y para $n\geq 3$, $C$ puede caer en $7n^{2}+4n+1$ casillas distintas.

Juan dijo...

Mi solución no me gustó. Llamo dos cuadros vecinos si el caballo puede saltar entre ellos en 1 paso. Demostraré que la respuesta es $(n+1)^3$ si $ n \le 1$, 33 si n=2, y es $7n^2+4n+1$ si $n \ge 3$ . La primera parte es fácil. Si no avanzo solo puedo llegar a 1 recuadro, si sí avanzo pero solo una vez, puedo llegar a 8 cuadros, y si avanzo dos veces, es fácil ver con un dibujo que se puede llegar a 33 cuadros. Ahora, también con un dibujo es fácil ver que con $n=3$ se logran los $7*3^2+4*3+1= 76$ cuadros prometidos. Ahora, ¿qué pasa si para $n \ge 3$ se cumple la fórmula? Demostraré lo siguiente:
Si tenemos un cuadrado de $(4n+1) \times (4n+1)$, centrado en la casille inicial, y le cortamos de las esquinas pirámides de cuadros de lado $n$ (de manera que obtenemos un "octágono" de área $(4n+1)^2 - 2n(n+1)$), y $n \ge 3$,entonces podemos colorear este octágono al estilo ajedrez con la casilla central (donde el caballo está inicialmente) blanca, tal que todos los cuadros blancos son alcanzables en $n$ pasos si n es par, y los negros si $n$ es par.
NOTA: Con ésto acabamos, pues con cuentas podremos deducir la fórmula inicial. ¿Por qué? Dividimos en dos casos.
$CASO$ $I$: n=2m, m positivo mayor que 1.
El área del cuadrado es $(4n+1)^2 = 16n^2 + 8n +1$. De ésto, como el centro es blanco, habrá menos blancos que negros, por lo que el número de blancos será $8n^2+4n+1$ Ahora, para acabar, demuestro que las pirámides tienen cada una $m^2$ blancos. Pero ésto es fácil, pues $1+3+5+...+(2m-1) = m^2$, y las diagonales alternan entre ser blancas o negras.
$CASO$ $II$: n=2m+1, m positivo
Las cuentas van igual, pero como ahora contamos a los negros, que son menos, habrá $8n^2+4n$ negros. Demuestro que las pirámides tienen $(n^2-1)/4 = m^2+m$ negros. Las pirámides tienen lado $2m+1$ y su esquina es blanca. Entonces, habrá $2+4+..+2m = 2(1+2+...+m) = m(m+1)$ negros, como deseábamos. Por tanto, hemos acabado las cuentas.
Así, solo nos queda demostrar el resultado.
Éste lo demuestro con inducción sobre $n$.
El caso base ya lo había hecho (el dibujo con $n=3$). Le llamo al octágono respectivo a $n$, $O_n$. Si C (digamos sin pérdida de generlidad, negro) está en $O_n$, entonces es trivial que existe un blanco en $O_n$ vecino de C, por lo que podré llegar a C en $n+1$ pasos (nota: aquí supongo sin pérdida de generalidad que $n$ es par). Si C está en $O_{n+1)$ pero no en $O_n$, entonces considero dos casos: está en una "diagonal cortada" de $O_{n+1}$, o en un lado de éste octágono. Ésto se reduce a demostrar las dos siguientes oraciones:
1. Si tengo dos líneas a distancia dos cuadros, y todos los blancos abajo de la línea de abajo están ocupados por un caballo, puedo llegar a cualquier negro entre las dos líneas.
2. Lo mismo, pero con líneas en modo Zig-Zag. (Nota: aquí, todos los cuadrados que comparten dos lados con alguna de las líneas son blancos).
Pero con un dibujo, estas dos oraciones son triviales.
Así, hemos acabado.
Quod erat demonstrandum. $\clubsuit$.

Chuck dijo...

Este problema me pareció un tanto divertido. Analizaremos en

casos distintos $n=2k\forall k\in\mathbb{N}\bigcup\{0\}$ y

$n=2k+1\forall k\in\mathbb{N}\bigcup\{0\}$. La función que

nos lleva de estos valores a la cantidad de casillas que

cumplen será $f$.

Dado una casilla en la que se encuentra el caballo, podemos

ver que en dos movimientos, podemos hacer cualquier

movimiento y regresarnos, así que una posibilidad es la

casilla en la que nos encontramos. Además, podemos trazar

una diagonal que pase por la casilla en la que estamos y se

extienda por toda la cuadrícula paralela a la gráfica de

$y=x$ y otra ortogonal a esta que también sea diagonal de la

casilla. Contaremos únicamente (por ahora sin incluir a la

casilla de origen) los puntos en los que podamos caer que

estén por encima (estricto) de la segunda línea y que pasen

por la primera línea o queden por encima de ella y

multiplicarla por cuatro para obtener el total. Con esto, no

es tan difícil ver que podemos caer en (considerando un paso

como de tamaño uno en un eje y a la casilla en que estamos

como el origen) las casillas con coordenadas $(0,2),(0,4),

(1,1),(3,3),(2,4),(-2,4),(1,3),(-1,3)$ únicamente y una vez

que lo contabilizamos las cuatro veces junto con la central,

vemos que si se inicia en un cuadro negro, se finaliza en

otro cuadro negro (pues en cada movimiento siempre se cambia

de color), y están ocupando todos los cuadros negros de una

cuadrícula de $(1+2(4))\times (1+2(4))$ exceptuando las

esquinas (que podemos ver como escaleras de un escalón)

esquinas de una cuadrícula homotética y concéntrica de $5

\times 5$. Haciendo un total de $\frac{9^{2}+1}{2}-8=33$

pues el centro es negro y tiene dimensiones impares.

Gracias a lo que hicimos hace un poco, podemos ver que $f(2

(1))=33$, mientras que , sin embargo es aún más poderoso, ya

que nos ayuda a intuir cómo será el mapa de casillas en las

que se podrá caer. Para comenzar, el hueco creado por las

esquinas de la cuadrícula de $5\times 5$ será eliminado por

cualquier casilla a la que se pudo llegar y que comparten un

vértice (hay $4$ de ellos), pues hay que "poner" una marca

en cada lugar según la descripción del párrafo anterior para

cada casilla en la que pudimos haber quedado (las casillas

con muchas marcas quedan como si tuvieran sólo una), así que

en realidad, veremos que obtendremos lo mismo pero en una

cuadrícula de $1+2(4)+2(4)$ (aumentando en $4$ en cada lado

cada vez) de cada dimensión, y los huecos creados por los

extremos de sus respectivas cuadrículas de $5\times 5$,

quedarán marcados, pues cada punto tiene hasta ahora (y esta

propiedad se conserva por la forma que veremos que tendrán

las casillas) dos casillas distintas con la que comparte un

vértice y las cuales (sin importar si son opuestas o no)

entre las dos podrán llegar a todas esas casillas. Mientras

que lo único que pasa es que las esquinas de las cuadrículas

de los puntos que se encuentran en las orillas, no

necesariamente sean marcados, y de hecho, por su acomodo en

diagonal, veremos que como el extremo del borde diagonal de

la figura formada por las casillas anteriores (en el ejemplo

anterior son los puntos $(2,4),(3,3)$ y sus correspondientes

en las otras secciones, dónde si hubiera una casilla entre

ellas, sería parte del borde diagonal pero no sería un

extremo), se generan dos más en la siguiente "capa" por así

decirlo (las nuevas casillas marcadas), mientras que cada

casilla en el borde diagonal que no es extremo, sólo agrega

una casilla en el borde diagonal de esta forma.

Chuck dijo...

De esta forma vemos que la cantidad que habrá para el $2(n+1)$ será igual a los que hubo en el $2n$ incrementado en $2$, y así nuestra nueva escalera tiene $2$ escalones más, pero como sólo nos interesan las casillas negras y la esquina de la escalera (el que no es parte de un escalón) es negro, los negros que nos importan son $(1)+((1)+2)=1+3=4$ (este número incrementa en $2$ al anterior), y como siempre será suma de impares, es conocido que es $n^{2}$. Pero además, es en las cuatro "esquinas", así que debemos restarle $4n^{2}$, mientras que como nuestra cuadrícula era de $2(4)n+1)$ por cada lado y el total de cuadritos son $64n^{2}+16n+1$ y sólo $32n^{2}+8n+1$ son de negros, pero quitándole las que no están incluidas, son $28n^{2}+8n+1$. Y cumple para el $n=0,2,3,4,\dots$, es decir, todos los naturales excepto el $1$, pues le quitamos cuatro casillas por los vértices de la cuadrícula de $5\times 5$ con centro en la casilla con la que comenzamos y entonces $f(2)=33$ y $f(2n)=7(2n)^{2}+4(2n)+1\forall n\in\{0,2,3,4,\dots\}$.

De manera similar, haremos el cálculo para movimientos impares (es decir, $2n+1$). $f(1)=8$, y además por argumentos similares a los anteriores, la figura que se forma a partir de $n=1$ es similar a la que se da con $2n$, pero en el caso inicial, los huecos de las cuadrículas de lado $5$ y centro donde empezamos, se pueden llenar con los otros puntos pero no con el mismo argumento (se revisa y se ve que es cierto con facilidad) para el cambio de $n=0$ a $n=1$, sin embargo de este en adelante es completamente análogo, así que como con este nuestra "escalera", no tiene escalones, en vez de ser suma de impares, lo será de los primeros $n$ pares y es igual a $n(n+1)$ (pero cuatro veces) mientras que las dimensiones de la cuadrícula que contiene a toda la figura será de $2(4)n+5=8n+5$, así que el total es de $64n^{2}+80n+25$ y blancos son (los que nos importan si empezamos en negro) $32n^{2}+40n+12$ y los que están marcados son $f(2n+1)=28n^{2}+36n+12= 7(2n+1)^{2}+4(2n+1)+1$.

Así que en conclusión es $f(n)=7n^{2}+4n+1$ excepto $n=1,2$ en las que $f(1)=8$ y $f(2)=33$.

Enrique dijo...

Pondré la idea del problema. Vemos que si n=1 y n=2, el numero de casillas a las que puede llegar el caballo es 8 y 33, respectivamente. Para n mayor o igual que 3, montamos un plano coordenado ortogonal sobre el tablero de manera que todo punto con coordenadas quede en el centro de alguna casilla y que el caballo empiece en (0,0). Coloreamos el tablero como ajedrez de manera que el caballo empieza en una casilla blanca, con lo que para n par el caballo debe quedar en una casilla blanca y para n par en una casilla negra.

Enrique dijo...

Consideramos O_n el octágono con vértices en (n,2n),(2n,n),(2n,-n),(n,-2n),(-n,-2n),(-2n,-n),(-2n,n),(-n,2n). Denotamos como color n al blanco si n es par y al negro si n es impar. Entonces, demostraremos por inducción que las casillas a las que puede llegar el caballo en n movimientos son las de color n que se encuentran dentro o sobre el borde de O_n para n mayor o igual a 3. Es fácil corroborar que esto se cumple para n=3. Supongamos que se cumple para cierto k=n. Las casillas a las que puede llegar el caballo en k+1 movimientos son aquellas a las que se puede llegar en un movimiento desde una casilla dentro o en el borde de O_k. Vemos que ninguna de dichas casillas queda fuera de O_(k+1). Ademas, podemos llegar a toda casilla de color k+1 en O_(k+1) desde alguna de color k en O_k en un movimiento de caballo. Esto completa la inducción. Es fácil ver que el numero de casillas en O_n es 7n^2+4n+1

Publicar un comentario