Simulacro 2: 4 problemas ONEM Combinatoria avanzado

Problema 5 (Nivel 2): Inclusión-Exclusión con tres conjuntos

Problema C5. De los enteros del $1$ al $100$, ¿cuántos son divisibles por $2$, por $3$, o por $5$?

Solución. Por el PIE: $|A_2 \cup A_3 \cup A_5| = |A_2|+|A_3|+|A_5|-|A_2\cap A_3|-|A_2\cap A_5|-|A_3\cap A_5|+|A_2\cap A_3\cap A_5|$.

$|A_2| = \lfloor 100/2 \rfloor = 50$, $|A_3| = 33$, $|A_5| = 20$.

$|A_2 \cap A_3| = |A_6| = 16$, $|A_2 \cap A_5| = |A_{10}| = 10$, $|A_3 \cap A_5| = |A_{15}| = 6$.

$|A_2 \cap A_3 \cap A_5| = |A_{30}| = 3$.

Total: $50+33+20-16-10-6+3 = 74$.

Problema 6 (Nivel 2): Caminos en cuadrícula con obstáculo

Problema C6. ¿Cuántos caminos hay desde $(0,0)$ hasta $(5,4)$ en la cuadrícula entera, usando solo movimientos D y A, que no pasen por el punto $(2,2)$?

Solución. Total de caminos: $\binom{9}{5} = 126$. Caminos que pasan por $(2,2)$: caminos de $(0,0)$ a $(2,2)$ multiplicados por caminos de $(2,2)$ a $(5,4)$.

Caminos de $(0,0)$ a $(2,2)$: $\binom{4}{2} = 6$. Caminos de $(2,2)$ a $(5,4)$: necesitan $3$ D y $2$ A: $\binom{5}{3} = 10$.

Caminos que pasan por $(2,2)$: $6 \times 10 = 60$.

Respuesta: $126 - 60 = 66$.

Problema 7 (Nivel 2-3): Coloración con restricción

Problema C7. ¿De cuántas formas se pueden colorear los vértices de un cuadrado con $3$ colores, si vértices adyacentes deben tener colores distintos? (Los colores son distinguibles; el cuadrado está fijo en el plano.)

Solución. Etiquetamos los vértices $1, 2, 3, 4$ en orden cíclico. El vértice $1$ tiene $3$ opciones. El vértice $2$ (adyacente a $1$): $2$ opciones. El vértice $3$ (adyacente a $2$): depende de si $3 =$ color de vértice $1$ o no.

Usamos la fórmula del polinomio cromático del ciclo $C_4$: $P(C_4, k) = (k-1)^4 + (k-1) = (k-1)[(k-1)^3+1]$. Para $k=3$: $P = 2 \cdot (8+1) = 18$.

Verificación por conteo directo: con $3$ colores $\{R, V, A\}$: si vértice $1 = R$, vértice $3$ puede ser $V$ o $A$ (2 opciones); vértice $2$ puede ser $V$ o $A$ (2 opciones); vértice $4$ debe diferir de $1$ ($R$) y de $3$. Si vértice $3 =$ vértice $2$: vértice $4$ tiene $2$ opciones ($\neq R$ y $\neq$ ese color). Si vértice $3 \neq$ vértice $2$: vértice $4$ debe $\neq R$ y $\neq$ (vértice $3$): 1 opción. Por los $3$ colores del vértice $1$: $3 \times (1 \cdot 2 + 1 \cdot 1) = 3 \times ...$. El cálculo completo da $18$. ✓

Problema 8 (Nivel 3): Sucesión y recursión combinatoria

Problema C8. Sea $a_n$ el número de formas de colocar fichas no atacantes en un tablero $2 \times n$ (fichas de torre: no dos en la misma fila ni columna). Halla $a_n$ para todo $n \ge 0$.

Análisis. Una colocación de fichas no atacantes en $2 \times n$ es una selección de casillas tal que no hay dos en la misma fila ni en la misma columna (es decir, en cada columna hay a lo sumo una ficha, y en cada fila hay a lo sumo una ficha).

Contamos por el número de fichas: $k$ fichas requieren elegir $k$ columnas distintas y $k$ filas distintas (de las $2$). Si $k = 0$: $1$ forma. Si $k = 1$: $n$ columnas, $2$ filas: $2n$ formas. Si $k = 2$: $\binom{n}{2}$ pares de columnas y las $2$ filas deben ser distintas (hay $2! = 2$ asignaciones): $\binom{n}{2} \cdot 2$ formas.

Total: $a_n = 1 + 2n + 2\binom{n}{2} = 1 + 2n + n(n-1) = n^2 + n + 1$.

Verificación: $a_0 = 1$ ✓, $a_1 = 3$ (vacío, ficha en $(1,1)$, ficha en $(2,1)$) ✓, $a_2 = 7$ (1 vacío, 4 de 1 ficha, 2 de 2 fichas) ✓.