Métodos de Contagem e Probabilidade

1 M todos de Contageme ProbabilidadePaulo Cezar Pinto Carvalho3 Sobre o AutorPaulo Cezar Pinto Carvalho formado em Engenharia pelo Insti-tuto Militar de Engenharia, Mestre em Estat stica pelo IMPAe PhDem Pesquisa Operacional pela Universidade Cornell. Atualmente pesquisador do IMPA, na rea de Vis o Computacional e Compu-ta o Gr fica. Divide o tempo devotado pesquisa com atividadesligadas melhoria do ensino em todos os n veis. Desde 1991 profes-sor do Programa de Aperfei oamento de Professores, promovido peloIMPA. autor de diversos livros da Cole o do Professor de Matem -tica, publicada pela SBM. Tamb m tem se dedicado s Olimp adas deMatem tica, participando da organiza o da Olimp ada Brasileira deMatem tica, desempenhando a fun o de l der em v rias olimp adasinternacionais e, mais recentemente, servindo no Comit Executivoda de come arEste livro dedicado a um tema que, paradoxalmente, extre-mamente simples, mas muitas vezes considerado dif cil poralunose professores.

2 Talvez isto se deva ao fato de que, diferentemente doque ocorre com outros assuntos da matem tica secund ria, cujo en-sino muitas vezes fortemente baseado na aplica o de f rmulas erepeti o de problemas-modelo, preciso pensar para resolver pro-blemas, mesmo os mais simples, de Contagem . Isto faz com que otema seja especialmente apropriado para este est gio, contribuindopara desenvolver a imagina o dos alunos e a sua confian a para re-solver muitos anos, o estudo de problemas de Contagem (e maisrecentemente de Probabilidade ) fez parte, exclusivamente, do EnsinoM dio. Entretanto, o tema perfeitamente acess vel aos alunos doEnsino Fundamental, o que tem sido reconhecido, por exemplo, pelosPar metros Curriculares editados pelo apostila possui 5 cap tulos. O primeiro destinado a ambosos grupos. desej vel que os alunos, principalmente os do grupo 1,resolvam todos os problemas propostos e que os instrutores encora-jem a exposi o de solu es diferentes e, principalmente, de solu eserradas.

3 Como em outras reas da Matem tica, muitas vezes apren-demos mais com os erros do que com os acertos ao resolver problemasde Contagem . Os Cap tulos 2 e 3 cont m essencialmente o mesmomaterial (uma introdu o no o de Probabilidade ), escritos paraiiidiferentes n veis de maturidade, sendo, em princ pio, indicados paraos grupos 1 e 2, respectivamente. Os Cap tulos 4 e 5 foram escritoscom os alunos do grupo 2 em mente, mas tamb m s o acess veis aosdo grupo 1, caso haja es para todos os problemas podem ser encontradas no claro que s devem ser consultadas ap s uma tentativa s riade resolu o dos de terminar com dois agradecimentos. O primeiro paraa Profa. Maria L cia Villela, pela revis o extremamente benfeita domaterial, tendo contribu do com diversas sugest es que foram incor-poradas ao texto. Mas o agradecimento mais especial vai parao C sar Morgado. Se os leitores acharem que estas notas s oparecidas com os seus escritos e suas aulas, isto n o mera coinci-d ncia.

4 Tive a sorte de ter sido aluno do Prof. Morgado no 3oanodo Ensino M dio, quando tive ocasi o de aprender sobre contagemdo modo exposto nesta apostila. At hoje continuo aprendendo comele, como colega e coautor. Espero que cada um de voc s, alunos, te-nha a oportunidade de ter um professor de Matem tica t o inspiradorquanto autorSum rio1 M todos de Contagem12 Probabilidade (grupo 1)163 Probabilidade (grupo 2)214 Mais Permuta es e Combina es (grupo 2)305 Probabilidade Condicional (grupo 2)396 Exerc cios Adicionais457 Solu es dos Exerc cios53iiiCap tulo 1M todos de ContagemProblemas de Contagem s o, muitas vezes, considerados dif ceisentre alunos e professores, apesar de as t cnicas matem ticas neces-s rias serem bastante elementares: essencialmente, o conhecimentodas opera es aritm ticas de soma, subtra o, multiplica o e divi-s o. O objetivo deste material habituar o aluno a trabalharcomproblemas de Contagem e a ver que, afinal de contas, tais problemaspodem ser resolvidos com racioc nios simples na grande maioria doscasos, sem exigir o uso de f rmulas complicadas.

5 Isto o que procu-ramos mostrar nos exemplos a bandeira com a forma abaixo vai ser pintadautilizando duas das cores dadas. 12 CAP. 1: M TODOS DE Contagem (a)Liste todas as poss veis bandeiras. Quantas s o elas?Solu o: importante ter um procedimento sistem tico para listartodas as poss veis bandeiras, sem repeti-las. Para tal, devemos iden-tificar as diferentes decis es a serem tomadas e examinar todas aspossibilidades para cada uma delas. No caso deste problema,umaforma natural para planejar o preenchimento da bandeira : escolher a cor a ser utilizada para a parte externa; a seguir, escolher a cor para o c rculo primeira decis o pode ser feita de3modos diferentes, j que a corexterna pode ser qualquer uma das dispon veis. Uma vez tomada estadecis o, a cor escolhida n o pode mais ser usada para o c rculo exemplo, se a cor preta for escolhida para a parte externa, a corinterna dever ser cinza ou , ent o, listar todas as poss veis bandeiras, que s o6, deacordo com a figura abaixo.

6 Com a cor externa preta: Cor a cor externa cinza: Cor a cor externa branca: Um fato importante, que pode ser explorado na Contagem eficiente do3n mero poss vel de bandeiras, o seguinte: as cores dispon veis parapintar o c rculo mudam de acordo com a escolha da parte externa,mas a sua quantidade sempre a mesma, j que, qualquer que seja acor externa escolhida, h sempre duas cores restantes para oc , poder amos ter empregado o seguinte racioc nio para contaro n mero de poss veis bandeiras, sem list -las:A cor externa pode ser escolhida de tr s modos diferentes. Qualquerque seja essa escolha, a cor do c rculo pode ser escolhida de dois mo-dos. Logo, o n mero total de possibilidades 2 + 2 + 2 = 3 2 = procedimento acima ilustra oPrinc pio MultiplicativoouPrinc pioFundamental da Contagem :Se uma decis oD1pode ser tomada depmodos e, qualquer que sejaessa escolha, a decis oD2pode ser tomada deqmodos, ent o o n -mero de maneiras de se tomarem consecutivamente as decis esD1eD2 igual Princ pio Multiplicativo pode ser ilustrado com o aux liode uma rvore de enumera o como a da figura a doc rculo4 CAP.

7 1: M TODOS DE Contagem (b)Quantas s o as poss veis bandeiras no caso em que4cores est odispon veis?Solu o:As decis es a serem tomadas s o exatamente as mesmas docaso anterior, tendo mudado apenas o n mero de possibilidades deescolha. Para a cor externa, temos agora4possibilidades. Uma vezescolhida a cor externa, a cor do c rculo pode ser qualquer uma dasoutras3. Logo, pelo Princ pio Multiplicativo, o n mero de modosdiferentes para pintar a bandeira 4 3 = s o as formas de pintar a bandeira a seguirutilizando3cores diferentes dentre4dadas? Solu o:Agora, temos3decis es consecutivas a tomar: a cor externa,a do ret ngulo e a do c rculo. A cor externa pode ser qualquer umadas4cores; uma vez escolhida a cor externa, o ret ngulo pode serpintado de tr s modos distintos. Logo, a escolha combinada da corexterna e do ret ngulo pode ser feita de4 3 = 12modos. Paracada um destes12modos, o c rculo pode ser pintado com uma dasduas cores que sobraram. Logo, o n mero total de possibilidades 4 3 2 = racioc nio acima mostra que o Princ pio Multiplicativo pode, na5realidade, ser aplicado quando temos diversas etapas de decis o: desdeque o n mero de possibilidades em cada etapa n o dependa das de-cis es anteriores, basta multiplic -los para achar o n mero total pintar a bandeira abaixo, h 4cores dispon quantos modos ela pode ser pintada de modo que faixas adjacentestenham cores distintas?

8 Solu o:O primeiro passo escolher em que ordem vamos pintara bandeira. Podemos, por exemplo, pintar as faixas de cima parabaixo (veja, no exerc cio 16, o que ocorre quando escolhemosmal aordem de preenchimento). A cor da primeira faixa pode ser qualqueruma das4cores. Qualquer que seja a cor escolhida, para a segundafaixa temos3cores para escolher. Escolhida a cor da segunda faixa,a terceira pode ser pintada de qualquer cor, exceto a usada para asegunda faixa. Assim, temos novamente3possibilidades de CAP. 1: M TODOS DE CONTAGEMO n mero total de possibilidades , ent o:4 3 3= 36 1afaixa2afaixa3afaixaExemplo s o os n meros de tr s algarismos distintos?Solu o:Vamos escolher, sucessivamente, os tr s algarismos, come- ando com o da esquerda (isto importante, como veremos abaixo).O primeiro algarismo pode ser escolhido de9modos, pois n o podeser igual a0. O segundo algarismo pode ser escolhido de9modos, poisn o pode ser igual ao primeiro algarismo. O terceiro algarismo podeser escolhido de8modos, pois n o pode ser igual nem ao primeironem ao segundo resposta 9 9 8 = c digo Morse usa duas letras, ponto e tra o, e aspalavras t m de1a4letras.

9 Quantas s o as palavras do c digoMorse?Solu o:H palavras de1,2,3e4letras, em quantidades , nossa estrat gia a de usar o Princ pio Multiplicativo paracontar separadamente estas palavras e, depois, somar estasquanti-dades. H 2palavras de uma letra; h 2 2 = 4palavras de duasletras, pois h dois modos de escolher a primeira letra e doismodosde escolher a segunda letra; analogamente, h 2 2 2 = 8palavrasde tr s letras e2 2 2 2 = 16palavras de4letras. O n merototal de palavras 2 + 4 + 8 + 16 = j deve ter percebido nesses exemplos qual a estrat gia pararesolver problemas de Contagem :1. Postura:Devemos sempre nos colocar no papel da pessoa quedeve fazer a a o solicitada pelo problema e ver que decis esdevemostomar. Nas diversas situa es dos Exemplos 1 a 3, n s nos colocamosno papel da pessoa que deveria colorir a bandeira; no Exemplo4,colocamo-nos no papel da pessoa que deveria escrever o n Divis o:Devemos, sempre que poss vel, dividir as decis es aserem tomadas em decis es mais simples, correspondentes sdiversasetapas do processo de decis o.

10 Colorir a bandeira foi dividido emcolorir cada regi o; formar um n mero de tr s algarismos foidivididoem escolher cada um dos tr s algarismos. Formar a palavra no c digoMorse foi dividido em escolher o n mero de letras e, a seguir,emescolher cada ordem em que as decis es s o tomadas pode ser extremamente im-portante para a simplicidade do processo de resolu o. Vamos voltarao Exemplo 4 (Quantos s o os n meros de tr s algarismos distintos?)para ver como uma estrat gia equivocada pode levar a uma solu odesnecessariamente ando a escolha dos algarismos pelo ltimo algarismo, h 10modos de escolher o ltimo algarismo. Em seguida, h 9modos deescolher o algarismo central, pois n o podemos repetir o algarismo j usado. Agora temos um impasse: de quantos modos podemos esco-lher o primeiro algarismo? A resposta depende . Se n o tivermosusado o0, haver 7modos de escolher o primeiro algarismo, pois n opoderemos usar nem o0nem os dois algarismos j usados nas demaiscasas; se j tivermos usado o0, haver 8modos de escolher o CAP.