Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






+2 votos

Hallar la cantidad de cuadrados si la siguiente tabla es:

1. De dimensiones nxn

2. De dimensiones nxm

por (710 puntos) en Combinatoria
recategorizada por

2 Respuestas

+2 votos

Respuesta parcial.

1.

Para $n=1$ hay $0$ cuadros.

Para $n=2$ hay $1$ cuadro.

Para $n=3$ hay $4$ cuadros pequeños y $2$ cuadros de tamaño grande (como en la figura de abajo).



Para $n=4$ hay $9$ cuadros de tamaño $1$, hay $2*4$ cuadros de tamaño $2$, hay $3$ cuadros de tamaño $3$ (como en la figura de abajo).



En general hay $(n-1)^2$ cuadros de tamaño $1$, $2*(n-2)^2$ cuadros de tamaño $2$,...,$i(n-i)^2$ cuadros de tamaño $i$,...,y $(n-1)$ cuadros de tamaño $n-1$.

Por lo tanto hay $\sum i(n-i)^2$ para $i\in\{1,...,n-1\}$. Esto es $n^2(n^2-1)/12$.

por (6,2m puntos)
editado por
De pronto no entiendo bien tu manera de contar. Me parece, por ejemplo, que para $n=4$ hay 9 cuadrados de tamaño 2 y 4 de tamaño 4. Y también (aunque esto es bastante trivial y no muy esencial), para cada $n$ se te está escapando contar el cuadro de tamaño $n$.
Creo que hay un problema en la cuenta. Yo diría (Digo) que hay $n^{2}$, cuadrados de tamaño 1, $(n-1)^{2}$ cuadros de tamaño 2 y así hasta tener 1 de lado n (Aunque con eso ya estaría resuelto el problema para n=m).
Bueno, lo único que consideré fue que los vértices de los cuadros fueran vértices en la cuadrícula.
Ya entiendo, contaste todos los cuadrados que se pudieran armar, no solo aquellos cuyas aristas estuvieran en la gráfica, y estás tomando n como la cantidad de puntos en el lado, y no la longitud del lado. Eso arma un problema más general, interesante.
Me parece que ya es claro como contar: $\sum i(n-i)(m-i)$ si se cuentan cuadrados rotados, o $\sum (n-i)(m-i)$ si no (las sumas son para $i\in \{1,..., min\{n,m\}-1\}$ y para el caso de una malla de $nm$ vértices).
+2 votos

Ya clarificó el compañero Chris de qué manera entendió él el problema, y ya presentó una respuesta parcial. La manera como yo entendí la pregunta, era que había que contar el número de cuadrados que son una unión de cuadrados unitarios (es decir, "cuadrado de tamaño $n$" significa cuadrado de lados paralelos a los ejes cartesianos, con vértices en los puntos de la retícula y cuyo lado tiene longitud $n$).

 Así, supongamos que tenemos una cuadrícula de dimensiones $n\times m$ y supongamos, por simplicidad, que $n\leq m$. Contemos los cuadrados de tamaño $k$ dentro de esta cuadrícula (obviamente, para que esto tenga sentido, necesitamos que $1\leq k\leq n$). Digamos que indexamos los cuadrados de nuestra cuadrícula, contando de izquierda a derecha y de abajo hacia arriba (entonces, el cuadrado del extremo inferior izquierdo es el que tiene índice $(1,1)$, el del extremo inferior derecho tiene índice $(n,1)$, el de la esquina superior izquierda tiene índice $(1,m)$ y el cuadrado de la esquina superior derecha está indexado por $(n,m)$). Nótese que cada cuadrado de tamaño $k$ tiene una esquina inferior izquierda, cuyo índice $(i,j)$ debe de satisfacer que $i+k-1\leq n$ y $j+k-1\leq m$ (pues de lo contrario el cuadrado "se saldría" de nuestra cuadrícula). Por lo tanto, el índice $(i,j)$ de la esquina inferior izquierda de cualquier cuadrado de tamaño $k$ debe satisfacer que $i\leq n+1-k$ y $j\leq m+1-k$. Recíprocamente, para cada cuadrado cuyo índice $(i,j)$ satisface las desigualdades previas, es posible utilizarlo como esquina inferior izquierda de un cuadrado de tamaño $k$ (pues las desigualdades aseguran que dicho cuadrado "sí cabe" dentro de nuestra cuadrícula). Finalmente, es claro que distintos cuadrados de tamaño $k$ tienen distinta esquina inferior izquierda. Lo que esto muestra es que los cuadrados de tamaño $k$ están en biyección con los pares $(i,j)$ con $1\leq i\leq n+1-k$ y $1\leq j\leq m+1-k$, por lo tanto hay $(n+1-k)(m+1-k)$ de ellos. Esto significa que el número total de cuadrados en la retícula de tamaño $n\times m$ es:

$\sum\limits_{k=1}^{\min\{n,m\}}(n+1-k)(m+1-k)$.

Cualquier sugerencia para simplificar esta expresión será bienvenida. En el caso particular cuando $n=m$ obtenemos $\sum_{k=1}^n(n+1-k)^2=\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$.

por (15,5m puntos)
Yo lo resolví de este modo.
Al contar, tenemos que hay $n^{2}$, cuadrados de tamaño 1, $(n−1)^{2}$ cuadros de tamaño 2 y así hasta tener 1 de lado n.
De este modo tenemos el resultado para n=m, que es el que has dicho.

Si suponemos que n<m, entonces sea k=m-n.
Tomando el caso del cuadrado de nxn, tenemos la fórmula para $a_{n}$ (Cantidad de cuadrados en una tabla cuadrada). Si le añadimos una columna, estamos añadiendo n cuadrados de tamaño 1, n-1 cuadrados de tamaño 2, y así. De ahí añadiendo k columnas (Para un total de m columnas), tenemos $b_{nm}=a_n+kn(n+1)/2$.
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...