Nessa conhecida brincadeira, os participantes irão 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ão escritos um a um em pedaços de papel que são dobrados e colocados em uma urna ou caixinha. Cada participante retira então um papelzinho contendo um nome. Caso algum participante retire seu próprio nome, o processo de retirada é reiniciado, tantas vezes quanto necessário para que cada participante tenha um amigo secreto que não seja ele próprio!
Imagem extraída de https://www.portalamirt.com.br
Um belo problema seria investigar de quantas formas diferentes cada participante pode sortear aleatoriamente o “papelzinho” com o nome de quem vai presentear de modo que ninguém tire o próprio nome. Nesta Sala de Estudos, apresentaremos uma técnica de contagem com a qual conseguiremos resolver esse problema: a chamada Permutação Caótica.
Mas para que você entenda bem essa nova técnica, é muito importante ter um bom domínio do Princípio Fundamental da Contagem. (Que tal passar nesta Sala para revisar este conceito?)
Vamos lá?
Brincando com o tema
Vamos começar o nosso estudo com um probleminha para desenvolvermos uma nova habilidade.
Em uma prateleira há três livros, um de Matemática, um de Física e um de Química. Os livros estão arrumados, da esquerda para direita, da seguinte maneira:
MatemáticaFísicaQuímica.
De quantas maneiras os livros podem ser rearrumados de modo que nenhum deles permaneça no mesmo lugar?
Solução:
Uma boa estratégia para resolver esse problema é listar todas as possibilidades para os livros e em seguida contar quantas satisfazem o enunciado. Vejamos!
Pelo Princípio Fundamental da Contagem, temos [tex]3!=6[/tex] casos para arrumação dos [tex]3[/tex] livros, conforme vemos a seguir.
MatemáticaFísicaQuímica
MatemáticaQuímicaFísica
FísicaMatemáticaQuímica
FísicaQuímicaMatemática
QuímicaFísicaMatemática
QuímicaMatemáticaFísica
Note que sendo a arrumação inicial
MatemáticaFísicaQuímica,
temos apenas duas soluções:
FísicaQuímicaMatemática
QuímicaMatemáticaFísica.
Fácil, não é mesmo?
Agora, que tal resolver o problema com quatro livros…
Em uma prateleira há [tex]4[/tex] livros, um de Matemática, um de Física, um de Química e um de Biologia. Os livros estão arrumados, da esquerda para direita, da seguinte maneira:
MatemáticaFísicaQuímicaBiologia.
De quantas maneiras os livros podem ser rearrumados de modo que nenhum deles permaneça no mesmo lugar?
Solução:
Novamente, vamos listar todas as arrumações possíveis e depois contar quantas soluções teremos. Veja que o Princípio Fundamental da Contagem nos mostra que há [tex]4!=24[/tex] maneiras de arrumar os livros:
MatemáticaFísicaQuímicaBiologiaFísicaMatemáticaQuímicaBiologia
MatemáticaFísicaBiologiaQuímicaFísicaMatemáticaBiologiaQuímica
MatemáticaBiologiaQuímicaFísicaFísicaQuímicaMatemáticaBiologia
MatemáticaBiologiaFísicaQuímicaFísicaQuímicaBiologiaMatemática
MatemáticaQuímicaBiologiaFísicaFísicaBiologiaQuímicaMatemática
MatemáticaQuímicaFísicaBiologiaFísicaBiologiaMatemáticaQuímica
QuímicaFísicaBiologiaMatemáticaBiologiaFísicaMatemáticaQuímica
QuímicaFísicaMatemáticaBiologiaBiologiaFísicaQuímicaMatemática
QuímicaMatemáticaBiologiaFísicaBiologiaQuímicaMatemáticaFísica
QuímicaMatemáticaFísicaBiologiaBiologiaQuímicaFísicaMatemática
QuímicaBiologiaFísicaMatemáticaBiologiaMatemáticaQuímicaFísica
QuímicaBiologia MatemáticaFísicaBiologiaMatemáticaFísicaQuímica
Note, uma vez mais, que sendo a arrumação inicial
MatemáticaFísicaQuímicaBiologia,
temos nove soluções:
FísicaMatemáticaBiologiaQuímica
FísicaQuímicaBiologiaMatemática
FísicaBiologiaMatemáticaQuímica
QuímicaMatemáticaBiologiaFísica
QuímicaBiologiaFísicaMatemática
QuímicaBiologia MatemáticaFísica
BiologiaQuímicaMatemáticaFísica
BiologiaQuímicaFísicaMatemática
BiologiaMatemáticaFísicaQuímica.
A nossa estratégia funcionou mais uma vez, mas o trabalho foi bem maior.
Imaginem, agora, se o problema fosse com cinco livros. Como pelo Princípio Fundamental da Contagem há [tex]5!=120[/tex] arrumações possíveis, utilizando a estratégia até aqui adotada, após listar os [tex]120[/tex] casos, devemos analisar quais estão com os livros nas posições adequadas.
Muito trabalhoso, não acham!?
Além disso, como há um grande número de casos para serem analisados, podemos não perceber e deixar de contar alguma solução.
Chegou a hora de apresentarmos a ferramenta matemática que resolverá o problema do amigo-secreto, pois essa ferramenta pode ser também utilizada para resolver esse problema dos livros e outros mais com essa mesma característica. A princípio, vamos fazer uma apresentação informal da ferramenta.
Você pode modificar a ordem desses elementos, e formar outras sequências ordenadas com os mesmos elementos. Nessas novas sequências, elementos podem ficar na mesma posição que estavam na sequência original ou terem suas posições originais modificadas, não é?
Nesta Sala, vamos tratar das reordenações de sequências nas quais TODOS os objetos mudam de lugar com relação às suas posições iniciais: os desarranjos.
Por exemplo, a partir dos números [tex]1, 2, 3, 4[/tex], podemos definir a sequência ordenada
\begin{array}{c c c c c c c}
1&&2&&3&&4\\
\overline{\text{1º elemento}}&&\overline{\text{2º elemento}}&&\overline{\text{3º elemento}}&&\overline{\text{4º elemento}}&&
\end{array}
e, nesse caso, usaremos a notação [tex](1, 2, 3, 4)[/tex] para indicar a ordem que fixamos.
Observe que as ordenações [tex](2, 1, 4, 3)[/tex] e [tex](3, 1, 4, 2)[/tex] são desordens da sequência ordenada [tex](1, 2, 3, 4)[/tex];
\begin{array}{c c c c c c c c}
\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}\\
2&&1&&4&&3&\qquad &3&&1&&4&&2
\end{array}
mas [tex](1, 3, 4, 2)[/tex] não o é, já que o elemento [tex]1[/tex] ficou no seu lugar primitivo.
\begin{array}{c c c c c}
\textcolor{red}{1}&&\textcolor{red}{2}&&\textcolor{red}{3}&&\textcolor{red}{4}\\
\textcolor{red}{1}&&3&&4&&2&
\end{array}
Mais formalmente, "uma reordenação dos elementos de uma sequência [tex]\left(a_1, a_2, a_3, \cdots , a_n\right)[/tex] é dita um Desarranjo, ou uma Desordem, quando nenhum dos elementos [tex]a_i[/tex] está na sua posição original, isto é, na [tex]i[/tex]-ésima posição.
Denotaremos por [tex]D_{n}[/tex] o número de Desarranjos de uma sequência de [tex]n[/tex] elementos.
(Observe que o número [tex]D_{n}[/tex] não está associado ao tipo de elementos de uma sequência, mas sim às posições ocupadas por tais elementos.)
► Com essa ferramenta, notamos que no primeiro problema, ao considerarmos a sequência de elementos [tex]\left(a_1,a_2,a_3 \right)[/tex] com:
- [tex]a_1:[/tex] livro de Física;
- [tex]a_2:[/tex] livro de Química;
- [tex]a_3:[/tex] livro de Matemática;
encontramos [tex]\, \fcolorbox{black}{#B2EDE0}{$D_{3}=2$}[/tex].
► Já no segundo exemplo, considerando a sequência de elementos [tex]\left(a_1,a_2,a_3, a_4\right)[/tex] com:
- [tex]a_1:[/tex] livro de Física;
- [tex]a_2:[/tex] livro de Química;
- [tex]a_3:[/tex] livro de Matemática;
- [tex] a_4:[/tex] livro de Biologia;
encontramos [tex]\, \fcolorbox{black}{#B2EDE0}{$D_{4}=9$}[/tex].
► A solução do problema semelhante aos anteriores, mas com [tex]5[/tex] livros, é [tex]D_{5}[/tex]. (Precisamos calcular esse valor.)
► Repare também que não é difícil entendermos que o número de Desarranjos em um conjunto com apenas um elemento é zero, ou seja, [tex] \fcolorbox{black}{#B2EDE0}{$D_{1}=0$}[/tex], pois não temos como "desarranjar" uma sequência com um único elemento!
► Analisando uma sequência genérica [tex]\left(a_1,a_2 \right)[/tex], vemos que para ela temos apenas um reordenamento, [tex]\left(a_2,a_1 \right)[/tex], e esse único reordenamento é um Desarranjo, pois nenhum dos dois elementos manteve sua posição original. Assim, [tex] \fcolorbox{black}{#B2EDE0}{$D_{2}=1$}[/tex].
Portanto, já conseguimos descobrir os quatro números de Desordens iniciais:
►[tex]D_{1}=0[/tex];
►[tex]D_{2}=1[/tex];
►[tex]D_{3}=2[/tex];
►[tex]D_{4}=9[/tex].
► Utilizando esses valores, vamos determinar [tex]D_{5}[/tex], ou seja, o número de Desarranjos para uma sequência com cinco elementos previamente ordenados.
[tex]A:[/tex] Desordens em que o elemento [tex]a_1[/tex] ocupará a posição do índice do elemento que está na primeira posição. Por exemplo, [tex](a_\textcolor{#FF0000}{4},a_5,a_2,\textcolor{#FF0000}{a_1},a_3)[/tex];
[tex]B:[/tex] Desordens em que o elemento [tex]a_1[/tex] não ocupará a posição do índice do elemento que está na primeira posição. Por exemplo, [tex](a_\textcolor{#FF0000}{4},a_1,a_2,\textcolor{#FF0000}{a_5},a_3)[/tex]
Dessa forma,
[tex] D_{5}=[/tex] número de elementos do conjunto [tex]A[/tex] [tex]+[/tex] número de elementos do conjunto [tex]B[/tex].
- Para formar uma desordem do grupo [tex]A[/tex], devemos tomar duas decisões:
- Escolher o elemento que ocupará a primeira posição e, consequentemente, trocará de posição com [tex]a_1[/tex]: isso pode ser feito de [tex]4[/tex] maneiras;
- Em seguida, arrumar os outros três elementos, sem que nenhum fique na posição inicial, o que pode ser feito de [tex]D_{3}[/tex] maneiras.
- Para formar uma desordem do grupo [tex]B[/tex], devemos tomar também duas decisões:
- Escolher o elemento da sequência que ficará na primeira posição e isso pode ser feito de [tex]4[/tex] maneiras, já que o elemento [tex]a_1[/tex] não poderá ocupar essa posição.
- Em seguida, arrumar os outros quatro elementos, sem que nenhum fique na posição inicial e o elemento [tex]a_1[/tex] não fique na posição original do elemento que ocupará agora a primeira posição: isso pode ser feito de [tex]D_{4}[/tex] maneiras.
Assim, pelo Princípio Fundamental da Contagem, temos [tex]\boxed{4 \cdot D_{3}}[/tex] desordens distintas no conjunto [tex]A\,.[/tex]
Novamente, pelo Princípio Fundamental da Contagem, temos [tex]\boxed{4 \cdot D_{4}}[/tex] elementos no conjunto [tex]B[/tex].
Portanto,
[tex]\qquad \qquad D_{5}=4 \cdot D_{3}+ 4 \cdot D_{4}[/tex]
[tex]\qquad \qquad D_{5}=4 \cdot (D_{3}+D_{4})[/tex]
[tex]\qquad \qquad D_{5}=4 \cdot (2+9)[/tex]
[tex]\qquad \qquad \fcolorbox{black}{#B2EDE0}{$D_{5}=44$}\,.[/tex]
Particularmente, podemos repetir esse mesmo raciocínio para uma sequência de [tex]n[/tex] elementos [tex]\left(a_1, a_2, a_3, \cdots , a_n\right)[/tex], com [tex]n\gt 5[/tex], e obter que o valor de [tex]D_n[/tex] é dado por:
[tex]D_{n}=(n-1) \cdot D_{n-2}+ (n-1) \cdot D_{n-1}[/tex]
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)$}\,[/tex].
Observe que para obter [tex]D_n[/tex], você precisa recorrer aos valores de [tex]D_{n-1}[/tex] e [tex]D_{n-2}[/tex], ou seja, você precisa dos dois últimos valores imediatamente calculados. Por essa razão, essa fórmula do [tex]D_n[/tex] é um exemplo do que chamamos de "Fórmula de Recorrência". (Para a nossa discussão, não será necessário que você saiba trabalhar com fórmulas de recorrência, mas se você se interessar pelo assunto, temos uma sala sobre Recorrências no nosso Blog. Dê uma passadinha por lá, mais tarde!)
Por enquanto, vamos apenas aplicar essas fórmulas para ampliar a nossa sequência de valores de [tex]D_n[/tex] e na solução dos problemas que serão apresentados:
[tex]D_{1}=0[/tex]
[tex]D_{2}=1[/tex]
[tex]D_{3}=2[/tex]
[tex]D_{4}=9[/tex]
[tex]D_{5}=44[/tex]
[tex]D_{6}=5\times \left(9+44\right)=265[/tex]
[tex]D_{7}=6\times \left(44+265\right)=1854[/tex]
[tex]D_{8}=7\times \left(265+1854\right)=14\,833[/tex]
[tex]\qquad \qquad \vdots[/tex]
Se você sabe o que é fatorial de um número natural, há também uma fórmula fechada para a obtenção do número de Desarranjos de sequências ordenadas com [tex]n[/tex] elementos:
[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=n! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dots + \dfrac{(-1)^{n}}{n!}\right]$}[/tex]
Assim, por exemplo,
[tex]\qquad \qquad D_{4}=4! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dfrac{1}{4!}\right]\\
\qquad \qquad D_{4}=24 \cdot\left[1-1+\dfrac{1}{2}-\dfrac{1}{6}+\dfrac{1}{24}\right]=9.[/tex]
A discussão sobre a obtenção dessa fórmula não será feita neste momento; mas se você quer utilizá-la e não sabe ou não se lembra dos fatoriais, clique no botão abaixo.
Para amadurecer o conceito e as fórmulas de Desarranjo,
veja mais dois exemplos desse tipo de problema.
Quantos são os anagramas da palavra CLUBE, nos quais nenhuma das letras está na sua posição original?
Professores que utilizam quadro branco contam cada vez mais com novas possibilidades de cores a utilizar. Isto facilita principalmente àqueles que lecionam geometria ou mesmo os que desejam colorir pelo simples fato da diversidade. O professor Cleber, muito caprichoso, comprou as [tex]6[/tex] canetas abaixo (preta, azul, verde, alaranjada, vermelha e roxa).
Imagem extraída de http://comercialdantas.com.br/escolar-e-escritorio/pinceis-e-marcadores/marcador-para-quadro-branco-pilot.html
Utilizando todas elas na apresentação de certo conteúdo, ele confundiu-se e errou ao colocar a tampa de todas elas, de forma que nenhuma delas ficou com a tampa correta, correspondente à sua cor.
De quantas maneiras distintas essa confusão pode ocorrer?
Voltando ao problema inicial…
Voltemos ao problema do "amigo-secreto":
- De quantas maneiras as pessoas de um grupo [tex]n[/tex] amigos podem sortear seus amigos ocultos, sem que uma pessoa sorteie a si mesma?
Se denotarmos o grupo de pessoas participantes da brincadeira por [tex]\left(p_1, p_2, \cdots , p_n \right)[/tex], o problema equivale a determinar o número de desarranjos de uma sequência com [tex]n[/tex] elementos e, portanto, podemos responder sem titubear que esse número é [tex]\boxed{D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)}\,[/tex].
Permutações Caóticas
Você deve estar se perguntando…
|
Cadê as tais Permutações Caóticas??? |
 |
Permutação Caótica é a mesma coisa que Desarranjo!
O nome Permutação Caótica é utilizado quando a ferramenta matemática que denominamos Desarranjo é apresentada dentro do estudo das Permutações, já que os desarranjos são casos particulares de permutação.
Permutações e Combinações são ferramentas matemáticas que permitem que consigamos determinar o número de elementos de conjuntos formados a partir de determinadas regras, sem que seja necessário contarmos um a um esses elementos.
Particularmente, as Permutações são utilizadas em situações em que temos uma sequência ordenada com uma quantidade finita de elementos (que podem inclusive aparecer repetidamente) e precisamos saber de quantas maneiras podemos misturar TODOS esses elementos de modo a formar novas sequências, duas a duas distintas.
Dependendo das regras utilizadas para formar essas sequências, temos os diversos tipos de Permutação existentes. Ao misturar os elementos de uma sequência ordenada, as sequências obtidas nas quais nenhum elemento ocupa a sua posição original são chamadas de “Permutações Caóticas” ou Desarranjos.
 |
Se você quiser ver outros exemplos ou explorar um pouco mais o assunto, conheça a Sala de Estudo sobre Permutação Caótica do nosso Blog. |
Equipe COM – OBMEP
[1] A Matemática do Ensino Médio (volume 2): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[2] A Matemática do Ensino Médio (volume 4): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[3] Matemática Discreta: Coleção Profmat – Augusto César Morgado; Paulo Cesar Pinto Carvalho.
[4] Análise Combinatória e Probabilidade – Augusto César Morgado; João Bosco Pitombeira de Carvalho; Paulo Cesar Pinto Carvalho e Pedro Fernandez.
[5] Notas de aulas do professor Cleber Gouvêa Fernandes (IFRJ).