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