Problema
Seja o conjunto [tex]S=\{1, 2, 3, … , 2015\}[/tex] e considere todos os seus subconjuntos de [tex]1000[/tex] elementos.
De cada subconjunto de [tex]1000[/tex] elementos, escolha o menor elemento.
Escreva a média aritmética destes “menores números” na forma [tex]\dfrac{p}{q}[/tex], com [tex]p[/tex] e [tex]q[/tex] números primos entre si e positivos, e determine [tex]p+q[/tex].
Ferramentas que ajudam
Para resolver este problema será necessário saber quantos subconjuntos com [tex]k[/tex] elementos podemos formar, a partir de um conjunto com [tex]n[/tex] elementos, com [tex]0 \lt k \le n.[/tex]
Lembre-se de que em um conjunto a ordem na qual os elementos aparecem não importa!
[tex]\{1, \, 2, \, 3, \, 4\}=\{2, \, 4, \, 3, \, 1\}=\{4,3, \, 2, \, 1\}[/tex]
Chamamos número binomial ou coeficiente binomial [tex] \, \left(\begin{array}{c}n\\k \end{array}\right)[/tex] o número de subconjuntos de [tex]k[/tex] elementos que podemos extrair de um conjunto com [tex]n[/tex] elementos.
Dessa forma, [tex] \, \left(\begin{array}{c}n\\k \end{array}\right)[/tex] é simplesmente o número de combinações de [tex]n[/tex] elementos tomados [tex]k[/tex] a [tex]k[/tex] e, assim, a Análise Combinatória nos ensina que
[tex]\qquad \qquad \left(\begin{array}{c}n\\k \end{array}\right)=C_k^n=\dfrac{n!}{k!(n-k)!}.[/tex] [tex] \qquad (i)[/tex]
Ainda com relação aos números binomiais, necessitaremos de um importante resultado da Análise Combinatória, o qual será utilizado sem justificativas.
Se [tex]a[/tex] e [tex]b[/tex] são números naturais, então:
[tex]\;\begin{align*} \binom{a}{a} + \binom{a+1}{a} + \binom{a+2}{a} + \dots + \binom{a+b}{a} = \binom{a+b+1}{a+1}\end{align*}.\qquad[/tex][tex] \;(ii)[/tex]
Solução
Seja [tex]M[/tex] a média desejada. Antes de calcular [tex]M[/tex] faremos algumas observações.
(1) Para um conjunto com [tex]2015[/tex] elementos, nós temos [tex]\begin{align*}\binom{2015}{1000}\end{align*}[/tex]subconjuntos de [tex]1000[/tex] elementos.
(2) Observe que um subconjunto de [tex]S[/tex] cujo menor elemento seja [tex]1873[/tex], por exemplo, não tem [tex]1000[/tex] elementos, já que, sendo [tex]2015-1872=143[/tex], tal subconjunto tem, no máximo, 143 elementos. Assim, cabe a seguinte pergunta: Para que um subconjunto de [tex]S[/tex] tenha [tex]1000[/tex] elementos, que condições o menor de seus elementos deve satisfazer?
Vejamos. Observe que
– existem [tex]1001[/tex] inteiros de [tex]1015[/tex] a [tex]2015[/tex], inclusive;
– existem exatamente [tex]1000[/tex] inteiros de [tex]1016[/tex] a [tex]2015[/tex], inclusive;
– há apenas [tex]999[/tex] inteiros de [tex]1017[/tex] a [tex]2015[/tex], inclusive;
– há apenas [tex]998[/tex] inteiros de [tex]1018[/tex] a [tex]2015[/tex], inclusive;
logo, nas condições do enunciado, para que um subconjunto de [tex]S[/tex] tenha [tex]1000[/tex] elementos, é necessário que o menor de seus elementos seja no máximo [tex]1016[/tex].
(3) Seja [tex]t[/tex] um elemento de [tex]S[/tex] tal que [tex]1\leq t\leq 1016[/tex].
Quantos são os subconjuntos de [tex]S[/tex] com [tex]1000[/tex] elementos que possuem [tex]t[/tex] como seu menor elemento?
Bem, se [tex]t[/tex] é o menor elemento de um subconjunto de [tex]S[/tex] com [tex]1000[/tex] elementos, podemos escolher os outros [tex]999[/tex] elementos desse subconjunto entre os [tex]2015-t[/tex] elementos de [tex]\{1,2,\dots,2015\}[/tex] que são maiores do que [tex]t[/tex]. Dessa forma, vamos escolher [tex]999[/tex] números dentre os elementos do conjunto [tex]\{t+1,t+2,\dots,2015\}[/tex] e, assim, temos [tex]\begin{align*}\binom{2015 – t}{999}\end{align*} [/tex] subconjuntos de [tex]S[/tex] com [tex]1000[/tex] elementos e que possuem [tex]t[/tex] como seu menor elemento.
Pronto, agora estamos preparados para calcular a média [tex]M[/tex].
Em função da observação (2):
[tex]\qquad \qquad M=\dfrac{1 \times Q_1+2\times Q_2+3\times Q_3+ \cdots +1016\times Q_{1016}}{Q}[/tex]
onde para cada [tex]t[/tex], com [tex]t \in \{1,2,\cdots,1016\}[/tex], [tex]Q_t[/tex] é a quantidade de subconjuntos de [tex]S[/tex] com [tex]1000[/tex] elementos que possuem [tex]t[/tex] como seu menor elemento e [tex]Q[/tex] é o total de subconjuntos de [tex]S[/tex] com [tex]1000[/tex] elementos.
Mas, pela observação (1),
- [tex]Q=\begin{align*}\binom{2015}{1000}\end{align*}[/tex]
e pela observação (3):
- [tex]Q_1= \left(\begin{array}{c}2015-1\\999 \end{array}\right)=\left(\begin{array}{c}2014\\999 \end{array}\right)[/tex];
- [tex]Q_2= \left(\begin{array}{c}2015-2\\999 \end{array}\right)=\left(\begin{array}{c}2013\\999 \end{array}\right)[/tex];
- [tex]Q_3= \left(\begin{array}{c}2015-3\\999 \end{array}\right)=\left(\begin{array}{c}2012\\999 \end{array}\right)[/tex];
- . . .
- [tex]Q_{1016}= \left(\begin{array}{c}2015-1016\\999 \end{array}\right)=\left(\begin{array}{c}999\\999 \end{array}\right)[/tex].
Portanto
[tex]\qquad \qquad M = \dfrac{ 1 \times\binom{2014}{999} + 2 \times\binom{2013}{999} + 3 \times\binom{2012}{999} + \cdots+ 1016 \times\binom{999}{999} }{ \binom{2015}{1000} }[/tex],
donde
[tex]\quad \begin{align*} \binom{2015}{1000} M &= 1 \times\binom{2014}{999} + 2 \times\binom{2013}{999}+ 3 \times\binom{2012}{999} + \dots + 1016 \times\binom{999}{999} \\
&=\left[\binom{2014}{999} + \binom{2013}{999}+ \binom{2012}{999} + \dots + \binom{999}{999}\right]+ \\
& \qquad \quad \left[\binom{2013}{999} + \binom{2012}{999} + \dots + \binom{999}{999}\right]+ \\
& \qquad \quad \left[\binom{2012}{999} + \dots + \binom{999}{999}\right]+ \dots\\
& \qquad \quad \dots +\\
& \qquad \quad \left[\binom{999}{999}\right] \\
&=\left[ \binom{2015}{1000} + \binom{2014}{1000}+ \binom{2013}{1000} + \dots + \binom{1000}{1000}\right] \\ &= \binom{2016}{1001}. \end{align*}[/tex]
Observe que usamos a identidade [tex](ii)[/tex]:
[tex]\qquad \qquad \begin{align*} \binom{a}{a} + \binom{a+1}{a} + \binom{a+2}{a} + \dots + \binom{a+b}{a} = \binom{a+b+1}{a+1}\end{align*}.[/tex]
em cada expressão delimitada por colchetes. Até mesmo em [tex]\left(\begin{array}{c}999\\999 \end{array}\right).[/tex]
Finalmente, usando a definição de número binomial e a definição de fatorial, temos que:
[tex]\qquad M =\dfrac{\left(\begin{array}{c}2016\\1001\end{array}\right)}{ \left(\begin{array}{c}2015\\1000\end{array}\right)}=\dfrac{\,\,\,\dfrac{2016!}{1001! \, 1015!}\,\,\,}{\dfrac{2015!}{1000! \, 1015!}}=\dfrac{2016!}{1001!\cancel{1015!}}\times\dfrac{1000!\cancel{1015!}}{2015!}\\
\qquad M=\dfrac{2016!}{2015!}\times\dfrac{1000!}{1001!}= \dfrac{2016}{1001} = \dfrac{288}{143}[/tex].
Como [tex]143=11\times 13[/tex] e [tex]288=2^5\times 3^2[/tex], então
[tex]\qquad \qquad M =\dfrac{288}{143}[/tex], com [tex]143[/tex] e [tex]288[/tex] primos entre si,
e, portanto, [tex]\boxed{p+q=288+143=431}[/tex].
Solução elaborada pelos Moderadores do Blog.