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

Otra forma de ver esto: para cada tamaño, hay un cuadrado que se mueve dentro del más grande.

¿Cuánto puede moverse? Un cuadrado de tamaño $k\times k$ dentro de un cuadrado de tamaño $n\times n$ tiene $n-k+1$ posiciones posibles en cada dirección (arriba-abajo y izquierda-derecha): considera la posición de la esquina superior izquierda, por ejemplo. Por lo tanto, hay $(n-k+1)^2$ esos cuadrados.

¿Puedes terminar desde aquí?

Answer 2

Otra forma de contar:

Para cada $(i, j, k)$ con $1 \le i, j \le n$ y $0 \le k \le \min(n-i, n-j)$ hay un cuadrado con la esquina superior izquierda en $(i, j)$ y la esquina inferior derecha en $(i+k, j+k).

Por lo tanto, el total es:

$\begin{array}\\ s(n) &=\sum_{i=1}^n \sum_{j=1}^n (1+\min(n-i, n-j))\\ &=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} (1+\min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \min(i, j)\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} \min(i, j)+\sum_{j=i} \min(i, j)+\sum_{j=i+1}^{n-1} \min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} j+i+\sum_{j=i+1}^{n-1} i)\\ &=n^2+\sum_{i=0}^{n-1} (\frac12i(i-1)+i+i(n-1-(i+1)+1))\\ &=n^2+\sum_{i=0}^{n-1} (\binom{i}{2}+i+i(n-i-1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\sum_{i=0}^{n-1} (ni-i(i+1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-\sum_{i=1}^{n} i(i-1)\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-2\binom{n+1}{3}\\ &=\frac13(n+1)n(n-1)\\ \end{array} $

Answer 3

Deje que los vértices de la cuadrícula $n \times n$ sean $\{(x,y)| 0\le x \le n; 0 \le y \le n\}.

(¿Eso es lo que es una cuadrícula $n \times n$? ¿Un $1 \times 1$ tiene $4$ vértices y un cuadrícula $n \times n$ tiene $(n+1)^2$ vértices? ¿O es una cuadrícula $1 \times 1$ un solo punto? Estoy asumiendo lo primero).

Un cuadrado $k \times k$ tendrá un vértice inferior izquierdo en $(x,y)$ y un vértice superior derecho en $(x+k, y+k)$ con la condición $0 \le x; 0 \le y; x+k \le n; y+k \le n$ o en otras palabras: $0 \le x \le n-k; 0 \le y \le n-k.

Hay $n-k+1$ opciones posibles para $x$ y $n-k+1$ opciones para $y$, entonces hay $(n-k+1)^2$ cuadrados $k\times k$.

Entonces el número total de cuadrados es $\sum{k=1}^n(n-k+1)^2$. Deje que $j = n-k+1$ y tenemos #cuadrados = $\sum_{j = n;j--}^1j^2 = \sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}6$.

O para decirlo más simplemente... Un cuadrado $k \times k$ tiene un lado de longitud $k$. Hay $n-(k-1)$ formas de elegir este lado de la cuadrícula que tiene longitud $n$, por lo que para cuadrados de longitudes $1,2, ...., n$ hay $n, n-1....., 1$ forma de elegir el lado horizontal y $n, n-1,...., 1$ formas de elegir los lados verticales. Entonces hay $n^2, (n-1)^2,....., 1^2$ cuadrados posibles $1\times 1, 2\times 2, ...,n \times n$. Entonces hay $\sum k^2 = \frac{n(n+1)(2n+1)}6$ cuadrados totales.

Answer 4

CONSEJO:

Puedes contar la cantidad de cuadrados de lado unitario. Ahora sigue aumentando el lado del cuadrado (a 2, luego a 3 y así sucesivamente) y cuenta la cantidad de cuadrados. Para facilitar las cosas, hay $24^2$ cuadrados unitarios y 1 cuadrado con lado 24. Encuentra los valores intermedios restantes y súmalos.

Answer 5

Esta probablemente no es la forma más elegante o eficiente de resolver el problema, pero fue mi primer pensamiento. La idea esencial es simplemente contar la cantidad de triples ordenados $(i,j,\ell)$ que nos dan cuadrados "válidos".

Hay tres elecciones que hacer: primero, elegir el vértice inferior izquierdo (lo cual requiere dos elecciones: una coordenada $x$ y una coordenada $y$), y luego elegir una longitud de lado. Para hacer el trabajo un poco más fácil, asumamos que la coordenada $x$ es menor que la coordenada $y$. Luego, al final, note que cualquier cuadrado con vértice inferior izquierdo $(i,j)$ y longitud de lado $\ell$ puede ser reflejado para obtener un cuadrado con vértice inferior izquierdo $(j,i)$ y longitud de lado $\ell$ (por lo tanto, el número total se duplica).

Tomando un enfoque más general, responderé la siguiente pregunta:

Sea $C = \{ (i,j) \mid i,j\in\mathbb{N}_0, 0 \le i, j \le N \}$, donde $N \in \mathbb{N}$. ¿Cuántos cuadrados se pueden formar con lados paralelos a los ejes $x$ e $y$, con vértices en $C$?

Un enfoque posible es hacer tres elecciones:

1. elegir la coordenada $x$, $i$, del vértice inferior izquierdo,
2. elegir la coordenada $y$, $j$, del vértice inferior izquierdo, y
3. elegir la longitud de lado, $\ell$, del cuadrado.

Para simplificar ligeramente el razonamiento, hay tres casos que deben ser considerados: $i < j$, $i=j$, y $i > j$. Los dos primeros casos son simétricos, por lo que esto se reduce a contar la cantidad de cuadrados con $i < j$ y duplicarlo, y contar la cantidad de cuadrados con $i=j$.

• Asumamos que $i = j$. La esquina inferior izquierda será de la forma $(i,i)$, donde $i$ es un entero entre $0$ y $N-1$ (inclusive). Una vez que el vértice inferior izquierdo está fijo, el vértice superior derecho es $(i+\ell, i+\ell)$. Por un lado, $\ell$ debe ser al menos $1$. Por otro lado, $$ i + \ell \le 24 \implies \ell \le 24-i. $$ Por lo tanto, la cantidad total de cuadrados que se pueden construir con $i=j$ es $$ \sum_{i=0}^{N-1} \sum_{\ell=1}^{N-i} 1 %= \sum_{i=0}^{N-1} (N-i) %= N^2 - \frac{1}{2}(N-1)N = \frac{1}{2} N (N+1).$$

• Asumamos que $i < j$. La coordenada $x$ del vértice inferior izquierdo, $i$, puede ser cualquier entero de $0$ a través de $N-1$. Una vez fija esta coordenada, la coordenada $y$, $j$, puede ser cualquier entero de $i+1$ a través de $N-1$. Finalmente, la longitud de lado, $\ell$, debe ser al menos $1$, y debe ser elegida de modo que el vértice superior derecho tenga ambas coordenadas no mayores que $N$. Esto significa que $\ell + j \le N$, de lo cual se deduce que $\ell < N - j$. Por lo tanto, la cantidad total de cuadrados que se pueden construir con $i es \begin{align} \sum_{i=0}^{N-1} \sum_{j=i+1}^{N-1} \sum_{\ell = 1}^{N-j} 1 % I'll be honest---I worked this out by hand, then plugged it into WolframAlpha to check. The computation is not hard, but is tedious, so I am going to elide it here entirely. = \frac{1}{6} N(N^2-1) = \frac{1}{6}(N-1)N(N+1). \end{align} Doble esto para concluir que la cantidad total de cuadrados con $i\ne j$ es $$ \frac{1}{3} (N-1)N(N+1). $$

Por lo tanto, la cantidad total de cuadrados que se pueden construir con lados paralelos a los ejes y vértices en el conjunto $C$ es $$ \frac{1}{2} N (N+1) + \frac{1}{3} (N-1)N(N+1) %= N(N+1)\left(\frac{1}{2} + \frac{1}{3}N-\frac{1}{3}\right) = \frac{1}{6}N(N+1)(2N+1). $$

Por ejemplo, con $N=3$, esto da $$ \frac{1}{6}(3)(4)(7) = 14.$$ Es razonablemente fácil verificar a mano que esto es correcto:

En la pregunta realizada aquí, $N=24$. Por lo tanto, hay $$ \frac{1}{6}(24)(25)(49) = 4900 $$ posibles formas de construir cuadrados con vértices paralelos a los ejes y coordenadas entre $0$ y $24$ (inclusive).

---

[1] Para los propósitos de esta pregunta, $0$ no es un número natural. El conjunto $\mathbb{N}_0$ denota el conjunto de números naturales con cero, es decir, el conjunto de enteros no negativos.

NB: He sido atrapado por un nerd con esta pregunta. También sospecho que ha sido duplicada, y que hay una respuesta en el sitio en algún lugar, pero no puedo encontrarla. Así que estoy publicando esta respuesta.