Ibero 2003 - P4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años 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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2003 - P4

Mensaje sin leer por Gianni De Rico »

Sea $M=\{1,2,\ldots ,49\}$ el conjunto de los primeros $49$ enteros positivos. Determine el máximo entero $k$ tal que el conjunto $M$ tiene un subconjunto de $k$ elementos en el que no hay $6$ números consecutivos. Para ese valor máximo de $k$, halle la cantidad de subconjuntos de $M$, de $k$ elementos, que tienen la propiedad mencionada.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Carrrrr
Mensajes: 1
Registrado: Lun 09 Mar, 2020 12:56 pm
Nivel: 3

Re: Ibero 2003 - P4

Mensaje sin leer por Carrrrr »

Es mi primer post, espero que esté bien. :D
Spoiler: mostrar
Vamos a demostrar que el máximo $k$ es $41$. Un ejemplo es sencillo retirando los $8$ múltiplos de $6$ que tenemos y obteniendo así: $A=\{1;2;3;4;5;7;8;9;10;11;13;14;\dots ; 46;47;49\}$.
Demostraremos que con $k\geq 42$ no es posible.
Para ello, veamos que retirando $7$ elementos, podemos pensar que el conjunto se dividida en $8$ intervalos de números consecutivos (pueden haber intervalos vacíos). Por ejemplo si retiramos el número $10$, obtenemos los intervalos $[1;9]$ y $[11;49]$. Si los intervalos son de la longitud máxima (es decir, tienen $5$ elementos). En total estaríamos cubriendo $40$ números, pero tenemos $42$ para repartir, y eso nos obliga a tener un intervalo mayor que $6$, por lo que no es posible debido a la condición que nos impone el enunciado.

Para ver de cuántas formas, podemos pensar el problema de nuevo, como $9$ intervalos, donde la suma de la cantidad de los elementos de cada intervalos, nos de como resultado $41$, siempre en cuando ningún intervalos tenga una cantidad mayor o igual a $6$ elementos. Para ello lo pensamos de la siguiente manera:
Supongamos que en un principio, los $9$ intervalos tienen $5$ elementos cada uno, dando un total de $45$ números. La pregunta es, de cuántas formas puedo retirarles $4$ elementos entre los $9$ que tengo en el total.

Si de los $9$ intervalos, decidimos restarle al menos un elemento a $4$ de ellos, entonces nos obliga a quitarle exactamente $1$ a cada elemento. Entonces la cuenta es sencilla, tenemos $\binom{9}{4}=126$ combinaciones, tales que $5$ intervalos tengan $5$ elementos y los otros $4$ tengas $4$ elementos.

Si de los $9$ intervalos, decidimos restarle al menos un elemento a $3$ de ellos, entonces nos obliga a quitarle exactamente $2$ a un intervalo, y $1$ a los restantes. Pero notemos, si elegimos $3$ intervalos, luego podes reacomodar de $3$ formas distintas. (1 1 2 ; 1 2 1; 2 1 1). Por lo que la cantidad de combinaciones es de $\binom{9}{3}\cdot 3=252$.

Si de los $9$ intervalos, decidimos restarle al menos un elemento a $2$ de ellos, entonces nos permite hacer las siguientes distribuciones:
2 2 ---> Nos da $\binom{9}{2}=36$
3 1 ---> Nos da $\binom{9}{2}\cdot 2=72$

Por último, si de los $9$ intervalos decidimos restarle al menos un elemento a $1$ de ellos, entonces nos obliga sacarle $4$ elementos a ese único intervalo que elegimos, por lo que nos da:
$\binom{9}{1}=9$.
Finalmente, la cantidad total de combinaciones es $126+252+36+72+9=495$.
4  
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: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Ibero 2003 - P4

Mensaje sin leer por Matías V5 »

Hola Carrrrr!

Creo que tu solución está perfecta. Un comentario:
Spoiler: mostrar
Vos llegás a que para resolver el problema hay que contar de cuántas maneras se puede elegir $4$ elementos para retirar en los $9$ intervalos. Eso sería lo mismo que preguntarse de cuántas maneras se pueden distribuir $4$ bolitas en $9$ cajas. Hay una fórmula para eso: viewtopic.php?f=5&t=49
En este caso nos da $\binom{4+9-1}{9-1} = \binom{12}{8} = 495$, y te ahorrás el análisis de casos.
Saludos!
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
Responder