ONEM 2018 - Fase 3 - Nivel 2 - P8

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nando

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

ONEM 2018 - Fase 3 - Nivel 2 - P8

Mensaje sin leer por Nando »

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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

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

Mensaje sin leer por BrunZo »

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 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

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

Mensaje sin leer por Fran5 »

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 //
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

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

Mensaje sin leer por BrunZo »

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 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

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

Mensaje sin leer por Fran5 »

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 //
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

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

Mensaje sin leer por BrunZo »

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