José Paulo Q. Carneiro
UFRJ, Rio de Janeiro, RJ

Pouco antes das festas do último fim de ano, eu estava reunido com um grupo de familiares, que resolveu planejar a célebre brincadeira do "amigo oculto". Éramos 9 pessoas. Foi escrito o nome de cada pessoa em um papelzinho, e procedeu-se ao sorteio, para determinar quem iria dar presente a quem. Feito o sorteio, logo apareceu alguém que tirou a si mesmo. Sendo contra as regras da brincadeira que alguém presenteie a si mesmo, e para preservar o sigilo, tivemos que proceder a outro sorteio. No segundo sorteio, o mesmo fenômeno ocorreu, dessa vez com outra pessoa. Uma das pessoas presentes — um analista de sistemas — voltou-se para mim e perguntou: "Você, que é matemático, diga: vai ficar acontecendo isso a vida toda? Qual a probabilidade de isso ocorrer?".

Na realidade, essa é uma ocorrência de um célebre problema de Combinatória, o das chamadas permutações caóticas.

Cada sorteio define uma função f do conjunto das 9 pessoas em si mesmo. f(x) = y significa que x deve presentear y. Como duas pessoas diferentes não podem tirar o mesmo amigo oculto (o sorteio é feito sem reposição), e todas as 9 pessoas serão presenteadas,  f é uma bijeção do conjunto A das 9 pessoas sobre si mesmo, ou seja, uma permutação desse conjunto. Alguém será amigo oculto de si mesmo quando existir em A um certo x tal que f(x)=x. Na nomenclatura usual de funções, um tal x é chamado ponto fixo de  f. O problema agora consiste em determinar, dentre o total das 9! = 362880 permutações dos elementos de A, quantas são as que têm ponto fixo — correspondentes aos sorteios fracassados —  e quantas não têm ponto fixo — correspondentes aos sorteios que deram certo. Pode parecer estranho que justamente os casos que aqui "dão certo" é que são chamados, na nomenclatura clássica, de permutações caóticas. 0 motivo é que essa nomenclatura se prende à interpretação de permutações como "arrumações" dos elementos 1, . . ., 9 nos lugares de 1 a 9; uma permutação caótica é então uma permutação em que todo o mundo está fora de seu lugar "natural".

Antes de resolver o problema, vamos introduzir uma forma de representar permutações. Adotando o clássico símbolo a b para designar que f(a) = b, e numerando as pessoas de 1 a 9, uma possível permutação é, por exemplo:

1 8   2 1   3 3   4 9   5 7   6 6   7 4   8 2   9 5

Observe que podemos colocar essas informações na seguinte or­dem:

l 8 2 l         3 3         4 9 5 7 4         6 6

Note que as pessoas 1; 8; 2; 1 formam, nessa ordem, um ciclo: 1 presenteia 8, que presenteia 2, que presenteia 1. Representaremos esse ciclo por (182). O mesmo ciclo poderia ser representado também por (821) ou (218) (certo?), mas não por (128), que significaria: 1 2 8 1, que é diferente. Situação análoga ocorre com os elementos 4; 9; 5; 7, que formam o ciclo (4957). Os pontos fixos 3 e 6 podem ser considerados como ciclos de tamanho 1. Desse modo, essa permutação pode ser representada por: (182) (3) (4957) (6). Repare que, se trocarmos os ciclos de lugar, nada muda nas informações, de modo que a mesma permutação poderia ser representada, por exemplo, por (4957) (6) (3) (182). Já trocar a ordem das pessoas dentro dos ciclos pode alterar ou não a permutação, como vimos.

Antes de passar adiante, o leitor deve, se achar necessário, escrever algumas permutações nessa notação. Pode ser útil, aliás, representar graficamente as permutações através de seus ciclos. No exemplo citado, teríamos:

Fica claro agora que, quando procuramos as permutações que não possuem pontos fixos, estamos procurando quais as permutações que não apresentam ciclos de tamanho 1.

Para adquirir uma familiaridade com o problema, comecemos por examinar como seria o problema com números menores. Chamando de n o número de pessoas, e de K_n o número de permutações do conjunto dessas pessoas, que não têm elementos fixos, então a probabilidade de que o sorteio "dê certo" será:   p_n = K_n /n!.

Para n = 1, a única permutação que existe é: 1 1, ou, na nossa notação: (1), a qual tem ponto fixo. É claro então que  K₁ = 0  e  p₁ = 0.

Para n = 2, as duas permutações são: (1) (2) e (12). Só a segunda é caótica; portanto:   K₂ = 1  e  p₂ = 1/2.

Para n = 3, existem 6 permutações: (1)(2)(3), (1)(23), (2) (13), (3) (12), (123) e (132). Dessas, só as duas últimas não têm ciclos de tamanho 1, isto é,  não têm pontos  fixos. Logo, K3 = 2 e  p₃ = 1/3.

É claro que não podemos contar dessa maneira para o caso n = 9, com um total de mais de 300 mil permutações. Vamos então fazer um raciocínio mais sutil, para esse caso. Imaginemos todas as permutações caóticas das 9 pessoas. Fixemos a atenção na pessoa de número 9. Em qualquer das 9! permutações, essa pessoa tem que estar em algum ciclo de tamanho maior que 1 (lembre-se que não há ponto fixo numa permutação caótica!). Chamemos então de D₉ o número de permutações caóticas (das 9 pessoas) em que a pessoa 9 está num ciclo de tamanho 2, e de ,B₉ o número de permutações caóticas (das 9 pessoas) em que a pessoa 9 está num ciclo de tamanho maior que 2. E claro que   K₉ = B₉ + D₉.

Se tomarmos uma permutação caótica em que 9 esteja num ciclo de tamanho maior que 2 (por exemplo, (15) (3246) (798)) e "suprimirmos" o 9, obteremos uma permutação caótica das 8 pessoas restantes (no exemplo anterior, obteríamos: (15) (3246) (78)); por outro lado, o caminho inverso — ou seja, "inserir" o 9 nesta permutação caótica das 8 primeiras pessoas, para obter uma permutação caótica das 9 originais — pode ser feito de 8 maneiras diferentes, como vemos no exemplo dado: (195)(3246)(78), ou (159)(3246)(78), ou (15)(39246)(78), ou   (15)(32946)(78),   ou   (15)(32496)(78),   ou  (15)(32469)(78), ou (15)(3246)(798), ou (15)(3246)(789)). Na realidade, o processo descrito nesse "caminho inverso" consiste em substituir cada flecha a b por a 9 b. No exemplo, fizemos isso, sucessivamente, com as flechas 1 5, 5 1, 3 2, 2 4, 4 6, 6 —> 3, 7 8, 8   7, que são as oito flechas da permutação. Portanto, a conclusão é que cada permutação caótica de 8 pessoas gera, por esse processo, 8 permutações caóticas de 9 pessoas nas quais a pessoa 9 está num ciclo de tamanho maior que 2, ou seja: B₉ = 8K₈.

Se tomarmos agora uma permutação caótica em que 9 esteja num ciclo de tamanho igual a 2 (por exemplo, (178) (3426) (59)) e "suprimirmos" o 9, obteremos não uma permutação caótica das 8 pessoas restantes, e sim uma permutação das 8 pessoas com um único ponto fixo (no exemplo anterior, obteríamos: (178) (3426) (5)). Essa pode ser olhada como um ponto fixo (no caso, o 5) justaposto a uma permutação caótica das outras 7 pessoas. Como existem 8 candidatos a serem o ponto fixo, conclui-se que cada permutação caótica de 7 pessoas gerará, pelo processo de "acrescentar" o 9 ao ponto fixo, 8 permutações caóticas de 9 pessoas nas quais 9 está num ciclo de tamanho 2, ou seja:   B₉ = 8K₇.

Como K₉ = B₉ + D₉, segue que: K₉ = 8K₈ + 8K₇.

O leitor pode agora repetir o mesmo raciocínio para n em vez de 9, para concluir que: K_n = (n 1)K_n-1 + (n l)K_n-2. Dividindo por n! e simplificando, passa-se às probabilidades que nos interessam, obtendo:

Essa é uma fórmula, de recorrência, que permite calcular  p_n, uma vez que já saibamos as probabilidades anteriores   p_n-1  e  p_n-2 . Por exemplo:

Continuando, encontram-se:

e assim por diante.

Para obter uma fórmula geral, observemos que a fórmula (*) pode ser escrita como: p_n  p_n-1 = (1/n)(. p_n-1 p_n-2), ou ainda, chamando p_n  p_n-1 de d_n , como: d_n = (l / n)d_n-1. Observando ainda que d₂ = p₂ p₁ = 1/2 0 = 1/2, tem-se, sucessivamente:

Por fim, a relação  p_n  p_n-1 = d_n  acarreta:

Somando-se termo a termo e simplificando, obtém-se, finalmente, a fórmula geral que resolve o problema:

Observando a tabela de valores de p_n,  o leitor vai reparar que esses valores crescem (cada vez menos) quando   n   passa de ímpar para par, e diminuem (cada vez menos) quando n passa de par para ímpar, sugerindo que p_n deva tender a se aproximar de um certo valor (entre 0,36667 e 0,36806), ora por excesso, ora por falta. Isso de fato é verdade. Esse valor é l /e, em que e 2,71828 é a célebre base dos logaritmos naturais (ver RPM 25, p.6). Se o leitor tiver acesso a uma calculadora com a tecla e^x, poderá verificar que l / e = e^-1 0,36788. A justificativa desse fato pode ser feita através da fórmula de Taylor para a função exponencial, estudada em Cálculo Diferencial, segundo a qual:   e^x = 1 + (x / l!) + (x² / 2!) + ^{. . .}.

Em suma, pode-se dizer que a probabilidade de que o sorteio do amigo oculto dê certo oscila em torno de aproximadamente 37% (conseqüentemente, 63% de não dar certo), estando já bem perto desse valor a partir de 5 pessoas.

Desejamos concluir com duas observações:

1.   Na referência [2], encontra-se uma outra resolução do problema das permutações caóticas, baseada na fórmula que dá o número de elementos de uma união de conjuntos em termos dos números de elementos de cada conjunto e de suas interseções.   Apresentamos essa dedução alternativa (sugerida em um exercício de [1]), por achá-la também instrutiva, já que utiliza métodos que podem parecer à primeira vista artificiosos,  mas que na realidade ocorrem com freqüência, como fórmulas de recorrência, passagem a diferenças, etc.

2.  O estudo das permutações no curso secundário tem-se prendido demasiadamente ao simples cálculo envolvido em problemas de Análise Combinatória. Um problema como esse, do amigo oculto, pode servir para introduzir um estudo em que as permutações aparecem como funções, permitindo o estudo de pontos fixos, composição de permutações, etc.   Desse modo, estaremos abordando um terreno bastante atraente do ponto de vista didático (principalmente quando as permutações são olhadas em um gráfico de flechas, como foi sugerido aqui), e que possui diversos pontos em comum com alguns assuntos importantes, como o estudo dos determinantes (onde aparece o "sinal" de uma permutação) ou dos grupos, que começaram, historicamente como grupos de permutações (inicialmente chamadas de substituições).

Referências Bibliográficas

[1]   KEMENY, J.G. e outros. Introduction to Finite Mathematics Englewood Cliffs, N.J., Prentice-Hall, 1960.

[2]   MORGADO, A.C.O. e outros. Análise Combinatória, e Probabilidade. Rio de Janeiro, IMPA - VITAE,         1991.