De sumas de cuadrados y dobles conteos

Pues el otro dia (hoy, pero bueno, pronto sera “otro dia”) estaba algo aburrido y me puse a jugar un rato a ver si podían salir cosas padres de cosas ya conocidas, y pues afortunadamente me salió una cosa padre de una conocida.

Quizás varias veces se han enfrentado con el problema “¿Cuántos cuadrados hay en un tablero de nxn cuyos lados sean paralelos a los lados de la cuadricula?”. Si no lo han hecho les recomiendo ampliamente que lo intenten antes de continuar leyendo.

Pues bueno, la respuesta facil es contarlos por tamaño ¿Cuántos hay de 1×1? ¿Cuántos de 2×2?, etc. Pues de 1×1 hay n^2, de 2×2 hay (n-1)^2, … de nxn solo hay 1 (checalo). Pues entonces la cantidad de cuadritos en un tablero de nxn es:

1^2+2^2+3^2+...+n^2

Ok, entonces uno puede ser feliz y pensar que aqui se acaba todo. Pero no, ahi me tienen dandole vueltas al asunto tratando de ver que mas se puede encontrar. ¿Por qué no contar de nuevo los cuadritos? Tras varios intentos fallidos de hacer esto, encuentro un nuevo metodo rebuscado para contar los cuadritos, que mas o menos dice asi:

Fíjense en todas las diagonales de 45 grados que van en una sola dirección, por ejemplo, de arribaderecha a abajoizquierda. Si se fijaron en todas deben de ser 2n+1. Hay dos con 2 puntos, dos con 3, dos con 4, … y UNA con n+1 puntos, ¿de acuerdo?. Pues resulta que un cuadrito de los que queremos esta determinado al seleccionar una diagonal y dos puntos en ella, y esto cuenta todos los cuadritos (verifiquenlo), entonces podemos contar todos los cuadritos por:

{2 \choose 2}+{3 \choose 2}+...+{n+1 \choose 2}  +  {2 \choose 2}+{3 \choose 2}+... + {n \choose 2}

En algun momento vimos que {2 \choose 2}+{3 \choose 2}+...{k \choose 2}={k+1 \choose 3}, asi que la cantidad de cuadritos la podemos simplificar a:

{n+2 \choose 3}+{n+1 \choose 3} = \frac{(n+2)!}{3!(n-1)!}+\frac{(n+1)!}{3!(n-2)!} =\frac{(n+2)(n+1)(n)+(n+1)(n)(n-1)}{3!} =
\frac{(n+1)(n)(2n+1)}{6}.

Wow, que bien, pues resulta que todo el tiempo contamos lo mismo, esto es, cuadritos. Como contamos la misma cosa entonces los dos resultados deben de ser los mismos. ¿Qué nos dice esto? Pues que:
1^2+2^2+3^2+...+n^2 = \frac{(n+1)(n)(2n+1)}{6}

¿Padre? Bueno, ya saben, para la proxima cuenten dos veces. Pueden intentar hacer algo parecido con la suma de cubos, pero me parece que ahi ya se complica un poco. Suerte, feliz navidad y feliz año nuevo. Si tienen cualquier duda en algun paso o lo que sea escribanme para intentar ser mas claro.

Saludos
Leo

6 comentarios en “De sumas de cuadrados y dobles conteos

  1. excelente! jejejeje
    he estado muy desconectado de la olimpiada, pero ya estoy recuperando el ritmo :)

    Una pregunta intersante sobre tu post es si habrá alguna representación gráfica que permita contar mas fácil la suma …

  2. vwdvwvvwvewvwevewvwefewfcewncfuer nhrev rnehv r efvrenhvrevhervuevhervreivhervrehveuvhvuvhvhvhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

  3. q bonito…
    aunque si eso haces cuando te aburres… no puedo esperar ver que harás cuando te diviertas, haha

    0 7 8 22 23 55 56 66 88 109 125

incluye tu respuesta

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s