Problema S\u00f4nia, a professora de um Clube de Matem\u00e1tica, resolve aplicar uma prova surpresa para sua turma de [tex]10[\/tex] alunos e diz que a avalia\u00e7\u00e3o pode ser feita individualmente ou em duplas. \n<\/div>\n Lembrete:<\/strong> <\/p>\n Uma das maneiras de agruparmos elementos de um dado conjunto \u00e9 escolh\u00ea-los levando-se em considera\u00e7\u00e3o apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos \u00e9 denominado uma Combina\u00e7\u00e3o simples<\/em><\/strong>. Especificamente, quando escolhemos [tex]r[\/tex] dentre [tex]n[\/tex] elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combina\u00e7\u00e3o simples de [tex]n[\/tex] elementos tomados [tex]r[\/tex] a [tex]r[\/tex]. [tex]C_{n\\, ,\\, r}=C_n^r=\\dfrac{n!}{(n-r)!\\, r!} \\text{, com } n,r\\in\\mathbb{N} \\text{ e }\\, r\\leqslant n[\/tex].<\/p>\n O quociente [tex]\\dfrac{n!}{(n-r)!\\, r!}[\/tex] tamb\u00e9m pode ser denotado por [tex]\\dbinom{n}{r}[\/tex] e nesse caso \u00e9 denominado coeficiente binomial<\/em><\/strong> ou n\u00famero binomial<\/em><\/strong>.<\/p>\n<\/div>\n Solu\u00e7\u00e3o 1<\/p>\n Vamos solucionar o problema a partir da quantidade de duplas formadas.<\/p>\n 2\u00b0 caso:<\/strong> Apenas uma dupla formada. 3\u00ba caso:<\/strong> Duas duplas formadas. 4\u00ba caso:<\/strong> Tr\u00eas duplas formadas. 5\u00ba caso:<\/strong> Quatro duplas formadas. 6\u00ba caso:<\/strong> Cinco duplas formadas. Finalmente, utilizando o Princ\u00edpio Aditivo, temos Solu\u00e7\u00e3o elaborada pelos Moderadores do Blog<\/strong>.<\/p>\n<\/div>\n \n Solu\u00e7\u00e3o 2<\/p>\n Vamos fazer esta segunda solu\u00e7\u00e3o utilizando Racioc\u00ednio Recursivo! – Pela restri\u00e7\u00e3o imposta no enunciado, se [tex]X[\/tex] far\u00e1 a prova sozinho, teremos que resolver como os outros alunos ficar\u00e3o distribu\u00eddos. Assim, passamos para um \u201cnovo\u201d problema com as mesmas restri\u00e7\u00f5es do problema inicial, por\u00e9m teremos [tex]9[\/tex] alunos. Chamaremos de [tex]a_{9}[\/tex] a solu\u00e7\u00e3o do problema para [tex]9[\/tex] alunos. [tex]\\qquad \\qquad a_{3}=a_{2}+2 \\cdot a_{1}[\/tex] Assim, podemos escrever a f\u00f3rmula de recorr\u00eancia completa e a sequ\u00eancia que nos permite responder a pergunta do problema:<\/p>\n [tex]\\begin{cases} a_{1}=1; \\\\a_{2}=2;\\\\ a_{n}=a_{n-1}+(n-1) \\cdot a_{n-2}; \\text{ para }n \\ge 3. \\end{cases}[\/tex]<\/p>\n Dessa f\u00f3rmula, obtemos: ou seja, existem [tex] \\, \\fcolorbox{black}{#eee0e5}{$9496$}[\/tex] maneiras de organizar a turma para fazer a prova da professora S\u00f4nia.<\/p>\n \n
\n (Indicado a partir do 2\u00ba ano do E. M.)<\/span><\/p>\n
\n
\nDe quantas formas a turma pode ser organizada para fazer a prova? <\/strong><\/p>\n![\"explicador_p\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2013\/01\/menino.jpg\")
<\/p>\n
\nE o legal \u00e9 que, dado um conjunto finito, podemos determinar quantos agrupamentos desse tipo podemos fazer, sem que precisemos exibi-los.<\/p>\n\n
\n\n1\u00ba caso:<\/strong> Nenhuma dupla formada.<\/p>\n
\n
\n– O n\u00famero de maneiras de escolher uma dupla em um grupo de [tex]10[\/tex] pessoas \u00e9 [tex]C_{10}^{2}=45[\/tex].
\n– Os outros alunos far\u00e3o a prova sozinhos, portanto h\u00e1 apenas um modo de organizar os que sobram. <\/p>\n\n
\n– O n\u00famero de maneiras de escolher a primeira dupla em um grupo de [tex]10[\/tex] pessoas \u00e9 [tex]C_{10}^{2}=45[\/tex]; para a segunda teremos [tex]C_{8}^{2}=28[\/tex] maneiras. Pelo Princ\u00edpio Multiplicativo, teremos [tex]45 \\cdot 28[\/tex] possibilidades. Perceba que essa contagem deve ser dividida por [tex]2![\/tex], pois a permuta\u00e7\u00e3o das duplas n\u00e3o resulta em uma configura\u00e7\u00e3o diferente (Escolher a dupla A<\/strong> e a dupla B<\/strong> \u00e9 a mesma situa\u00e7\u00e3o de escolher a dupla B<\/strong> e depois a A<\/strong>.).
\n– Os outros alunos far\u00e3o a prova sozinhos, portanto h\u00e1 apenas um modo de organizar os que sobram. <\/p>\n\n
\n– O n\u00famero de maneiras de escolher a primeira dupla em um grupo de [tex]10[\/tex] pessoas \u00e9 [tex]C_{10}^{2}=45[\/tex]; para a segunda teremos [tex]C_{8}^{2}=28[\/tex] e para terceira dupla [tex]C_{6}^{2}=15[\/tex]. Pelo Princ\u00edpio Multiplicativo, teremos [tex]45 \\cdot 28 \\cdot 15[\/tex] possibilidades.
\nPerceba que essa contagem deve ser dividida por [tex]3![\/tex], pois a permuta\u00e7\u00e3o das duplas n\u00e3o resulta em uma configura\u00e7\u00e3o diferente (mesmo motivo do caso anterior).
\n– Os outros alunos far\u00e3o a prova sozinhos, portanto h\u00e1 apenas um modo de organizar os que sobram. <\/p>\n\n
\n– O n\u00famero de maneiras de escolher a primeira dupla em um grupo de [tex]10[\/tex] pessoas \u00e9 [tex]C_{10}^{2}=45[\/tex], para a segunda teremos [tex]C_{8}^{2}=28[\/tex], para a terceira [tex]C_{6}^{2}=15[\/tex] e para a quarta dupla [tex]C_{4}^{2}=6[\/tex]. Pelo Princ\u00edpio Multiplicativo, teremos [tex]45 \\cdot 28 \\cdot 15 \\cdot 6[\/tex] possibilidades. Perceba que essa contagem deve ser dividida por [tex]4![\/tex], pelo mesmo motivo dos casos anteriores.
\n– Os outros alunos far\u00e3o a prova sozinhos, portanto h\u00e1 apenas um modo de organizar os que sobram. <\/p>\n\n
\n– O n\u00famero de maneiras de escolher a primeira dupla em um grupo de [tex]10[\/tex] pessoas \u00e9 [tex]C_{10}^{2}=45[\/tex], para a segunda teremos [tex]C_{8}^{2}=28[\/tex], para a terceira [tex]C_{6}^{2}=15[\/tex], para a quarta [tex]C_{4}^{2}=6[\/tex] e a quinta dupla [tex]C_{2}^{2}=1[\/tex]. Pelo Princ\u00edpio Multiplicativo, teremos [tex]45 \\cdot 28 \\cdot 15 \\cdot 6 \\cdot 1[\/tex]. Perceba que essa contagem deve ser dividida por [tex]5![\/tex], pelo mesmo motivo dos casos anteriores. <\/p>\n\n
\n[tex]\\qquad \\qquad 1+45+630+3150+4725+945=9496[\/tex],
\nou seja, existem [tex] \\, \\fcolorbox{black}{#eee0e5}{$9496$}[\/tex] maneiras de organizar a turma para fazer a prova da professora S\u00f4nia.<\/p>\n
\n
\n
\nSeja [tex]a_{10}[\/tex] o n\u00famero de maneiras de organizar os [tex]10[\/tex] alunos para a prova surpresa e suponha que [tex]X[\/tex] seja um aluno dessa turma. Observe que h\u00e1 apenas duas situa\u00e7\u00f5es poss\u00edveis: [tex]X[\/tex] far\u00e1 a prova sozinho ou [tex]X[\/tex] far\u00e1 a prova em dupla.<\/p>\n\n
\n[tex]a_{10}=[\/tex] solu\u00e7\u00f5es com [tex]X[\/tex] fazendo a prova sozinho [tex]+[\/tex] solu\u00e7\u00f5es com [tex]X[\/tex] fazendo a prova em dupla.<\/li>\n
\n– Agora, se [tex]X[\/tex] for realizar a prova em dupla, temos [tex]9[\/tex] maneiras de escolher a sua dupla e, novamente, teremos que resolver como os outros alunos ficar\u00e3o distribu\u00eddos. Assim, tamb\u00e9m chegamos a um \u201cnovo\u201d problema com as mesmas restri\u00e7\u00f5es do problema inicial, por\u00e9m com [tex]8[\/tex] alunos. De forma an\u00e1loga, chamaremos de [tex]a_{8}[\/tex] a solu\u00e7\u00e3o do problema para [tex]8[\/tex] alunos.
\nEsse racioc\u00ednio nos mostrou que:
\n\t[tex]\\qquad \\qquad \\boxed{a_{10}=a_{9}+9 \\cdot a_{8}}[\/tex].
\nOu seja, a solu\u00e7\u00e3o do problema para [tex]10[\/tex] alunos \u00e9 a soma das solu\u00e7\u00f5es para [tex]9[\/tex] alunos mais nove vezes o n\u00famero de solu\u00e7\u00f5es para [tex]8[\/tex] alunos.\n<\/ul>\n\n
\n[tex]\\qquad \\qquad \\boxed{a_{n}=a_{n-1}+(n-1) \\cdot a_{n-2}}[\/tex].<\/li>\n<\/ul>\n\n
\nTeremos apenas uma solu\u00e7\u00e3o. Portanto,
\n[tex]\\qquad \\qquad \\boxed{a_{1}=1}[\/tex].<\/li>\n
\n [tex]\\qquad \\qquad \\boxed{a_{2}=2}[\/tex]. <\/li>\n
\n[tex]\\qquad \\qquad a_{3}=2+2 \\cdot 1[\/tex]
\n[tex]\\qquad \\qquad \\boxed{a_{3}=4}[\/tex].
\nO resultado faz sentido, pois com [tex]3[\/tex] alunos temos [tex]4[\/tex] solu\u00e7\u00f5es ([tex]3[\/tex] modos de escolhermos a dupla mais todos fazendo a prova individualmente). <\/ul>\n
\n[tex]\\qquad \\qquad a_{1}=1[\/tex]
\n[tex]\\qquad \\qquad a_{2}=2[\/tex]
\n[tex]\\qquad \\qquad a_{3}=4[\/tex]
\n[tex]\\qquad \\qquad a_{4}=10[\/tex]
\n[tex]\\qquad \\qquad a_{5}=26[\/tex]
\n[tex]\\qquad \\qquad a_{6}=76[\/tex]
\n[tex]\\qquad \\qquad a_{7}=232[\/tex]
\n[tex]\\qquad \\qquad a_{8}=764[\/tex]
\n[tex]\\qquad \\qquad a_{9}=2620[\/tex]
\n[tex]\\qquad \\qquad a_{10}=9496[\/tex]<\/p>\n