{"id":70789,"date":"2017-01-24T14:26:03","date_gmt":"2017-01-24T16:26:03","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=70789"},"modified":"2023-04-06T01:29:33","modified_gmt":"2023-04-06T04:29:33","slug":"problema-olimpico-nivel-c-menores-elementos-de-subconjuntos-escolhidos","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/problema-olimpico-nivel-c-menores-elementos-de-subconjuntos-escolhidos\/","title":{"rendered":".Problema Ol\u00edmpico – N\u00edvel C: Menores elementos de subconjuntos escolhidos"},"content":{"rendered":"

\n

\n

Problema<\/p>\n

\nSeja o conjunto [tex]S=\\{1, 2, 3, … , 2015\\}[\/tex] e considere todos os seus subconjuntos de [tex]1000[\/tex] elementos.
\nDe cada subconjunto de [tex]1000[\/tex] elementos, escolha o menor elemento.
\nEscreva a m\u00e9dia aritm\u00e9tica destes “menores n\u00fameros” na forma [tex]\\dfrac{p}{q}[\/tex], com [tex]p[\/tex] e [tex]q[\/tex] n\u00fameros primos entre si e positivos, e determine [tex]p+q[\/tex].<\/div>\n

\n

\n

Ferramentas que ajudam<\/p>\n

\nPara resolver este problema ser\u00e1 necess\u00e1rio 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]
\nLembre-se de que em um conjunto a ordem na qual os elementos aparecem n\u00e3o importa!<\/p>\n

\"f023\"<\/p>\n

[tex]\\{1, \\, 2, \\, 3, \\, 4\\}=\\{2, \\, 4, \\, 3, \\, 1\\}=\\{4,3, \\, 2, \\, 1\\}[\/tex]<\/p>\n

\n

\nDefini\u00e7\u00e3o:<\/strong> Sejam [tex]n[\/tex] e [tex]k[\/tex] n\u00fameros naturais tais que [tex]k \\le n.[\/tex]
\nChamamos n\u00famero binomial ou coeficiente binomial [tex] \\, \\left(\\begin{array}{c}n\\\\k \\end{array}\\right)[\/tex] o n\u00famero de subconjuntos de [tex]k[\/tex] elementos que podemos extrair de um conjunto com [tex]n[\/tex] elementos.
\nDessa forma, [tex] \\, \\left(\\begin{array}{c}n\\\\k \\end{array}\\right)[\/tex] \u00e9 simplesmente o n\u00famero de combina\u00e7\u00f5es de [tex]n[\/tex] elementos tomados [tex]k[\/tex] a [tex]k[\/tex] e, assim, a An\u00e1lise Combinat\u00f3ria nos ensina que
\n[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] <\/span>\n<\/div>\n

\n

Ainda com rela\u00e7\u00e3o aos n\u00fameros binomiais, necessitaremos de um importante resultado da An\u00e1lise Combinat\u00f3ria, o qual ser\u00e1 utilizado sem justificativas.<\/p>\n

\n

Se [tex]a[\/tex] e [tex]b[\/tex] s\u00e3o n\u00fameros naturais, ent\u00e3o:<\/p>\n

\n

[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] <\/span>\n<\/div>\n

\n<\/div>\n

\n

\n

Solu\u00e7\u00e3o <\/p>\n

\nSeja [tex]M[\/tex] a m\u00e9dia desejada. Antes de calcular [tex]M[\/tex] faremos algumas observa\u00e7\u00f5es.<\/p>\n

(1)<\/strong><\/span> Para um conjunto com [tex]2015[\/tex] elementos, n\u00f3s temos [tex]\\begin{align*}\\binom{2015}{1000}\\end{align*}[\/tex]subconjuntos de [tex]1000[\/tex] elementos.
\n(2)<\/strong><\/span> Observe que um subconjunto de [tex]S[\/tex] cujo menor elemento seja [tex]1873[\/tex], por exemplo, n\u00e3o tem [tex]1000[\/tex] elementos, j\u00e1 que, sendo [tex]2015-1872=143[\/tex], tal subconjunto tem, no m\u00e1ximo, 143 elementos. Assim, cabe a seguinte pergunta: Para que um subconjunto de [tex]S[\/tex] tenha [tex]1000[\/tex] elementos, que condi\u00e7\u00f5es o menor de seus elementos deve satisfazer?
\nVejamos. Observe que
\n<\/span>– existem [tex]1001[\/tex] inteiros de [tex]1015[\/tex] a [tex]2015[\/tex], inclusive;
\n<\/span>– existem exatamente [tex]1000[\/tex] inteiros de [tex]1016[\/tex] a [tex]2015[\/tex], inclusive;
\n<\/span>– h\u00e1 apenas [tex]999[\/tex] inteiros de [tex]1017[\/tex] a [tex]2015[\/tex], inclusive;
\n<\/span>– h\u00e1 apenas [tex]998[\/tex] inteiros de [tex]1018[\/tex] a [tex]2015[\/tex], inclusive;
\nlogo, nas condi\u00e7\u00f5es do enunciado, para que um subconjunto de [tex]S[\/tex] tenha [tex]1000[\/tex] elementos, \u00e9 necess\u00e1rio que o menor de seus elementos seja no m\u00e1ximo [tex]1016[\/tex]<\/strong>.
\n(3)<\/strong><\/span> Seja [tex]t[\/tex] um elemento de [tex]S[\/tex] tal que [tex]1\\leq t\\leq 1016[\/tex].
\nQuantos s\u00e3o os subconjuntos de [tex]S[\/tex] com [tex]1000[\/tex] elementos que possuem [tex]t[\/tex] como seu menor elemento?
\nBem, se [tex]t[\/tex] \u00e9 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\u00e3o maiores do que [tex]t[\/tex]. Dessa forma, vamos escolher [tex]999[\/tex] n\u00fameros 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.<\/strong> <\/p>\n

Pronto, agora estamos preparados para calcular a m\u00e9dia [tex]M[\/tex].
\nEm fun\u00e7\u00e3o da observa\u00e7\u00e3o (2)<\/strong><\/span>: <\/p>\n

\n

[tex]\\qquad \\qquad M=\\dfrac{1 \\times Q_1+2\\times Q_2+3\\times Q_3+ \\cdots +1016\\times Q_{1016}}{Q}[\/tex]<\/p>\n

\n

onde para cada [tex]t[\/tex], com [tex]t \\in \\{1,2,\\cdots,1016\\}[\/tex], [tex]Q_t[\/tex] \u00e9 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] \u00e9 o total de subconjuntos de [tex]S[\/tex] com [tex]1000[\/tex] elementos.
\nMas, pela observa\u00e7\u00e3o (1)<\/strong><\/span>, <\/p>\n