{"id":149015,"date":"2020-03-16T01:24:14","date_gmt":"2020-03-16T04:24:14","guid":{"rendered":"http:\/\/clubes.obmep.org.br\/blog\/?page_id=149015"},"modified":"2024-11-26T23:16:26","modified_gmt":"2024-11-27T02:16:26","slug":"sala-de-estudo-permutacao-caotica","status":"publish","type":"page","link":"https:\/\/clubes.obmep.org.br\/blog\/sala-de-estudo-permutacao-caotica\/","title":{"rendered":".Sala de Estudo: Permuta\u00e7\u00e3o Ca\u00f3tica"},"content":{"rendered":"

\n

\n
Permuta\u00e7\u00e3o Ca\u00f3tica<\/strong><\/div>\n
\n
\n
\n\u00c9 muito comum em nosso pa\u00eds, geralmente no Natal e tamb\u00e9m na P\u00e1scoa, uma brincadeira conhecida como “amigo-oculto” ou “amigo-secreto”.
\nNessa conhecida brincadeira, os participantes ir\u00e3o trocar presentes, sem que cada um saiba de quem vai ganhar seu presente e, obviamente, o que vai ganhar! Para isso, os nomes dos participantes s\u00e3o escritos um a um em peda\u00e7os de papel que s\u00e3o dobrados e colocados em uma urna ou caixinha. Cada participante retira ent\u00e3o um papelzinho contendo um nome. Caso algum participante retire seu pr\u00f3prio nome, o processo de retirada \u00e9 reiniciado, tantas vezes quanto necess\u00e1rio para que cada participante tenha um amigo secreto que n\u00e3o seja ele pr\u00f3prio!<\/p>\n

\n\"\"Imagem extra\u00edda de https:\/\/www.portalamirt.com.br<\/p>\n

Um belo problema seria investigar de quantas formas diferentes cada participante pode sortear aleatoriamente o \u201cpapelzinho\u201d com o nome de quem vai presentear de modo que ningu\u00e9m tire o pr\u00f3prio nome. Nesta Sala de Estudos, apresentaremos uma t\u00e9cnica de contagem com a qual conseguiremos resolver esse problema: a chamada Permuta\u00e7\u00e3o Ca\u00f3tica<\/strong><\/span>.
\nMas para que voc\u00ea entenda bem essa nova t\u00e9cnica, \u00e9 muito importante ter um bom dom\u00ednio do Princ\u00edpio Fundamental da Contagem<\/em><\/strong>. (Que tal passar nesta Sala<\/em><\/strong><\/span><\/a> para revisar este conceito?)<\/span><\/div>\n

Vamos l\u00e1?<\/p>\n

\n
\n
\n
\n

Brincando com o tema<\/p>\n

Vamos come\u00e7ar o nosso estudo com um probleminha para desenvolvermos uma nova habilidade.<\/p>\n

\nProblema 1<\/strong><\/span> (Adaptado de C\u00edrculo Matem\u00e1tico de Moscou<\/strong>)<\/span>
\nEm uma prateleira h\u00e1 tr\u00eas livros, um de Matem\u00e1tica, um de F\u00edsica e um de Qu\u00edmica. Os livros est\u00e3o arrumados, da esquerda para direita, da seguinte maneira: <\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span>.<\/p>\n

De quantas maneiras os livros podem ser rearrumados de modo que nenhum deles permane\u00e7a no mesmo lugar?<\/p>\n

\n

Solu\u00e7\u00e3o:<\/strong>
\nUma boa estrat\u00e9gia para resolver esse problema \u00e9 listar todas as possibilidades para os livros e em seguida contar quantas satisfazem o enunciado. Vejamos!
\nPelo Princ\u00edpio Fundamental da Contagem, temos [tex]3!=6[\/tex] casos para arruma\u00e7\u00e3o dos [tex]3[\/tex] livros, conforme vemos a seguir.<\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span>
\nMatem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span>
\nF\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span>
\nF\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span>
\nQu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span>
\nQu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/p>\n

Note que sendo a arruma\u00e7\u00e3o inicial<\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span>,<\/p>\n

temos apenas duas solu\u00e7\u00f5es:<\/p>\n

F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span>
\nQu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span>.<\/p>\n<\/div>\n

\n

F\u00e1cil, n\u00e3o \u00e9 mesmo?
\nAgora, que tal resolver o problema com quatro livros…<\/p>\n

\n

\nProblema 2<\/strong><\/span> (Adaptado de C\u00edrculo Matem\u00e1tico de Moscou<\/strong>)<\/span>
\nEm uma prateleira h\u00e1 [tex]4[\/tex] livros, um de Matem\u00e1tica, um de F\u00edsica, um de Qu\u00edmica e um de Biologia. Os livros est\u00e3o arrumados, da esquerda para direita, da seguinte maneira:<\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span>.<\/p>\n

De quantas maneiras os livros podem ser rearrumados de modo que nenhum deles permane\u00e7a no mesmo lugar?<\/p>\n

Solu\u00e7\u00e3o: <\/strong>
\nNovamente, vamos listar todas as arruma\u00e7\u00f5es poss\u00edveis e depois contar quantas solu\u00e7\u00f5es teremos. Veja que o Princ\u00edpio Fundamental da Contagem nos mostra que h\u00e1 [tex]4!=24[\/tex] maneiras de arrumar os livros:<\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span>
\nMatem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span>
\nMatem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span>
\nMatem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span>
\nMatem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span>
\nMatem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/p>\n

Qu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span>
\nQu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span>
\n Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span>
\nQu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Biologia<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span>
\nQu\u00edmica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span>
\nQu\u00edmica<\/span><\/span>Biologia<\/span><\/span> Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span><\/span><\/span><\/span><\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/p>\n

Note, uma vez mais, que sendo a arruma\u00e7\u00e3o inicial<\/p>\n

Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span>,<\/p>\n

temos nove solu\u00e7\u00f5es:<\/p>\n

F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>Qu\u00edmica<\/span>
\nF\u00edsica<\/span><\/span>Qu\u00edmica<\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span>
\nF\u00edsica<\/span><\/span>Biologia<\/span><\/span>Matem\u00e1tica<\/span><\/span>Qu\u00edmica<\/span>
\nQu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span>
\nQu\u00edmica<\/span><\/span>Biologia<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span>
\nQu\u00edmica<\/span><\/span>Biologia<\/span><\/span> Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span>
\nBiologia<\/span><\/span>Qu\u00edmica<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span>
\nBiologia<\/span><\/span>Qu\u00edmica<\/span><\/span>F\u00edsica<\/span><\/span>Matem\u00e1tica<\/span>
\nBiologia<\/span><\/span>Matem\u00e1tica<\/span><\/span>F\u00edsica<\/span><\/span>Qu\u00edmica<\/span>.<\/p>\n<\/div>\n

\n

A nossa estrat\u00e9gia funcionou mais uma vez, mas o trabalho foi bem maior.
\nImaginem, agora, se o problema fosse com cinco livros. Como pelo Princ\u00edpio Fundamental da Contagem h\u00e1 [tex]5!=120[\/tex] arruma\u00e7\u00f5es poss\u00edveis, utilizando a estrat\u00e9gia at\u00e9 aqui adotada, ap\u00f3s listar os [tex]120[\/tex] casos, devemos analisar quais est\u00e3o com os livros nas posi\u00e7\u00f5es adequadas.<\/p>\n

Muito trabalhoso, n\u00e3o acham!? <\/span> <\/p>\n

Al\u00e9m disso, como h\u00e1 um grande n\u00famero de casos para serem analisados, podemos n\u00e3o perceber e deixar de contar alguma solu\u00e7\u00e3o.
\nChegou a hora de apresentarmos a ferramenta matem\u00e1tica que resolver\u00e1 o problema do amigo-secreto, pois essa ferramenta pode ser tamb\u00e9m utilizada para resolver esse problema dos livros e outros mais com essa mesma caracter\u00edstica. A princ\u00edpio, vamos fazer uma apresenta\u00e7\u00e3o informal da ferramenta.<\/p>\n

\n

\nSuponha que voc\u00ea tenha um certo conjunto de elementos e que os tenha colocado em uma certa ordem, formando assim uma sequ\u00eancia ordenada.
\nVoc\u00ea pode modificar a ordem desses elementos, e formar outras sequ\u00eancias ordenadas com os mesmos elementos. Nessas novas sequ\u00eancias, elementos podem ficar na mesma posi\u00e7\u00e3o que estavam na sequ\u00eancia original ou terem suas posi\u00e7\u00f5es originais modificadas, n\u00e3o \u00e9?
\nNesta Sala, vamos tratar das reordena\u00e7\u00f5es de sequ\u00eancias nas quais TODOS os objetos mudam de lugar com rela\u00e7\u00e3o \u00e0s suas posi\u00e7\u00f5es iniciais: os desarranjos<\/strong>.
\nPor exemplo, a partir dos n\u00fameros [tex]1, 2, 3, 4[\/tex], podemos definir a sequ\u00eancia ordenada
\n\\begin{array}{c c c c c c c}
\n1&&2&&3&&4\\\\
\n\\overline{\\text{1\u00ba elemento}}&&\\overline{\\text{2\u00ba elemento}}&&\\overline{\\text{3\u00ba elemento}}&&\\overline{\\text{4\u00ba elemento}}&&
\n\\end{array}
\ne, nesse caso, usaremos a nota\u00e7\u00e3o [tex](1, 2, 3, 4)[\/tex] para indicar a ordem que fixamos.
\nObserve que as ordena\u00e7\u00f5es [tex](2, 1, 4, 3)[\/tex] e [tex](3, 1, 4, 2)[\/tex] s\u00e3o desordens da sequ\u00eancia ordenada [tex](1, 2, 3, 4)[\/tex];
\n\\begin{array}{c c c c c c c c}
\n\\textcolor{red}{1}&&\\textcolor{red}{2}&&\\textcolor{red}{3}&&\\textcolor{red}{4}&\\qquad &\\textcolor{red}{1}&&\\textcolor{red}{2}&&\\textcolor{red}{3}&&\\textcolor{red}{4}\\\\
\n2&&1&&4&&3&\\qquad &3&&1&&4&&2
\n\\end{array}
\n mas [tex](1, 3, 4, 2)[\/tex] n\u00e3o o \u00e9, j\u00e1 que o elemento [tex]1[\/tex] ficou no seu lugar primitivo.
\n\\begin{array}{c c c c c}
\n\\textcolor{red}{1}&&\\textcolor{red}{2}&&\\textcolor{red}{3}&&\\textcolor{red}{4}\\\\
\n\\textcolor{red}{1}&&3&&4&&2&
\n\\end{array}
\nMais formalmente, "uma reordena\u00e7\u00e3o dos elementos de uma sequ\u00eancia [tex]\\left(a_1, a_2, a_3, \\cdots , a_n\\right)[\/tex] \u00e9 dita um Desarranjo<\/strong>, ou uma Desordem<\/strong>, quando nenhum dos elementos [tex]a_i[\/tex] est\u00e1 na sua posi\u00e7\u00e3o original, isto \u00e9, na [tex]i[\/tex]-\u00e9sima posi\u00e7\u00e3o.
\nDenotaremos por [tex]D_{n}[\/tex] o n\u00famero de Desarranjos de uma sequ\u00eancia de [tex]n[\/tex] elementos.
\n(Observe que o n\u00famero [tex]D_{n}[\/tex] n\u00e3o est\u00e1 associado ao tipo de elementos de uma sequ\u00eancia, mas sim \u00e0s posi\u00e7\u00f5es ocupadas por tais elementos.)<\/span><\/p>\n<\/div>\n

\n

►<\/span> Com essa ferramenta, notamos que no primeiro problema, ao considerarmos a sequ\u00eancia de elementos [tex]\\left(a_1,a_2,a_3 \\right)[\/tex] com:<\/p>\n