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

Solución. Como cada número pertenece a $3$ subconjuntos y hay $8$ números, el número total de elementos entre todos los subconjuntos es $24$. Así, como cada subconjunto tiene $4$ elementos, habrá un total de $6$ subconjuntos.

Un ejemplo de familia en esta situación es tomar $\{1,2,3,4\}$, $\{5,6,7,8\}$, $\{1,2,5,6\}$, $\{3,4,7,8\}$, $\{1,3,5,7\}$ y $\{2,4,6,8\}$ como elementos de la misma.

Informar

Solución. Hay un total de $7!=5050$ posibilidades. Obviamente en primer lugar aparecerán los números que comienzan por $1$, que son un total de $6!=720$, que es el número de posibles permutaciones de los números $\{2,3,4,5,6,7\}$. A continuación encontraremos otros $720$ números que comienzan por $2$. Los $720$ números que comienzan por $3$ ocuparán las posiciones $1441$ a $2160$, luego sabemos que el número que buscamos comienza por $3$.

Vamos a determinar ahora la segunda cifra significativa, para lo que nos centraremos en los $720$ números formados de menor a mayor por las cifras $\{1,3,4,5,6,7\}$. Las $5!=120$ primeras comienzan por $1$ y corresponden a las que empiezan por $31$, que en la ordenación original ocupan las posiciones $1441$ a $1560$. Las que comienzan por $32$ ocuparán de la $1561$ a la $1680$, y así sucesivamente hasta los que comienzan por $36$, que ocupan las posiciones $1921$ a $2040$, luego el número que buscamos comienza por $36$.

Repetimos el proceso con la tercera cifra significativa, agrupando los resultados en subconjuntos de $4!=24$ números. Los que comienzan por $361$ ocupan las posiciones $1921$ a $1944$, los que comienzan por $362$ las posiciones $1945$ a $1968$, los que comienzan por $364$ las posiciones $1969$ a $1992$ y los que comienzan por $365$ las posiciones $1993$ a $2016$. El último número de este grupo (posición $2016$) es $3657421$ y el penúltimo (posición $2015$, que es el buscamos) será por tanto $3657412$.

Nota. Un razonamiento más generalizable se podría haber hecho dividiendo $2015-1$ entre $720$, el cociente está relacionado con el número que hay que tomar, y el resto (menos una unidad) se divide ahora entre $120$, después se repite con $24$,... El razonamiento sería algo similar a la forma que se hace un cambio de base de numeración, pero como si en cada paso la base fuese distinta.

Informar

Solución. Vamos a resolver el problema de forma más general, suponiendo que hay $2n$ equipos que juegan $n$ partidos, pues el razonamiento es el mismo. Entonces, si ponemos los $2n$ equipos en cierto orden, podemos emparejar al primero con el segundo, el tercero con el cuarto, etc. Hay $(2n)!$ formas distintas de ordenar los $2n$ equipos pero obviamente distintas ordenaciones dan lugar a los mismos emparejamientos. Concretamente, podemos permutar cada pareja emparejada y el emparejamiento no cambia: como hay $n$ parejas, esto da un total de $2^n$ posibilidades. Pero también podemos permutar parejas entre sí, y los emparejamientos tampoco cambian, lo que nos da un total de $n!$ reordenaciones. Deducimos que de las $(2n)!$ formas distintas de ordenar, cada emparejamiento está contado $2^n\cdot n!$ veces, lo que nos da un total de \[\frac{(2n)!}{2^n\cdot n!}\] emparejamientos distintos. En el enunciado tenemos $n=10$, luego el número buscado es: \[\frac{20!}{2^{10}\cdot 10!}=1\cdot 3\cdot 5\cdots 19=654729075.\] Informar

Solución. El número de casos posibles es $2^{12}$ pues cada una de las doce monedas tiene dos opciones. El número de casos favorables es el mismo que el número de formas de elegir tres monedas entre las doce, es decir, las combinaciones de 12 elementos tomados de 3 en 3. Por tanto, como cada caso es equiprobable, la probabilidad buscada es el cociente entre casos favorables y casos posibles, esto es, \[\frac{\binom{12}{3}}{2^{12}}=\frac{12\cdot 11\cdot 10}{3\cdot 2\cdot 2^{12}}=\frac{55}{1024}{.}\] Informar

Solución. Este es un problema clásico de combinaciones con repetición. De todas formas, veamos cómo podemos razonar para encontrar la solución. Vamos a ver que encontrar una forma de repartir $100$ euros entre $6$ personas es equivalente a encontrar una forma de elegir $5$ elementos de un conjunto de $105$ y, por tanto, el número buscado en el apartado (a) son las combinaciones de $105$ elementos tomados de $5$ en $5$, es decir, \[\left(\begin{array}{c}105\\5\end{array}\right)=\frac{105\cdot 104\cdot 103\cdot 102\cdot 101}{5\cdot 4\cdot 3\cdot 2\cdot 1}=96560646.\] Para verlo, pongamos $105$ elementos en fila y elijamos $5$, que separan a los $100$ restantes en $6$ conjuntos. Empezando en orden por un extremo, a cada uno de los $6$ amigos, que hemos ordenado previamente, le damos tantos caramelos como elementos tenga el conjunto que le toque. Así obtenemos todas las formas de repartir los euros, luego éste es el número buscado (observa que dos de estos $5$ elementos que hemos destacado pueden ser consecutivos, lo que quiere decir que el conjunto que queda entre los dos tiene cero elementos).

El segundo apartado es muy parecido al primero. Se pueden tomar dos caminos. La primera opción es calcular el número de formas de repartir en las que alguno haya recibido cero euros y restárselo al número calculado anteriormente (pero este cálculo es muy largo). La segunda opción es repartir previamente un euro a cada amigo y luego calcular el número de formas de repartir los $94$ restantes. En vista del apartado (a), este número no es más que \[\left(\begin{array}{c}99\\5\end{array}\right)=\frac{99\cdot 98\cdot 97\cdot 96\cdot 95}{5\cdot 4\cdot 3\cdot 2\cdot 1}=71523144.\]

Informar

Solución. Para el primer apartado, vamos a ver que el número de subconjuntos de $A$ es el mismo que el de aplicaciones de $f:A\rightarrow\{0,1\}$, que es $2^n$ (ya que hay que elegir independientemente la imagen de cada uno de los $n$ elementos de $A$ entre dos posibilidades). La forma de ver esto es que a cada subconjunto $B$ de $A$ le asignamos la aplicación que manda todos los elementos de $B$ en uno y los demás en cero. Es fácil ver ahora que cada subconjunto determina la aplicación y cada aplicación determina al subconjunto (la preimagen del uno).

Para el segundo apartado, vamos a intentar generalizar la idea anterior. A cada pareja $\{B,C\}$ de subconjuntos de $A$ le vamos a asignar la aplicación $f:A\rightarrow\{0,1,2\}$ que manda los elementos de $B$ al $1$, los elementos de $C$ al $2$ y los elementos restantes al $0$. Esto da una correspondencia biyectiva entre las parejas (ordenadas) de subconjuntos disjuntos y las aplicaciones $f:A\rightarrow\{0,1,2\}$. El número de tales aplicaciones es $3^n$ (¿por qué?), pero como estamos interesados en parejas sin importar el orden tendremos que eliminar algunos. Concretamente, cada pareja la estamos contando dos veces (se corresponde con cambiar $1$ por $2$ en la imagen de la aplicación $f$ que hemos asociado) salvo la pareja $(\emptyset,\emptyset)$ que sólo se cuenta una vez (se corresponde con la aplicación constante cero). Por tanto, la respuesta al segundo apartado es $\frac{3^n+1}{2}$. Informar

Solución. Haremos inducción sobre el número $n$ de rectas para probar que el número de puntos de intersección es $\frac{1}{2}(n^2-n)$ y el número de regiones es $\frac{1}{2}(n^2+n+2)$.

1. Para $n=1$, está claro que no hay puntos de intersección por lo que la fórmula $\frac{1}{2}(n^2-n)$ es válida para $n=1$. Supuesto que es cierta para $n-1$ rectas, probémosla para $n$. No obstante, los puntos de intersección de $n$ rectas son los puntos para $n-1$ rectas más los $n-1$ puntos que introduce la recta adicional cortando a todas las anteriores. En consecuencia, usando la hipótesis de inducción, para $n$ rectas tendremos \[\frac{(n-1)^2-(n-1)}{2}+(n-1)=\frac{n^2-n}{2},\] lo que prueba la fórmula propuesta.
2. Para $n=1$, está claro que hay dos regiones por lo que la fórmula $\frac{1}{2}(n^2+n+2)$ es válida para $n=1$. Supuesto que es cierta para $n-1$ rectas, para $n$ rectas las regiones son las que determinan $n-1$ de las rectas rectas más las $n$ que introduce la recta adicional cortando a todas las anteriores. La hipótesis de inducción nos dice entonces que el número de regiones para $n$ rectas es \[\frac{(n-1)^2+(n-1)+2}{2}+n=\frac{n^2+n+2}{2},\] que es la fórmula propuesta para $n$ y hemos terminado la inducción.

Finalmente, respondamos a la última pregunta de forma afirmativa también por inducción sobre $n$. Cuando tenemos una sola recta, es claro que se puede colorear (usando un color para cada una de las dos regiones en que el plano queda dividido). Supongamos ahora que para cualquier colección de $n-1$ rectas la coloración es posible. Al introducir una nueva recta que no corta a las anteriores basta invertir los colores a un lado de la nueva recta y dejarlos como estaban al otro lado, dando así una coloración para las $n$ rectas. Informar

Solución. Para calcular el número de puntos de intersección, basta darse cuenta de que cada par de rectas determina un único punto de intersección (no hay pares de paralelas). Además, dos pares de rectas distintos determinan intersecciones distintos (no hay tres rectas concurrentes). Por tanto, hay tantos puntos como parejas de elementos en un conjunto de $n$ elementos, es decir, la solución al primer apartado es \[\binom{n}{2}=\frac{n(n-1)}{2}.\] Para calcular el número de regiones, consideremos otra recta auxiliar $r$ que no sea paralela a ninguna de las anteriores y de forma que todos los puntos de intersección queden al mismo lado de $r$. Como $r$ corta a las $n$ rectas originales, deducimos que $r$ atraviesa $n+1$ de las regiones (infinitas, no acotadas) que queremos cortar. Ahora comenzamos a trasladar $r$ paralelamente hasta que toque alguna de las intersecciones: en ese momento encontrará una nueva región. Si seguimos trasladando $r$ en la misma dirección encontraremos a las $\binom{n}{2}$ intersecciones una por una y cada vez que encontremos una de ellas cortaremos a una región nueva. Por tanto, el número de regiones está dado por las $n+1$ originales más las $\binom{n}{2}$ que encontramos. En resumen, la solución al segundo apartado está dada por \[n+1+\binom{n}{2}=\frac{n^2+n+2}{2}.\] Finalmente, respondamos a la última pregunta de forma afirmativa por inducción sobre $n$. Cuando tenemos una sola recta, es claro que se puede dibujar, usando un color para cada una de las dos regiones en que el plano queda dividido. Supongamos ahora que para cualquier colección de $n$ rectas la coloración es posible. Al introducir una nueva recta que no corta a las anteriores basta invertir los colores a un lado de la nueva recta y dejarlos como estaban al otro lado. Informar

Solución. Cada pareja de vértices determina una recta, lo que hace un total de $\binom{n}{2}=\frac{n(n-1)}{2}$ rectas. Aquí también estamos contando las $n$ rectas que contienen a los lados (que no son diagonales) por lo que el número de rectas diagonales es $\frac{n(n-1)}{2}-n=\frac{n(n-3)}{2}$. Ahora bien, cada par de estas rectas determina un punto de intersección (no hay dos paralelas), lo que hace un total de $\binom{n(n-3)/2}{2}$ puntos de intersección. Sin embargo, en cada vértice se unen $n-3$ diagonales, lo que nos dice que en el cómputo anterior estábamos contando cada vértice $\binom{n-3}{2}$ veces, por lo que la solución al primer apartado es \[\binom{\frac{n(n-3)}{2}}{2}-n\binom{n-3}{2}=\frac{n(n-3)(n^2-7n+14)}{8}.\] Para resolver el segundo apartado, observemos que cada punto interior del polígono está determinado por la intersección de dos rectas diagonales, cada una de las cuales viene determinada por dos vértices, por lo que a cada uno de tales puntos se le pueden asignar cuatro de los vértices. Lo importante ahora es darse cuenta de que dados cuatro vértices, estos determinan un único punto interior al polígono. En efecto, dado que el polígono es convexo, estos cuatro vértices determinan un cuadrilátero convexo (llamémoslo $ABCD$, con los vértices ordenados en sentido contrario a las agujas del reloj) y tres puntos de intersección que no son vértices ($AB\cap CD$, $AC\cap BD$ y $AD\cap BC$), de los cuales sólo uno es interior ($AC\cap BD$) y es la intersección de diagonales, no de lados del polígono. Deducimos que hay un punto de intersección de diagonales interior al polígono por cada subconjunto de cuatro vértices y, en consecuencia, el número buscado de puntos interiores es \[\binom{n}{4}=\frac{n(n-1)(n-2)(n-3)}{24},\] mientras que el de puntos exteriores viene dado por \[\frac{n(n-3)(n^2-7n+14)}{8}-\frac{n(n-1)(n-2)(n-3)}{24}=\frac{n(n-3)(n^2-9n+20)}{12}\]

Nota. Las fórmulas anteriores son válidas para un triángulo (los puntos de intersección interiores y exteriores son cero), aunque el razonamiento no es riguroso en este caso ya que estamos considerando números combinatorios que no están definidos como $\binom{0}{2}$ ó $\binom{3}{4}$.

Informar