Question

Considera todos los subconjuntos de $1000$ elementos del conjunto $\{1, 2, 3, \ldots, 2015\}.$ De cada uno de tales subconjuntos elige el elemento menor. La media aritmética de todos estos elementos menores es $\frac{p}{q},$ donde $p$ y $q$ son enteros positivos primos entre sí. Halla $p + q.$

Consider all $1000$ -element subsets of the set $\{1, 2, 3, \ldots, 2015\}.$ From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Respuesta

Respuesta: 431

Conceptos:combinaciones valor esperado biyección

Nivel de dificultad: 3270

Pista pequeña:

Exactamente $\binom{2015-j}{999}$ de los subconjuntos tienen a $j$ como elemento menor

Exactly $\binom{2015-j}{999}$ of the subsets have least element $j$

Pista grande:

Interpreta $\sum j\binom{2015-j}{999}$ como el conteo de los subconjuntos de $1001$ elementos de un conjunto de $2016$ elementos según su segundo elemento más pequeño

Interpret $\sum j\binom{2015-j}{999}$ as counting $1001$ -element subsets of a $2016$ -element set by their second-smallest element

Solución:

Un subconjunto de $1000$ elementos tiene a $j$ como elemento menor exactamente cuando contiene $j$ junto con $999$ elementos mayores, así que $\binom{2015-j}{999}$ de los subconjuntos tienen a $j$ como elemento menor. Por lo tanto la media es $\frac{\sum_{j} j\binom{2015-j}{999}}{\binom{2015}{1000}}.$

El numerador cuenta algo concreto: para construir un subconjunto de $1001$ elementos de $\{0, 1, \ldots, 2015\}$ cuyo segundo elemento más pequeño sea $j,$ elige su elemento más pequeño de $\{0, \ldots, j-1\}$ ( $j$ maneras) y sus $999$ elementos mayores de $\{j+1, \ldots, 2015\}.$ Al sumar sobre $j$ se cuenta cada subconjunto de $1001$ elementos exactamente una vez, así que $\sum_j j\binom{2015-j}{999} = \binom{2016}{1001}.$

Por lo tanto la media es $\frac{\binom{2016}{1001}}{\binom{2015}{1000}} = \frac{2016}{1001} = \frac{288}{143},$ que está en su forma más simple, y $p + q = 288 + 143 = 431.$

A $1000$ -element subset has least element $j$ exactly when it contains $j$ together with $999$ larger elements, so $\binom{2015-j}{999}$ of the subsets have least element $j.$ The mean is therefore $\frac{\sum_{j} j\binom{2015-j}{999}}{\binom{2015}{1000}}.$

The numerator counts something concrete: to build a $1001$ -element subset of $\{0, 1, \ldots, 2015\}$ whose second-smallest element is $j,$ choose its smallest element from $\{0, \ldots, j-1\}$ ( $j$ ways) and its top $999$ elements from $\{j+1, \ldots, 2015\}.$ Summing over $j$ produces every $1001$ -element subset exactly once, so $\sum_j j\binom{2015-j}{999} = \binom{2016}{1001}.$

Hence the mean is $\frac{\binom{2016}{1001}}{\binom{2015}{1000}} = \frac{2016}{1001} = \frac{288}{143},$ which is in lowest terms, and $p + q = 288 + 143 = 431.$

2015 AIME I Problema 12

Respuesta: 431

Nivel de dificultad: 3270

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años