Regional 2022 N3 P1

Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1068
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Regional 2022 N3 P1

Mensaje sin leer por Matías V5 »

Una sucesión creciente de números naturales se dice impar-par si cada término en una posición impar es impar y cada término en una posición par es par. Todas las sucesiones crecientes impar-par cuyos términos son menores o iguales que $4$ son: $\{1\}, \{3\}, \{1,2\}, \{1,4\}, \{3,4\}, \{1,2,3\}$ y $\{1,2,3,4\}$.
Determinar la cantidad de sucesiones crecientes impar-par cuyos términos son menores o iguales que $10$.
Nota. Una sucesión se dice creciente si cada término es mayor que el término que lo precede.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y
konnyg
Mensajes: 2
Registrado: Jue 30 Jun, 2022 9:54 pm

Re: Regional 2022 N3 P1

Mensaje sin leer por konnyg »

Spoiler: mostrar
Puede ser 143?
Regional
Mensajes: 2
Registrado: Jue 08 Sep, 2022 10:14 pm

Re: Regional 2022 N3 P1

Mensaje sin leer por Regional »

Alguien me podría decir el procedimiento? :geek:
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 566
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 15
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Regional 2022 N3 P1

Mensaje sin leer por Turko Arias »

Regional escribió: Jue 08 Sep, 2022 10:15 pm Alguien me podría decir el procedimiento? :geek:
Spoiler: mostrar
Regional.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
1  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Regional
Mensajes: 2
Registrado: Jue 08 Sep, 2022 10:14 pm

Re: Regional 2022 N3 P1

Mensaje sin leer por Regional »

JAJAJAJ no puedo creer que hiciste un meme conmigo, pero necesito el procedimiento para saber si lo hice bien :cry:
FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 45
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 8
Nivel: 3
Ubicación: Corrientes

Re: Regional 2022 N3 P1

Mensaje sin leer por FabriATK »

Regional escribió: Jue 08 Sep, 2022 10:43 pm JAJAJAJ no puedo creer que hiciste un meme conmigo, pero necesito el procedimiento para saber si lo hice bien :cry:
Te digo así más o menos lo que hice yo
Spoiler: mostrar
Sea S(n) la cantidad de sucesiones con los términos menores o iguales que n.
Ponele que vos sabés cuánto vale s(4). Ahora, si querés saber cuánto vale s(5) tenés en cuenta un par de cosas.
Cualquier sucesión que se cuente en s(4) también se va a contar en s(5). Pero en s(5) se agregan algunas: básicamente, se agregan todas las que tienen el 5. Cómo las sucesiones son crecientes, el 5 se agrega al final. Cómo son impar-par, el 5 sólo puede agregarse en las sucesiones que terminaban en un par. Además se agrega la sucesión {5}.
Con todos los impares pasa los mismo, y con los pares algo parecido(se agregan al final de las que terminaban en impar)
A partir de ahí te podés armar un cuadrito, que para n te diga s(n), el número de sucesiones terminadas en par y el números de sucesiones terminadas en impar. Haces eso con n desde 1 hasta 10 y estás.
Así a mí me dió 143
1  
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 566
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 15
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Regional 2022 N3 P1

Mensaje sin leer por Turko Arias »

Una solución que me gustó bastante
Spoiler: mostrar
Vamos a hacer las siguientes dos observaciones, que nos van a permitir resolver el problema de manera rápida e incluso, nos permite resolver en poco tiempo el problema reemplazando la cantidad $10$ por otro número que queramos.
Supongamos que tenemos escritas en el pizarrón todas las sucesiones crecientes impar-par que cuyos términos son todos menores o iguales que $n-1$, supongamos que $I_{n-1}$ de estas tienen longitud impar y $P_{n-1}$ tienen longitud par. Ahora, tiene sentido pensar que si queremos escribir todas las sucesiones crecientes impar- par con términos menores o iguales que $n$ podamos "reciclar" algunas de las escritas. Separemos en dos casos:
Si $n$ es par:
Notemos que al final de cada sucesión de longitud impar de las ya escritas, podemos escribir el número $n$ y obtenemos una nueva sucesión creciente impar-par pero ahora de longitud par. Además, podemos tomar cualquier sucesión de longitud par de las que servían en el caso de $n-1$ y dejarla tal cual sin modificarla, y seguiría funcionando. Además, notemos que no podemos generar una sucesión de longitud par que no provenga de una de longitud impar. Entonces, si la cantidad de sucesiones de longitud par actual es $P_n$, tenemos que $P_n=P_{n-1}+I_{n-1}$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud impar, porque entonces $n$ que es par estaría en posición impar, por lo que si $I_n$ es la cantidad de sucesiones de longitud impar, tenemos que $I_n=I_{n-1}$.

Si $n$ es impar:
Un razonamiento análogo al anterior, nos permite deducir que añadiendo $n$ al final de cada sucesión de longitud par ya escrita, podemos escribir el número $n$ y obtenemos una que cumple lo pedido pero de longitud impar. Además, podemos tomar cualquier sucesión de longitud impar y dejarla como estaba y también sirve. Además, notemos que la única sucesión de longitud impar que no provenga de una de longitud impar que podemos formar es la que tiene solo a $n$. Tenemos entonces que si la cantidad de sucesiones de longitud impar actual es $I_n$ entonces $I_n=P_{n-1}+I_{n-1}+1$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud par, porque entonces $n$ que es impar estaría en posición par, por lo que si $P_n$ es la cantidad de sucesiones de longitud par, tenemos que $P_n=P_{n-1}$.


Teniendo esto en cuenta, de repente podemos calcular con un par de sumas, sabiendo la cantidad de sucesiones crecientes impar-par de elementos hasta $k$ de longitud par y la cantidad de longitud impar, la cantidad de sucesiones de longitud par y de longitud impar pero yendo hasta $k+1$.

Para finalizar, agrego un cuadrito que fui completando con este método con los primeros resultados:
Tabla P1 Regional N3 2022.jpg
Para ver en ejemplo concreto el método aplicado, notamos que el $11$ es impar, así que en la fila de longitud par sigue el mismo número, y en la fila de longitud impar sumamos los de longitud par e impar del $10$ y le sumamos $1$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
2  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Sarita :)
Mensajes: 1
Registrado: Vie 09 Sep, 2022 12:01 am
Nivel: 3

Re: Regional 2022 N3 P1

Mensaje sin leer por Sarita :) »

Turko Arias escribió: Vie 09 Sep, 2022 12:14 am Una solución que me gustó bastante
Spoiler: mostrar
Vamos a hacer las siguientes dos observaciones, que nos van a permitir resolver el problema de manera rápida e incluso, nos permite resolver en poco tiempo el problema reemplazando la cantidad $10$ por otro número que queramos.
Supongamos que tenemos escritas en el pizarrón todas las sucesiones crecientes impar-par que cuyos términos son todos menores o iguales que $n-1$, supongamos que $I_{n-1}$ de estas tienen longitud impar y $P_{n-1}$ tienen longitud par. Ahora, tiene sentido pensar que si queremos escribir todas las sucesiones crecientes par-impar con términos menores o iguales que $n$ podamos "reciclar" algunas de las escritas. Separemos en dos casos:
Si $n$ es par:
Notemos que al final de cada sucesión de longitud impar de las ya escritas, podemos escribir el número $n$ y obtenemos una nueva sucesión creciente impar-par pero ahora de longitud par. Además, podemos tomar cualquier sucesión de longitud par de las que servían en el caso de $n-1$ y dejarla tal cual sin modificarla, y seguiría funcionando. Además, notemos que no podemos generar una sucesión de longitud par que no provenga de una de longitud impar. Entonces, si la cantidad de sucesiones de longitud par actual es $P_n$, tenemos que $P_n=P_{n-1}+I_{n-1}$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud impar, porque entonces $n$ que es par estaría en posición impar, por lo que si $I_n$ es la cantidad de sucesiones de longitud impar, tenemos que $I_n=I_{n-1}$.

Si $n$ es impar:
Un razonamiento análogo al anterior, nos permite deducir que añadiendo $n$ al final de cada sucesión de longitud par ya escrita, podemos escribir el número $n$ y obtenemos una que cumple lo pedido pero de longitud impar. Además, podemos tomar cualquier sucesión de longitud impar y dejarla como estaba y también sirve. Además, notemos que la única sucesión de longitud impar que no provenga de una de longitud impar que podemos formar es la que tiene solo a $n$. Tenemos entonces que si la cantidad de sucesiones de longitud impar actual es $I_n$ entonces $I_n=P_{n-1}+I_{n-1}+1$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud par, porque entonces $n$ que es impar estaría en posición par, por lo que si $P_n$ es la cantidad de sucesiones de longitud par, tenemos que $P_n=P_{n-1}$.


Teniendo esto en cuenta, de repente podemos calcular con un par de sumas, sabiendo la cantidad de sucesiones crecientes impar-par de elementos hasta $k$ de longitud par y la cantidad de longitud impar, la cantidad de sucesiones de longitud par y de longitud impar pero yendo hasta $k+1$.

Para finalizar, agrego un cuadrito que fui completando con este método con los primeros resultados:

Tabla P1 Regional N3 2022.jpg

Para ver en ejemplo concreto el método aplicado, notamos que el $11$ es impar, así que en la fila de longitud par sigue el mismo número, y en la fila de longitud impar sumamos los de longitud par e impar del $10$ y le sumamos $1$.
entonces que te quedó como resultado final?
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 566
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 15
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Regional 2022 N3 P1

Mensaje sin leer por Turko Arias »

Sarita :) escribió: Vie 09 Sep, 2022 11:20 am
Turko Arias escribió: Vie 09 Sep, 2022 12:14 am Una solución que me gustó bastante
Spoiler: mostrar
Vamos a hacer las siguientes dos observaciones, que nos van a permitir resolver el problema de manera rápida e incluso, nos permite resolver en poco tiempo el problema reemplazando la cantidad $10$ por otro número que queramos.
Supongamos que tenemos escritas en el pizarrón todas las sucesiones crecientes impar-par que cuyos términos son todos menores o iguales que $n-1$, supongamos que $I_{n-1}$ de estas tienen longitud impar y $P_{n-1}$ tienen longitud par. Ahora, tiene sentido pensar que si queremos escribir todas las sucesiones crecientes par-impar con términos menores o iguales que $n$ podamos "reciclar" algunas de las escritas. Separemos en dos casos:
Si $n$ es par:
Notemos que al final de cada sucesión de longitud impar de las ya escritas, podemos escribir el número $n$ y obtenemos una nueva sucesión creciente impar-par pero ahora de longitud par. Además, podemos tomar cualquier sucesión de longitud par de las que servían en el caso de $n-1$ y dejarla tal cual sin modificarla, y seguiría funcionando. Además, notemos que no podemos generar una sucesión de longitud par que no provenga de una de longitud impar. Entonces, si la cantidad de sucesiones de longitud par actual es $P_n$, tenemos que $P_n=P_{n-1}+I_{n-1}$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud impar, porque entonces $n$ que es par estaría en posición impar, por lo que si $I_n$ es la cantidad de sucesiones de longitud impar, tenemos que $I_n=I_{n-1}$.

Si $n$ es impar:
Un razonamiento análogo al anterior, nos permite deducir que añadiendo $n$ al final de cada sucesión de longitud par ya escrita, podemos escribir el número $n$ y obtenemos una que cumple lo pedido pero de longitud impar. Además, podemos tomar cualquier sucesión de longitud impar y dejarla como estaba y también sirve. Además, notemos que la única sucesión de longitud impar que no provenga de una de longitud impar que podemos formar es la que tiene solo a $n$. Tenemos entonces que si la cantidad de sucesiones de longitud impar actual es $I_n$ entonces $I_n=P_{n-1}+I_{n-1}+1$. Por último, notemos que agregando $n$ no podemos crear ninguna sucesión de longitud par, porque entonces $n$ que es impar estaría en posición par, por lo que si $P_n$ es la cantidad de sucesiones de longitud par, tenemos que $P_n=P_{n-1}$.


Teniendo esto en cuenta, de repente podemos calcular con un par de sumas, sabiendo la cantidad de sucesiones crecientes impar-par de elementos hasta $k$ de longitud par y la cantidad de longitud impar, la cantidad de sucesiones de longitud par y de longitud impar pero yendo hasta $k+1$.

Para finalizar, agrego un cuadrito que fui completando con este método con los primeros resultados:

Tabla P1 Regional N3 2022.jpg

Para ver en ejemplo concreto el método aplicado, notamos que el $11$ es impar, así que en la fila de longitud par sigue el mismo número, y en la fila de longitud impar sumamos los de longitud par e impar del $10$ y le sumamos $1$.
entonces que te quedó como resultado final?
Spoiler: mostrar
143, fijate que en la tablita en la columna del 10 está
1  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 181
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 8
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Regional 2022 N3 P1

Mensaje sin leer por Fedex »

Spoiler: mostrar
Sea $T(n)$ las sucesiones crecientes impar-par con términos $\leq n$.
Descomponemos $T(n) = L_i(n) + L_p(n)$ como la cantidad de sucesiones de largo impar y par respectivamente.
Notar que $L_i(2n) = L_i(2n-1)$ ya que realmente no podemos usar el $2n$ en una de largo impar y también $L_p(2n) = L_p(2n-2) + L_i(2n-1)$ donde el primer sumando es en caso de que no hayamos usado $2n$ en el ultimo lugar y el segundo es en caso de que si lo hayamos hecho. Como también $L_p(2n-2) = L_p(2n-1)$ sumando ambas tenemos:
$$T(2n) = T(2n-1) + L_i(2n-1) = 2T(n-1) - L_p(2n-1) = 2T(n-1) - L_p(2n-2)$$
Ahora haciendo lo mismo de antes $L_p(2n-2) = L_p(2n-4) + L_i(2n-3) = L_p(2n-3) + L_i(2n-3) = T(2n-3)$.
Teniendo la recurrencia:
$$T(n) = 2T(n-1) - T(n-3)$$
Para $n$ par. Basta checkear que se da lo mismo para $n$ impar para afirmar que se da para todo $n \geq 5$ (esto ya que en nuestro desarrollo bajamos hasta $n-4$ y $T(n-4)$ solo esta bien definido para $n-4 \geq 1$).
Calculando los primeros $4$ valores a mano podemos encontrar $T(10)$ usando esa formulita.
Aunque un dato gracioso es que en general $T(n) = F_{n+2} - 1$ donde $F_n$ es el $n$-esimo numero de Fibonacci.
This homie really did 1 at P6 and dipped.
Responder