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=KzTR72_srTU
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
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
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.
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$.
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$.
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.