Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Si quitamos los ocho múltiplos de $6$ nos quedan $41$ números que cumplen la propiedad ya que hemos dejado ocho bloques de 5 números consecutivos más el número 49 aislado. Veamos que si se omiten sólo 7 números, entonces tienen que quedar seis consecutivos, lo que nos dirá que $41$ es la respuesta. Si vemos estos siete números como separadore, los otros 42 números restantes quedarán separados en 8 grupos de números consecutivos. Si los 8 grupos tuvieran 5 o menos números, entonces tendríamos máximo $5\cdot 8=40$, pero hay 42, lo que nos dice que habrá 6 o más consecutivos (principio del palomar).

Veamos finalmente cuántos subconjuntos de $41$ elementos tienen la propiedad. Al igual que antes, al omitir 8 números, podemos transformar el problema en elegir 9 números $a_1,a_2,\ldots,a_9$ entre $1$ y $5$ que dirán la cantidad de números consecutivos que habrá entre cada uno de los 8 que se omiten. Como tiene que ser $a_1+a_2+\ldots+a_9=41$, podemos pensar en hacer $a_1=a_2=\ldots=a_9=5$ (el máximo) y luego restarle $1$ a cuatro de los nueve números (posiblemente con repetición). Esto no son más que combinaciones con repetición, que equivalen a su vez a elegir como separadores 9 elementos de un conjunto de $4+9=13$ elementos. Por tanto, tenemos un total de $\binom{13}{9}=\binom{13}{4}=715$ subconjuntos de $41$ elementos con la propiedad del enunciado.

Solución. Veamos en primer lugar cómo conseguir el máximo usando un razonamiento voraz. Supongamos que $k$ es el máximo y que $S$ es un subconjunto de $k$ elementos en el que no hay 6 números consecutivos. Tenemos dos propiedades importantes:

• Si $S$ omitiera dos o más números consecutivos $n,n+1,\ldots,n+a$, entonces podríamos restarle $a$ unidades a todos los elementos de $S$ mayores que $n+a$ y tendríamos un conjunto $S'$ con el mismo número de elementos y también cumpliendo la propiedad. Si $n+a=49$, podríamos añadirle más números a partir del $n+1$ y tendríamos $S'$ con más elementos, luego $S$ no sería el conjunto de más elementos.
• Si $S$ no contiene dos números $n$ y $n+a$ pero sí los intermedios $n+1,\ldots,n+a-1$, entonces tiene que ser $a\leq 6$ para que haya máximo cinco consecutivos. Si fuera $n+a\leq 6$, podemos añadir los números desde el $1$ hasta el $n$ y obtenemos un conjunto que cumple la propiedad con más elementos. Si fuera $a\lt 6$ (hay menos de 5 consecutivos), entonces podemos añadir $n+a$ al conjunto y sumarle una unidad a todos los elementos de $S$ mayores o iguales que $n+a$. Repitiendo el proceso, llegamos a un conjunto $S'$ con al menos el mismo número de elementos de $S$ y que tiene a $n+1,n+2,n+3,n+4,n+5$ pero no a $n$ ni $n+6$.

Estas idas nos dicen que un ejemplo de subconjunto $S\subset M$ con la mayor cantidad de números (sin 6 consecutivos) consiste en tomar 5 consecutivos, omitir el sexto, luego 5 consecutivos y omitir el sexto, y así sucesivamente. Como $49=8\cdot 6 +1$, tenemos que hay que omitir un mínimo de 8 números y que el mayor valor de $k$ es $49-8=41$.

Vamos ahora a contar cuántos subconjuntos de $41$ elementos tienen esta propiedad. La idea es que, al omitir 8 números, podemos transformar el problema en elegir 9 números $a_1,a_2,\ldots,a_9$ entre $1$ y $5$ que dirán la cantidad de números consecutivos que habrá entre cada uno de los 8 que se omiten. Como tiene que ser $a_1+a_2+\ldots+a_9=41$, podemos pensar en hacer $a_1=a_2=\ldots=a_9=5$ (el máximo) y luego restarle $1$ a cuatro de los nueve números (posiblemente con repetición). Esto no son más que combinaciones con repetición, que equivalen a su vez a elegir como separadores 9 elementos de un conjunto de $4+9=13$ elementos. Por tanto, tenemos un total de $\binom{13}{9}=\binom{13}{4}=715$ subconjuntos de $41$ elementos con la propiedad del enunciado.