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.
Suscribirse a:
Comentarios de la entrada (Atom)
12 comentarios:
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.
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.
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.
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.
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.
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.
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$.
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.
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$.
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.
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