Dado un cuadrado de $n \times n$, ¿cuántos cuadrados existen?

Question

¿Cuántos cuadrados existen en una rejilla de $n \times n$? Obviamente hay $n^2$ cuadrados pequeños, y $4$ cuadrados de tamaño $(n-1) \times (n-1)$.

¿Cómo puedo contar el número de cuadrados de cada tamaño?

Answer 1

Esto se puede demostrar usando inducción. Para simplificar la discusión, usaré la frase "una $n\times n$ cuadrícula" para denotar ese conjunto $$ \{ (i,j) : i,j\in\mathbb{Z}, 0 \le i,j \le n \}. $$

Proposición: Es posible construir $\sum_{j=1}^{n} j^2$ cuadrados en una $n\times n$ cuadrícula, donde todos los cuadrados tienen lados paralelos a los ejes.

Prueba: Como base para la inducción, observemos que cuando $n=1$, solo es posible construir un cuadrado (es decir, el cuadrado con vértices $(0,0)$, $(1,0)$, $(1,1)$ y $(0,1)$). Notar que $$ \sum_{j=1}^{1} j^1 = 1, $$ lo cual completa el caso base.

Para la inducción, supongamos que es posible construir $$ \sum_{j=1}^{k} j^2 \tag{IH}\label{ih}$$ cuadrados en una cuadrícula de $k\times k$ con lados paralelos a los ejes (nota: esto está etiquetado como (\ref{ih}), ya que es la hipótesis de inducción).

Primero observar que cada cuadrado en una cuadrícula de $k\times k$ también es un cuadrado en una cuadrícula de $(k+1)\times (k+1)$. Los únicos cuadrados en la cuadrícula más grande que no se cuentan aquí son aquellos con un vértice que tiene ya sea una coordenada $x$ o $y$ de $n$. Para contar estos, notar que para cada elección de $(i,j)$ en la cuadrícula de $k\times k$, hay exactamente un cuadrado con vértice inferior izquierdo en $(i,j)$, y un vértice en $(i,n)$ o $(n,j)$. Así que expandir la cuadrícula en una unidad en ambas direcciones agrega un total de $(k+1)^2$ nuevos cuadrados (tanto $i$ como $j$ pueden ser elegidos libremente entre $0$ y $k$, inclusive). Por lo tanto, el número de cuadrados en una cuadrícula de $(k+1)\times (k+1)$ está dado por $$ (\text{el número de cuadrados en una cuadrícula de $k\times k$}) + (k+1)^2 \underset{\ref{ih}}{=} \left[\sum_{j=1}^{k} j^2\right] + (k+1)^2 = \sum_{j=1}^{k+1} j^2, $$ que es el resultado deseado.

---

NB: Me han atrapado por este problema de nerds. También sospecho que está duplicado, y que hay una respuesta en algún lugar del sitio, pero no puedo encontrarla. Así que estoy publicando esta respuesta.

Answer 2

NOTA:

Para una cuadrícula de $n\times n$ la respuesta es $n^2+(n-1)^2+(n-2)^2+.....+1^2$

Entonces, la respuesta es $$ \frac{n(n+1)(2n+1)}{6} $$