OMA Foros

Spoiler: mostrar

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$

BrunZo escribió: ↑Dom 17 Mar, 2019 5:57 pm

Spoiler: mostrar

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$

Fran5 escribió: ↑Lun 18 Mar, 2019 5:37 pm

BrunZo escribió: ↑Dom 17 Mar, 2019 5:57 pm

Spoiler: mostrar

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...

Fran5 escribió: ↑Lun 18 Mar, 2019 11:06 pm Ay qué bestia que soy! jajaja no sé porqué omití el $2$

De todos modos... podrías demostrar la fórmula? o el hecho de que el triangulo de pascal tenga esa forma tan "fractal" ?

Spoiler: mostrar

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. ∎

Spoiler: mostrar

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! ∎