Question

Para cualquier conjunto finito $X,$ sea $|X|$ el número de elementos de $X.$ Define $S_n = \sum |A \cap B|,$ donde la suma se toma sobre todos los pares ordenados $(A, B)$ tales que $A$ y $B$ son subconjuntos de $\{1, 2, 3, \ldots, n\}$ con $|A| = |B|.$ Por ejemplo, $S_2 = 4$ porque la suma se toma sobre los siguientes pares de subconjuntos: $\begin{aligned} &(A, B) \in {}\\ &\quad \small\left\{\begin{gathered} (\emptyset, \emptyset), (\{1\}, \{1\}), \\ (\{1\}, \{2\}), (\{2\}, \{1\}), \\ (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\}) \end{gathered}\right\}, \end{aligned}$ lo que da $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4.$ Sea $\frac{S_{2022}}{S_{2021}} = \frac{p}{q},$ donde $p$ y $q$ son enteros positivos primos entre sí. Halla el residuo cuando $p + q$ se divide entre $1000.$

For any finite set $X,$ let $|X|$ denote the number of elements in $X.$ Define $S_n = \sum |A \cap B|,$ where the sum is taken over all ordered pairs $(A, B)$ such that $A$ and $B$ are subsets of $\{1, 2, 3, \ldots, n\}$ with $|A| = |B|.$ For example, $S_2 = 4$ because the sum is taken over the pairs of subsets $\begin{aligned} &(A, B) \in {}\\ &\quad \small\left\{\begin{gathered} (\emptyset, \emptyset), (\{1\}, \{1\}), \\ (\{1\}, \{2\}), (\{2\}, \{1\}), \\ (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\}) \end{gathered}\right\}, \end{aligned}$ giving $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4.$ Let $\frac{S_{2022}}{S_{2021}} = \frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find the remainder when $p + q$ is divided by $1000.$

Respuesta

Respuesta: 245

Conceptos:subconjuntos combinaciones doble conteo Convolución de Vandermonde

Nivel de dificultad: 2990

Pista pequeña:

Intercambia el orden de la suma: para cada elemento, cuenta los pares $(A, B)$ con $|A| = |B|$ que lo contienen en ambos conjuntos

Swap the order of summation: for each element, count the pairs $(A, B)$ with $|A| = |B|$ that contain it in both sets

Pista grande:

$\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1},$ así que $S_n = n\binom{2n-2}{n-1};$ luego simplifica el cociente de términos consecutivos

$\sum_k \binom{n-1}{k-1}^2 = \binom{2n-2}{n-1},$ so $S_n = n\binom{2n-2}{n-1};$ then simplify the ratio of consecutive terms

Solución:

Cuenta elemento por elemento: $S_n$ es igual al número de ternas $(x, A, B)$ con $|A| = |B|$ y $x \in A \cap B.$ Para un $x$ fijo y un tamaño $k,$ hay $\binom{n-1}{k-1}$ elecciones para cada uno de $A$ y $B$ que contienen a $x,$ así que por la identidad de Vandermonde $\begin{aligned} S_n &= n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 \\ &= n\binom{2n-2}{n-1}. \end{aligned}$

Por lo tanto, $\begin{aligned} \frac{S_{2022}}{S_{2021}} &= \frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} \\ &= \frac{2022}{2021} \cdot \frac{4042 \cdot 4041}{2021^2} \\ &= \frac{2 \cdot 2022 \cdot 4041}{2021^2}. \end{aligned}$ Como $2021 = 43 \cdot 47$ no divide ni a $2022,$ ni a $4041 = 3^2 \cdot 449,$ ni a $2,$ esta fracción está en su mínima expresión: $p = 2 \cdot 2022 \cdot 4041 = 16341804$ y $q = 2021^2 = 4084441.$

Entonces $p + q = 20426245,$ cuyo residuo módulo $1000$ es $245.$

Count element by element: $S_n$ equals the number of triples $(x, A, B)$ with $|A| = |B|$ and $x \in A \cap B.$ For a fixed $x$ and size $k,$ there are $\binom{n-1}{k-1}$ choices for each of $A$ and $B$ containing $x,$ so by the Vandermonde identity $\begin{aligned} S_n &= n \sum_{k=1}^{n} \binom{n-1}{k-1}^2 \\ &= n\binom{2n-2}{n-1}. \end{aligned}$

Therefore $\begin{aligned} \frac{S_{2022}}{S_{2021}} &= \frac{2022\binom{4042}{2021}}{2021\binom{4040}{2020}} \\ &= \frac{2022}{2021} \cdot \frac{4042 \cdot 4041}{2021^2} \\ &= \frac{2 \cdot 2022 \cdot 4041}{2021^2}. \end{aligned}$ Since $2021 = 43 \cdot 47$ divides neither $2022,$ $4041 = 3^2 \cdot 449,$ nor $2,$ this fraction is in lowest terms: $p = 2 \cdot 2022 \cdot 4041 = 16341804$ and $q = 2021^2 = 4084441.$

Then $p + q = 20426245,$ whose remainder modulo $1000$ is $245.$

2022 AIME I Problema 12

Respuesta: 245

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años