\n
\nna An\u00e1lise Combinat\u00f3ria<\/strong><\/div>\n
\n
\n
\n
Voc\u00ea j\u00e1 ouviu falar em An\u00e1lise Combinat\u00f3ria? <\/p>\n
Se voc\u00ea j\u00e1 estudou esse assunto, palavras como combina\u00e7\u00f5es<\/strong>, arranjos <\/strong> e permuta\u00e7\u00f5es<\/strong> possivelmente surgiram em sua mente. E isso \u00e9 natural, j\u00e1 que o estudo da An\u00e1lise Combinat\u00f3ria, pelo menos em seu est\u00e1gio inicial, trata da resolu\u00e7\u00e3o de problemas de Contagem e "combina\u00e7\u00f5es, arranjos e permuta\u00e7\u00f5es" s\u00e3o ferramentas utilizadas para resolver problemas de Contagem. Mas voc\u00ea sabia que n\u00e3o precisamos necessariamente utilizar f\u00f3rmulas para resolver problemas de Contagem?<\/strong> <\/p>\n Embora muitos exerc\u00edcios envolvendo Contagem sejam resolvidos utilizando-se alguma das t\u00e9cnicas citadas anteriormente – combina\u00e7\u00f5es, arranjos, permuta\u00e7\u00f5es – nem sempre conseguimos respostas t\u00e3o facilmente. Mais do que f\u00f3rmulas, por diversas vezes, a solu\u00e7\u00e3o de um problema de Contagem exige apenas engenhosidade e a real compreens\u00e3o da situa\u00e7\u00e3o apresentada no seu enunciado. \n Vamos l\u00e1?<\/p>\n Iniciaremos os nossos estudos aprendendo (ou relembrando) o que s\u00e3o anagramas<\/strong><\/span>. <\/p>\n \n \n H\u00e1 tamb\u00e9m anagramas que n\u00e3o fazem sentido, por exemplo:<\/p>\n ►<\/span> Exibimos acima alguns anagramas da palavra [tex]PORTA \\, [\/tex]. E se quis\u00e9ssemos saber quantos anagramas essa palavra possui?<\/strong><\/p>\n \n[tex]\\begin{array}{c c c c c} \n \n Agora, vamos ver dois exemplos motivadores do racioc\u00ednio que iremos explorar.<\/p>\n \n ►<\/span> Vamos calcular em quantos anagramas da palavra [tex]PORTA[\/tex] as vogais aparecem em ordem alfab\u00e9tica, ou seja, vamos determinar em quantos anagramas a letra [tex]A[\/tex] aparece antes da letra [tex]O[\/tex]. Como podemos resolver esse problema? <\/strong><\/p>\n Voc\u00ea deve ficar atento ao fato de que as vogais n\u00e3o precisam estar juntas. A palavra [tex]PARTO[\/tex] \u00e9 um dos anagramas que satisfazem \u00e0s condi\u00e7\u00f5es do problema. E [tex]AOTRP[\/tex] tamb\u00e9m o \u00e9. Note que os dois grupos possuem a mesma quantidade de anagramas (trocando o [tex]A[\/tex] pelo [tex]O[\/tex] temos um anagrama de cada grupo). \n \n ►<\/span> Troquemos de palavra. Se a palavra for [tex]ALUNO[\/tex], quantos s\u00e3o os anagramas em que as vogais est\u00e3o em ordem alfab\u00e9tica?<\/strong><\/p>\n Novamente, todos esses grupos cont\u00eam a mesma quantidade de anagramas. \n Nos dois exemplos, \u00e9 importante perceber que das [tex]120[\/tex] permuta\u00e7\u00f5es de cinco elementos escolhemos apenas aquelas em que as vogais n\u00e3o permutaram entre si. Assim, os grupos em que dividimos os anagramas, nos dois exemplos, “surgiram” da respectiva quantidade de permuta\u00e7\u00f5es das vogais de cada palavra: [tex]2=2![\/tex], na palavra porta, e [tex]6=3![\/tex], na palavra aluno. \n Vamos fazer mais um exemplo para ver se est\u00e1 entendida a estrat\u00e9gia?<\/p>\n \n Que tal voc\u00ea tentar resolver este problema? O diagrama a seguir ilustra essas op\u00e7\u00f5es.<\/li>\n<\/ul>\n \n[tex]\\begin{array}{c c c c c c} Logo, pelo Princ\u00edpio Fundamental da Contagem, o n\u00famero de modos distintos de embaralharmos as letras da palavra [tex]CAMELO \\, [\/tex] \u00e9 dado por [tex] \\, \\fcolorbox{#589386}{#ddebe8}{$\\textcolor{blue}{6}\\times\\textcolor{blue}{5}\\times \\textcolor{blue}{4}\\times \\textcolor{blue}{3}\\times \\textcolor{blue}{2}\\times \\textcolor{blue}{1}=720$} \\, .[\/tex]<\/p>\n \n [tex]\\textcolor{#589386}{(2)}[\/tex] Calculado o n\u00famero de anagramas sem qualquer restri\u00e7\u00e3o, observe que, para cada arruma\u00e7\u00e3o das vogais, podemos permutar as consoantes de [tex]6[\/tex] maneiras<\/p>\n \n[tex]\\begin{array}{c c c} das quais apenas uma apresenta as consoantes em ordem alfab\u00e9tica: <\/p>\n \n [tex]\\textcolor{#589386}{(3)}[\/tex] Como temos um total de [tex]720[\/tex] anagramas da palavra [tex]CAMELO \\, [\/tex] e desse total nos interessa apenas um sexto, a resposta deste problema \u00e9 [tex] \\, \\fcolorbox{#589386}{#ddebe8}{$\\dfrac{720}{6}=120$} \\, [\/tex] anagramas com as consoantes em ordem alfab\u00e9tica.<\/p>\n Observa\u00e7\u00f5es:<\/strong> \n<\/div>\n \n \n Passando a limpo…<\/p>\n – Ignoramos a princ\u00edpio as restri\u00e7\u00f5es de cada problema e iniciamos contando casos a mais. E como isso foi feito?<\/strong><\/p>\n \n ✐<\/span> Para contar sem restri\u00e7\u00f5es, nada mais \u00fatil do que utilizar o PFC<\/strong>: Princ\u00edpio Fundamental da Contagem. \n Assim, acabamos de descobrir mais uma utilidade da divis\u00e3o:<\/p>\n eliminar casos indevidamente contados em uma permuta\u00e7\u00e3o.<\/p>\n<\/div>\n \n Precisam de mais problemas?<\/p>\n \n De quantas maneiras diferentes o senhor Bruno poderia fazer essas atividades?<\/p>\n \n \n de quantas maneiras ele poderia execut\u00e1-las?<\/p>\n \n Portanto, a resposta do problema fica [tex]\\fcolorbox{#589386}{#ddebe8}{$\\dfrac{\\frac{6!}{2!}}{{2!}}=\\dfrac{6!}{2!2!}=180$} \\, .[\/tex] \n \n \n Na imagem acima temos doze crian\u00e7as – sete meninos e cinco meninas- e todos com alturas diferentes. \n At\u00e9 agora, obtivemos a quantidade de filas com as meninas ordenadas por altura, mas nessas filas os meninos ainda n\u00e3o est\u00e3o ordenados. <\/p>\n Portanto, o resultado final \u00e9 [tex]\\fcolorbox{#589386}{#ddebe8}{$\\dfrac{\\frac{12!}{5!}}{7!}=\\dfrac{12!}{5!7!}=792$} \\, .[\/tex] \n \n \n Mart\u00edn teve a ideia de convidar todos os sete novos amigos para um churrasco. Para isso, \u00e9 necess\u00e1rio ir at\u00e9 \u00e0 casa de cada um deles. De quantas maneiras isso pode ser feito se a primeira casa visitada deve ser a da Magali e, para que n\u00e3o haja brigas, antes de passar na casa do Cebolinha e do Casc\u00e3o, Mart\u00edn deve passar na casa da M\u00f4nica?<\/p>\n \n No total, pelo princ\u00edpio aditivo, existem [tex]\\fcolorbox{#589386}{#ddebe8}{$120+120=240$}[\/tex] maneiras diferentes de Mart\u00edn fazer os convites para seus amigos, respeitadas as regras impostas.\n<\/p><\/div>\n<\/div>\n<\/div>\n \n \n Os primeiros alvos de cada corrente est\u00e3o presos a um suporte e os outros est\u00e3o presos aos respectivos alvos imediatamente acima. \n \n Estamos interessados nos anagramas da palavra [tex]ABCDEFGH[\/tex], que no total s\u00e3o [tex]8! \\, [\/tex], tais que <\/p>\n Ficamos, ent\u00e3o, com um total de [tex] \\, \\fcolorbox{#589386}{#ddebe8}{$\\dfrac{8!}{3!2!3!}=560$} \\, [\/tex] possibilidades de acertos dos oito alvos, conforme as regras impostas.\n<\/p><\/div>\n<\/div>\n<\/div>\n Os pr\u00f3ximos problemas s\u00e3o para voc\u00eas…<\/p>\n Problema 6<\/strong><\/span> \n \n Problema 7<\/strong><\/span> \n \n \n Na pr\u00f3xima corrida, os competidores ser\u00e3o colocados em fila, de maneira que os n\u00fameros pares fiquem em ordem decrescente e os \u00edmpares em ordem crescente. \n \n \n Como o pr\u00f3prio nome indica, ele sempre tenta trapacear durante as corridas. Por esse motivo, na pr\u00f3xima corrida, ele dever\u00e1 largar na \u00faltima posi\u00e7\u00e3o. \n \n Bom trabalho, pessoal! <\/strong><\/p>\n \n \n Equipe COM – OBMEP<\/strong><\/span><\/p>\n<\/div>\n \n Clique no bot\u00e3o abaixo para visualizar a Sala. Mais um papel da divis\u00e3o na An\u00e1lise Combinat\u00f3ria Voc\u00ea j\u00e1 ouviu falar em An\u00e1lise Combinat\u00f3ria? Se voc\u00ea j\u00e1 estudou esse assunto, palavras como combina\u00e7\u00f5es, arranjos e permuta\u00e7\u00f5es possivelmente surgiram em sua mente. E isso \u00e9 natural, j\u00e1 que o estudo da An\u00e1lise Combinat\u00f3ria, pelo menos em seu … <\/p>\n
\nMas essas n\u00e3o s\u00e3o as \u00fanicas ferramentas que existem na An\u00e1lise Combinat\u00f3ria. Embora n\u00e3o t\u00e3o conhecido, o Princ\u00edpio das Gavetas de Dirichlet<\/strong> (tamb\u00e9m denominado Princ\u00edpio das Casas de Pombos<\/strong>), por exemplo, \u00e9 uma t\u00e9cnica muito eficaz na resolu\u00e7\u00e3o de determinados problemas de Contagem. (Se voc\u00ea n\u00e3o conhece esse Princ\u00edpio, voc\u00ea pode encontrar uma Sala de Estudo sobre ele no nosso Blog clicando AQUI<\/strong><\/span><\/a>.)<\/span>
\nOutra lembran\u00e7a que certamente surge na mente de quem j\u00e1 resolveu problemas de Contagem \u00e9 a utiliza\u00e7\u00e3o de muitas e muitas f\u00f3rmulas…<\/p>\n
\nNesta Sala de Estudos, vamos apresentar um tipo de racioc\u00ednio que permite resolver alguns problemas utilizando um pouco de criatividade. Mas, para que voc\u00ea entenda bem os problemas que ser\u00e3o propostos, voc\u00ea vai precisar do Princ\u00edpio Fundamental da Contagem – PFC<\/strong>. Se voc\u00ea n\u00e3o conhece ou n\u00e3o se lembra desse Princ\u00edpio, d\u00ea uma passadinha nesta Sala <\/strong><\/span><\/a> do nosso Blog antes de prosseguir. Afinal, o PFC \u00e9 um dos pilares da An\u00e1lise Combinat\u00f3ria!<\/strong> <\/p>\n
\n
\n
\n
\nAssim, os anagramas de uma dada palavra s\u00e3o as palavras obtidas pelo "embaralhamento" das letras da palavra original (manter as letras mudando ou n\u00e3o a ordem).<\/p>\n\n
\n
\n
\nA ideia de “embaralhar” as letras \u00e9 a mesma que a de permut\u00e1-las; portanto, a palavra [tex]PORTA[\/tex] possui:
\n[tex]\\qquad \\qquad 5!=5\\times 4\\times 3\\times 2\\times 1=120[\/tex] anagramas.
\nVamos visualizar essa conta?<\/p>\n\n
\n\\textcolor{blue}{5}\\text{ escolhas}&\\textcolor{blue}{4}\\text{ escolhas}&\\textcolor{blue}{3}\\text{ escolhas}&\\textcolor{blue}{2}\\text{ escolhas}&\\textcolor{blue}{1}\\text{ escolha}\\\\
\n\\overline{\\text{primeira letra}}&\\overline{\\text{segunda letra}}&\\overline{\\text{terceira letra}}& \\overline{\\text{quarta letra}}& \\overline{\\text{quinta letra}}
\n\\end{array}[\/tex]<\/p>\n\n
\nUma poss\u00edvel solu\u00e7\u00e3o para o problema \u00e9 a seguinte:
\nQualquer anagrama da palavra [tex]PORTA[\/tex] est\u00e1 em um dos dois grupos:<\/p>\n\n
\nLogo, a resposta do problema \u00e9 [tex] \\, \\fcolorbox{#589386}{#ddebe8}{$\\dfrac{5!}{2}=60$}:[\/tex] metade do total de todos os anagramas.\n<\/p><\/div>\n
\n
\n
\n
\n
\n
\n\nNeste exemplo, observamos que os poss\u00edveis anagramas podem ser agrupados em seis grupos:<\/p>\n
\n
\nPerceba que queremos apenas o primeiro grupo, pois nele as vogais est\u00e3o em ordem alfab\u00e9tica; como a palavra [tex]ALUNO[\/tex] possui [tex]5![\/tex] anagramas a resposta deste problema \u00e9 [tex] \\, \\fcolorbox{#589386}{#ddebe8}{$\\dfrac{5!}{6}=20$} \\, [\/tex], ou seja, um sexto do total dos anagramas da palavra em quest\u00e3o.\n<\/ul>\n<\/div>\n
\nDessa forma, a resposta poderia ser calculada por [tex] \\, \\boxed{\\dfrac{5!}{2!}} \\, [\/tex], no caso da palavra porta<\/strong> , e [tex] \\, \\boxed{\\dfrac{5!}{3!}} \\, [\/tex], no exemplo da palavra aluno<\/strong>.
\nNas duas situa\u00e7\u00f5es, a divis\u00e3o por [tex]2![\/tex] e [tex]3! \\, [\/tex], respectivamente, pode ser entendida como uma corre\u00e7\u00e3o que fazemos no c\u00e1lculo dos anagramas ([tex]5![\/tex]), j\u00e1 que as vogais de cada palavra n\u00e3o podem trocar de lugar entre si.<\/p>\n
\nDepois, clique no bot\u00e3o abaixo para ver a solu\u00e7\u00e3o.<\/p>\n
\nLembrando que as letras n\u00e3o se repetem, temos:<\/p>\n\n
\n
\n\\textcolor{blue}{6}\\text{ escolhas}&\\textcolor{blue}{5}\\text{ escolhas}&\\textcolor{blue}{4}\\text{ escolhas}&\\textcolor{blue}{3}\\text{ escolhas}&\\textcolor{blue}{2}\\text{ escolhas}&\\textcolor{blue}{1}\\text{ escolha}\\\\
\n\\overline{\\text{primeira letra}}&\\overline{\\text{segunda letra}}&\\overline{\\text{terceira letra}}& \\overline{\\text{quarta letra}}& \\overline{\\text{quinta letra}}& \\overline{\\text{sexta letra}}
\n\\end{array}[\/tex]<\/p>\n
\n\\textcolor{blue}{3}\\text{ escolhas}&\\textcolor{blue}{2}\\text{ escolhas}&\\textcolor{blue}{1}\\text{ escolha}\\\\
\n\\overline{\\text{primeira consoante}}&\\overline{\\text{segunda consoante}}&\\overline{\\text{terceira consoante}}
\n\\end{array}[\/tex]<\/p>\n\n
\na)<\/strong> Note que fizemos as continhas intermedi\u00e1rias; mas, tratando-se de produtos, n\u00e3o se apresse em faz\u00ea-las. Apenas indique-as, pois na finaliza\u00e7\u00e3o do problema podem ocorrer simplifica\u00e7\u00f5es.
\nb)<\/strong> Lembre-se de que para calcular a quantidade de anagramas de uma palavra com [tex]n[\/tex] letras distintas, basta calcular o fatorial de [tex]n.[\/tex] No nosso caso ter\u00edamos [tex]6!=720[\/tex] anagramas. A quantidade de grupos em que dividimos os anagramas corresponde ao n\u00famero de permuta\u00e7\u00f5es de tr\u00eas elementos, que tamb\u00e9m pode ser calculado via fatorial: [tex]3!=6.[\/tex] Dessa forma, a resposta final poderia ser calculada por:
\n [tex]\\qquad \\qquad \\dfrac{6!}{3!}=\\dfrac{6 \\times 5 \\times 4 \\times 3 \\times 2 \\times 1}{3 \\times 2 \\times 1}=6 \\times 5 \\times 4=120[\/tex]<\/p>\n<\/div>\n<\/div>\n
\n
\n
\n
\n– Em um segundo momento, desconsideramos os casos que n\u00e3o nos interessavam e que foram indevidamente contados.<\/strong><\/p>\n
\n ✄<\/span> Para descontar o que foi indevidamente contado, utilizamos divis\u00f5es.<\/p>\n
\n
\n
\n
\nO senhor Bruno realiza cinco atividades di\u00e1rias durante as manh\u00e3s da semana. S\u00e3o elas:<\/p>\n\n
\n[tex]A[\/tex]) Levar a filha \u00e0 escola;
\n[tex]B[\/tex]) Tomar caf\u00e9 da manh\u00e3:
\n[tex]C[\/tex]) Comprar o Jornal;
\n[tex]D[\/tex]) Fazer exerc\u00edcios f\u00edsicos;
\n[tex]E[\/tex]) Buscar a filha na escola.
\nAgora, perceba que o problema tem uma restri\u00e7\u00e3o: o senhor Bruno n\u00e3o pode buscar a filha na escola sem antes t\u00ea-la levado<\/strong>. Com isso, devemos ter sempre a atividade [tex]A[\/tex] antes da [tex]E[\/tex].
\nPodemos, ent\u00e3o, encarar o problema como formar um anagrama da palavra [tex]ABCDE[\/tex], mantendo as vogais em ordem alfab\u00e9tica.
\nNeste caso, obtemos como resposta [tex]\\fcolorbox{#589386}{#ddebe8}{$\\dfrac{5!}{2!}=60$} \\, .[\/tex]\n<\/div>\n<\/div>\n<\/div>\n
\nE se as atividades do senhor Bruno fossem:<\/p>\n\n
\n[tex]A[\/tex]) Levar a filha \u00e0 escola;
\n[tex]B[\/tex]) Tomar caf\u00e9 da manh\u00e3:
\n[tex]C[\/tex]) Comprar o Jornal;
\n[tex]D[\/tex]) Fazer exerc\u00edcios f\u00edsicos;
\n[tex]E[\/tex]) Buscar a filha na escola;
\n[tex]F[\/tex]) Ler o Jornal.
\nAgora o problema apresenta duas restri\u00e7\u00f5es: o senhor Bruno "n\u00e3o pode buscar a filha na escola sem antes t\u00ea-la levado" e "s\u00f3 poder\u00e1 ler o jornal depois de t\u00ea-lo comprado".
\nDessa forma, o que temos \u00e9 uma situa\u00e7\u00e3o an\u00e1loga a determinar os anagramas da palavra [tex]ABCDEF[\/tex], com o [tex]A[\/tex] aparecendo antes do [tex]E[\/tex] e, o [tex]C \\, [\/tex], antes do [tex]F[\/tex]. Vamos determinar quantos s\u00e3o esses anagramas. <\/p>\n\n
\nDestes, h\u00e1 dois tipos:<\/p>\n\n
\nMais uma vez, \u00e9 importante perceber que o primeiro [tex]2![\/tex] surge porque queremos o [tex]A[\/tex] na frente do [tex]E[\/tex] e, o segundo [tex]2![\/tex], porque queremos tamb\u00e9m o [tex]C[\/tex] na frente do [tex]F[\/tex].\n<\/p><\/div>\n<\/div>\n<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2018\/02\/F001.png\")
<\/p>\n
\nDe quantas maneiras podemos formar uma fila, de forma que os meninos entre si e as meninas entre si estejam em ordem crescente de altura?<\/p>\n\n
\n
\nDessa forma, s\u00e3o [tex]792[\/tex] filas poss\u00edveis de serem formadas, segundo as condi\u00e7\u00f5es do problema.\n<\/p><\/div>\n<\/div>\n<\/div>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2020\/02\/f02.png\")
<\/p>\n
\nA princ\u00edpio a resposta seria [tex]6![\/tex]. Por\u00e9m, com a restri\u00e7\u00e3o relativa ao Cebolinha e ao Casc\u00e3o, temos dois casos para considerar:<\/p>\n\n
\nEm um torneio de tiro, oito alvos s\u00e3o dispostos em tr\u00eas correntes penduradas, como mostra a figura abaixo. <\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2018\/02\/F003.png\")
\n<\/p>\n
\nPara ganhar a competi\u00e7\u00e3o todos os oito alvos devem ser atingidos. Assim, se um competidor acertar um alvo sem ter atirado no(s) que est\u00e1(\u00e3o) abaixo, este(s) cair\u00e1(\u00e3o) e o competidor n\u00e3o ganhar\u00e1 a pontua\u00e7\u00e3o relativa aos alvos perdidos.
\nPara obter a pontua\u00e7\u00e3o m\u00e1xima do torneio, de quantas maneiras diferentes cada competidor pode acertar os oito alvos?<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2018\/02\/F004.png\")
\n<\/p>\n\n
\nQuantos s\u00e3o os anagramas da palavra [tex]UNIVERSO[\/tex] em que as vogais aparecem em ordem alfab\u00e9tica?<\/p>\n
\n Vamos formar sequ\u00eancias com todos os n\u00fameros naturais [tex]1, \\, 2, \\, \\cdots , \\, 10[\/tex] de modo que o [tex]5[\/tex] esteja situado \u00e0 direita do [tex]2[\/tex] e \u00e0 esquerda do [tex]3[\/tex], embora n\u00e3o necessariamente em lugares consecutivos.
\nQuantas sequ\u00eancias obteremos?<\/p>\n
\n Um dos desenhos mais famosos e engra\u00e7ados de competi\u00e7\u00e3o \u00e9 o "CORRIDA MALUCA<\/strong>". Nele os carros dos onze competidores s\u00e3o numerados de 00 <\/strong> a 10<\/strong>.<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2018\/02\/F005.jpg\")
<\/p>\n
\nDe quantas maneiras diferentes isso pode ser feito? <\/p>\n
\n Um dos competidores da "CORRIDA MALUCA<\/strong>" \u00e9 o Dick Vigarista<\/strong><\/em> (carro 00).<\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2018\/02\/F006.jpg\")
<\/p>\n
\nDe quantas maneiras poder\u00e1 ser montada a largada, respeitando a ordem estabelecida no problema anterior?<\/p>\n
\n
\n
\n
\n[1]<\/strong> Pais & Filhos<\/strong><\/span><\/a> (\u00daltimo acesso em 14\/06\/20)
\n[2]<\/strong> Mauri\u00e7\u00e3o<\/strong><\/span><\/a> (\u00daltimo acesso em 14\/06\/20)
\n[3]<\/strong> TN<\/strong><\/span><\/a> (\u00daltimo acesso em 14\/06\/20)
\n[4]<\/strong> Mercado Livre<\/strong><\/span><\/a> (\u00daltimo acesso em 14\/06\/20)\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"