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