Amigo secreto e matemática

Para boa parte dos brasileiros, fim de ano é sinônimo de confraternização, festas, presentes, aniversário de Cristo, ..., Papai Noel, peru, Réveillon e, claro, amigo secreto (ou amigo oculto, dependendo da sua região). Para nós qualquer época do ano é sinônimo de matemática. A seguir, vamos então explorar um pouco a relação desta brincadeira com a matemática. Mais especificamente, vamos calcular a surpreendente probabilidade de que ninguém retire o seu próprio nome no amigo secreto.

O amigo secreto

Imagino que todo mundo já conheça e já tenha participado de um amigo secreto, mas vamos lá:

Cada uma de pessoas escreve seu nome num pedaço de papel e o deposita em algum recipiente. Após embaralhar todos estes pedacinhos de papel, cada pessoa retira (em alguma ordem pré-estabelecida), um desses papéis que contém o nome de alguma das pessoas. A pessoa que retirou o papel não pode contar o nome de quem tirou. Sendo assim, estas pessoas combinam um dia e, nesta data, a pessoa tem que dar um presente para a pessoa retirada no papel.

Problema: e se alguém tira o papel com o seu próprio nome? Então o ritual teria que ser feito novamente, até que nenhuma pessoa tire seu próprio nome.

A probabilidade de alguma determinada pessoa tirar o seu próprio nome é fácil: . Mas qual seria a probabilidade de pelo menos uma pessoa dentre as tirar seu próprio nome? Ou, inversamente, qual seria a probabilidade de ninguém tirar seu próprio nome? Esta probabilidade está longe de ser trivial. O objetivo deste post é calculá-la.

Permutações Caóticas

A primeira coisa a se fazer é interpretar o "amigo secreto" matematicamente. Observe que, para cada pessoa , é associada uma uma pessoa . Denote . Note também que cada pessoa escreveu seu nome num papel, logo sempre existe uma (única) pessoa que irá retirar este papel, possivelmente você mesmo. Este bla bla bla todo quer dizer que é uma permutação de elementos (isto é, uma função bijetora de em ).

Obs.: O conjunto é meramente ilustrativo. Na prática, também temos permutações entre conjuntos e (isto é, conjuntos de elementos, ou símbolos, quaisquer). Mas temos uma associação óbvia entre estes conjuntos e e, portanto, acabamos por definir uma permutação como sendo uma bijeção de apenas por comodidade.

Para satisfazermos a condição de que ninguém deve tirar seu próprio nome, devemos impor , para todo . Em jargão matemático, queremos que não tenha nenhum ponto fixo.

Sendo assim, um jogo de amigo secreto válido (isto é, ninguém tira seu próprio nome) entre pessoas é nada mais do que uma permutação de elementos sem nenhum ponto fixo. Permutações sem pontos fixos são importantes, por isso têm um nome especial, são chamadas de permutações caóticas, ou desarranjos. Como não gosto deste último nome, daqui em diante utilizarei o termo permutação caótica para designar uma permutação sem ponto fixo.

Uma outra maneira de se definir uma permutação caótica é dizendo que uma permutação caótica de elementos é uma bijeção entre e de forma que cada elemento do domínio tem uma imagem "proibida'' . Em breve, também iremos utilizar esta interpretação.

Vamos então formular um novo problema que praticamente resolverá a probabilidade que estávamos procurando no início:

Quantas permutações caóticas de elementos existem?

Na seção seguinte, resolveremos este novo problema e, como corolário, calcularemos a probabilidade proposta.

Solução

Defina como o número de permutações caóticas de elementos, (exercício: calcule alguns valores pequenos para ). Vamos encontrar uma fórmula recursiva para .

Dada uma uma permutação caótica de elementos , existem valores possíveis para . Suponha então , para algum . Agora iremos analisar o comportamento de no elemento .

• Se , então troca os elementos e entre si e se comporta como uma permutação caótica de elementos em . Logo, se , temos possibilidades para .
  
• Se , então agora se comporta como uma permutação caótica de elementos da seguinte forma: temos uma bijeção entre e e para cada elemento do domínio temos uma associação proibida, mais especificamente, os números são proibidos de ir em e é proibido de ir em . Se isto ficou confuso, renomeie os conjuntos anteriores, fazendo corresponder: , , observe que estamos identificando com [*].

Das observações feitas acima (e pelo Princípio Fundamental da Contagem), temos então nossa recursão:

Agora vamos manipular esta expressão e deixá-la num formato mais conveniente.

Agora é fácil ver, por indução, que

Como e , temos uma nova fórmula

A partir daqui, não há saída melhor do que observar o comportamento desta recursão, adivinhar uma fórmula e prová-la por indução. Mas isto é muito fácil se fizermos um pequeno truque: dividir ambos os lados por .

Então é claro que (e pode ser mostrado por indução)

Logo, temos a seguinte fórmula fechada para

Exercício: mostre por indução.

Há ainda uma outra forma de calcular esta fórmula que utiliza o Princípio da Inclusão e Exclusão, e pode ser encontrada (em inglês) aqui.

Agora podemos finalmente calcular a probabilidade de pelo menos uma pessoa retirar seu próprio nome no amigo secreto. O número total de possibilidades para as retiradas do papel é nada mais do que a quantidade de todas as permutações possíveis de elementos, ou seja, . O evento de ninguém tirar seu próprio nome é nada mais do que exigir que a permutação não possua ponto fixo, ou seja, a permutação deve ser caótica. Logo, o número de possibilidades para tal evento é . Assim, a probabilidade de isto acontecer é dada por

O leitor mais atento já deve ter percebido o quão surpreendente é esta probabilidade. Vejamos primeiro uma tabela com a probabilidade calculada para alguns valores de , com 7 casas:

Ou seja, conforme aumenta, a probabilidade está se aproximando de uma constante! Isto quer dizer que, na prática, a probabilidade de ninguém tirar seu próprio nome num amigo secreto com 10 ou com 100 pessoas é quase a mesma!

Ora, mas que constante mística seria essa? Se você está acostumado com expansões de Taylor a resposta é óbvia. A expansão da função é

Logo, quando , temos

Em outras palavras, a constante mágica é .

Comentários finais

É interessante observar que nos deparamos com esta probabilidade muito mais comumente do que se pensa. Por exemplo, se você pegar dois baralhos e começar a virar as cartas de cada um desses baralhos ao mesmo tempo, a probabilidade de não sair nenhuma carta repetida é também próxima de . A página da Wikipédia em inglês fornece outros exemplos e alguns links relacionados.

A solução deduzida aqui é devida a Euler, mas meus agradecimentos vão para o meu amigo Robson, que já está careca de saber combinatória e me mostrou isto pela primeira vez.

Até.

Notas

[*] Se você ainda não entendeu, não desista. Tentei explicar da melhor maneira possível, mas confesso que isto é um tanto confuso. O fato é que isto é verdade e você tem que encontrar um jeito de se convencer disso.