ONEM 2018 - Fase 3 - Nivel 2 - P8

Nando

OFO - Mención
Mensajes: 34
Registrado: Mar 31 Jul, 2018 7:39 pm
Medallas: 1

ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por Nando » Mié 13 Mar, 2019 10:47 pm

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.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 82
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por BrunZo » Dom 17 Mar, 2019 5:57 pm

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$

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 846
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por Fran5 » 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... :P
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 82
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por BrunZo » Lun 18 Mar, 2019 8:39 pm

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... :P
¿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. :D

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 846
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por Fran5 » 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" ?
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 82
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por BrunZo » Mar 19 Mar, 2019 12:20 pm

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" ?
Veamos. Haré mi mejor esfuerzo.

Triángulo de Pascal mód 2 = Sierpiński:
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. ∎
Unos en Pascal = $2^{d(n)}$:
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! ∎
Creo que con eso basta. :D

Responder