El siguiente arreglo de números es conocido como el Triángulo de Pascal. Se cumple que todos los números de los bordes izquierdo y derecho son iguales a $1$, además, cualquier otro número es igual a la suma de los dos números que están sobre él.
onem f3n2p8.jpg
Determine cuántos números pares hay en la fila $262$ del Triángulo de Pascal
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
El problema es análogo a contar la cantidad de $0$'s que hay en el Triángulo de Pascal $\mod 2$. Se sabe que las filas $2^n$ a $2^{n+1}-1$ se construyen a partir de dos copias de lo que hay en las filas $0$ a $2^n-1$ (véase Triángulo de Sierpiński). O sea, la cantidad de unos en la fila $262$ será la cantidad de unos en la fila $7$ por $2$. Esto es, $4\cdot 2=8$. Ahora, la cantidad de ceros es $263-8=255$. (Espero que esto valga.)
Quizá sea de interés saber que la cantidad de unos de la fila $n$ está dada por $2^{d(n)}$ donde $d(n)$ es la cantidad de dígitos $1$ en base $2$ de $n$
Quizá sea de interés saber que la cantidad de unos de la fila $n$ está dada por $2^{d(n)}$ donde $d(n)$ es la cantidad de dígitos $1$ en base $2$ de $n$
Pero para $n = 2^k$ se tiene que $d(n) = 1$... y aparece un $1$ a la izquierda y otro $1$ a la derecha.. de modo que hay al menos dos $1$ en vez de uno solo...
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Quizá sea de interés saber que la cantidad de unos de la fila $n$ está dada por $2^{d(n)}$ donde $d(n)$ es la cantidad de dígitos $1$ en base $2$ de $n$
Pero para $n = 2^k$ se tiene que $d(n) = 1$... y aparece un $1$ a la izquierda y otro $1$ a la derecha.. de modo que hay al menos dos $1$ en vez de uno solo...
¿Eh? O sea, tenés en total $2^{d(n)}=2^1=2$ unos en la $2^k$-ésima fila: uno a la derecha y uno a la izquierda. O sea, hay $2^{d(n)}$ unos, no $d(n)$.
PD: La formulita simplemente la saqué de Internet.
Vamos a demostrar que la fila $2^k-1$ es $111...111$ para $k>1$.
Para demostrar esto, procederemos por inducción:
Es claro que la fila $2^1-1=1$ cumple.
Ahora, si cumple para $2^k-1$, vamos a demostrar que se cumple para $2^{k+1}-1$. Si la fila $2^k-1$ tiene esa forma, la fila $2^k$ será $100...001$, y podremos deducir que el triángulo va a crecer con dos copias de sí mismo (esto ocurre ya que tenemos dos "semillas" en los extremos de esa fila.) Haciendo las cuentas necesarias [no tengo muchas ganas de hacerlas] podemos ver que, en efecto, el fractal se copia por completo, finalizando la fila $2^{k+1}-1$. Ahora, en la fila $2^{k+1}-1$, van a haber dos copias exactas de la fila $2^k-1$, que por hipótesis inductiva es $111...111$, de modo que, la fila $2^{k+1}-1$ será $111...111111...111$ como queríamos.
Con esto y repitiendo el argumento de las dos semillas, podemos ver que Pascal mód 2 efectivamente se construye a partir de réplicas de si mismo, a modo de Sierpiński. Con eso estamos. ∎
Vamos a aplicar inducción fuerte, usando los resultados obtenidos en lo anterior:
Es claro que las primeras filas cumplen (se puede checkear a mano.)
Ahora, si se cumple para las filas de $0$ a $2^k-1$, vamos a demostrar que se cumple para las filas de $2^k$ a $2^{k+1}$. Por todo lo que dijimos antes, es bastante notorio que si en la fila $n$ con $0\leq n\leq 2^k-1$ hay $2^{d(n)}$ unos, en la fila $n+2^k$, que cumplirá $2^k\leq n+2^k\leq 2^{k+1}-1$, habrá
$$2\cdot 2^{d(n)}=2^{d(n)+1}=2^{d(n+2^k)}$$
unos. ¡Estamos! ∎