Inspirado nesse clima de fim de ano, pensei em problemas que combinariam com essa última semana, e nenhum me pareceu mais adequado que o do amigo secreto. Todos já participamos de algo parecido, você é obrigado a tirar aleatoriamente um amigo que, via de regra, você mal conhece e deve comprar a ele um presente de até um determinado valor. É uma excelente oportunidade de ter que comprar coisas para quem não conhece e receber algo pífio de quem não gosta, porque presentes dependem do presenteado e, com pouca informação a respeito, esse processo tende a receber uma camiseta tamanho M que nunca na vida você usará.

Mas estes não são os únicos problemas do amigo secreto, há outros, que ao menos têm solução. Vou propor duas perguntas sobre a brincadeira, que envolvem pequenos defeitos que podem acontecer na seleção. Encontrar suas soluções é um interessante exercício de combnatória.

1) Qual a probabilidade de alguém tirar a si mesmo?

A primeira pergunta parece simples, mas tanto está longe de ser que ganhou um nome: o problema do chapeleiro. Suponha que o responsável por uma chapeleira perdeu o livro que dizia o dono de cada chapéu. Sem saída, ele distribui aleatoriamente os chapéus a quem vem buscar o seu. Qual a probabilidade de ele não ter acertado nenhum?

A resposta, apesar de bonita, não tem demonstração simples. Se peco na precisão, é por amor à clareza, vou tentar explicar o princípio desse cálculo. Você sabe que todas as permutações possíveis dos chapéus são $N!{}$, onde $N$ é o número de chapéus. Para saber a probabilidade de isso não acontecer, calculamos a chance de acontecer e tomamos a complementar. Para tal, basta somar as permutações que mantêm alguém constante (alguém recebeu o chapéu errado). Mas teremos um problema com isso, como veremos.

• Missão: calcular a chance de alguém ter recebido o próprio chapéu.

Sabemos que para calcular a chance de uma pessoa $i$ receber seu próprio chapéu basta somar quantas permutações de chapéu resultariam em ele terminando com seu chapéu na mão, e essa conta é simples, são $(N-1)!{}$ (com o dele fixo, calculamos as permutações dos demais). Mas não podemos apenas somar esse número para todos os $i$, pois estaremos contando muitas coisas duas vezes! Para entender, uso de exemplo os quatro irmão, G, B, R e Y, que decidiram ir a uma festa deixando seus chapéus na chapelaria. Eles chegaram da seguinte forma:

Há $4!=24$ configurações possíveis de distribuição de chapéus na saída, mas há apenas 6 configurações em que o verde recebe seu chapéu corretamente, vejamos:

Note que seria ingênuo apenas somar essas configurações para todos os irmãos e dizer que esse seria o número de permutações em que alguém recebe seu chapéu corretamente, pois notamos que poucas são as vezes em que apenas o verde recebe seu chapéu, ou seja, na conta do verde há vezes em que outros recebem seu chapéu e essas configurações serão contadas novamente na vez desses outros que receberam o chapéu correto. Felizmente isso pode ser corrigido, basta retirar o número de vezes em que dois recebem os chapéu correto.

Vamos colocar isso em uma linguagem matemática decente. Chamaremos $A_n$ o conjunto das permutações tais que o número $n$ recebe seu chapéu correto. Sabemos que $|A_n|=(N-1)!{}$. Mas o que queremos é $|\cup_n A_n|$, ou seja, o número total de permutações em que alguém é fixo.

Começamos calculando $\sum_n |A_n|$, mas provamos que contamos muita gente duas vezes. Pegamos esse resultado e subtraímos $\sum_{i<j} |A_{i,j}|$, onde $A_{i,j}$ é o conjunto das permutações que deixam $i$ e $j$ fixos, ou seja, eles recebem o chapéu correto.

Agora sofremos de outro mal, o remédio causou um novo sintoma. Ao excluirmos todos os que possuem dois fixos, excluímos duas vezes aqueles que possuem três fixos, e assim por diante, pois eles foram contados mais de uma vez nessa subtração. Isso não é problema, basta colocarmos de volta esses elementos, somando ao resultado o fator $\sum_{i<j<k} |A_{i,j,k}|$. O problema é que nessa soma contamos duas vezes os que possuem quatro fixos.

Deu para entender o mecanismo. Felizmente, como há um número finito de chapéus, ele algum dia terminará. E sabemos que o número de permutações possíveis com $n$ chapéus fixos é $(N-n)!{}$, isso nos permitirá calcular a soma total. Mas precisamos também lembrar que ao calcularmos $\sum_{i<j<k}|A_{i,j,k}|$, por exemplo, temos que somar $(N-3)!{}$ um número de vezes equivalente ao número de configurações possíveis na escolha de $i,j,k$, ou seja, um número ${N\choose 3}$ de vezes. Calculando ${N\choose 3}(N-3)!{}$, abrindo a fórmula binomial, nos resta apenas um fator, nesse caso, de $\frac{N!}{3!}$. É fácil deduzir que com os demais será a mesma coisa:

\[|\cup_n A_n|=\sum_n|A_n|-\sum_{i<j}|A_{i,j}|+\sum_{i<j<k}|A_{i,j,k}|+\ldots\]

\[= \frac{N!}{1!}-\frac{N!}{2!}+\frac{N!}{3!}+\ldots = N!\sum_{j=1}^{N-1} (-1)^{j+1}\frac{1}{j!}$

Esse é o número total de configurações em que alguém recebe seu chapéu corretamente. Para descobrir a chance de alguém receber o chapéu, basta dividir esse valor pelo número total de configurações, ou seja, $N!{}$. Concluímos aquela missão estabelecida acima, mas queremos a chance do complementar acontecendo, e para encontrar a probabilidade de ninguém ter o chapéu correto basta tomar 1 e subtrair esse valor calculado. Teremos:

$P(N)=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}+\ldots +(-1)^N\frac{1}{N!}$

E essa é a probabilidade, no amigo secreto, de ninguém tirar a si mesmo:

É fácil perceber que essa soma tende rapidamente a $\frac{1}{e}$, pois nosso resultado são exatamente as somas parciais da série de Taylor de $\frac{1}{e}$, e é interessante perceber como esse valor já é quase exato já a partir de cinco participantes, a convergência do fatorial sempre impressiona. Como toda boa série de Taylor, o erro é da ordem do último termo somado, então é natural que a partir de 5 participantes a diferença entre essa probabilidade e $ \frac{1}{e}$ seja menor que 1/120. É notável também o fato de, com apenas um participante, a chance ser zero de ninguém tirar a si mesmo, o que era, pelo bom senso, esperado.

O resultado é interessante também por outro motivo. Se aumentamos o número de participantes, a chance de uma pessoa escolhida tirar a si própria é cada vez menor, mas o número de pessoas que podem tirar a si mesmas aumenta, a resposta de “para onde vai a probabilidade” não é trivial e é bem interessante que nenhum desses elementos domine o outro, ou seja, a probabilidade não vai nem para zero, nem para um, mas para um valor intermediário e longe de ser evidente.

2) Qual a chance da brincadeira do amigo secreto não para no meio, ou seja, não “fechar o ciclo” antes de terminar e alguém ser obrigado a recomeçar o jogo?

Essa resposta é mais simples e possui menos imagens. Começamos por um participante qualquer. Para que o jogo não pare, ele não pode tirar a si mesmo, sobram $N-1$ opções. Ao tirar algum deles, essa próxima pessoa não pode tirar nem ela mesma, nem o primeiro, então sobram apenas $N-2$ opções a ela. Assim sucessivamente, é fácil ver que o número de ciclos possíveis que não serão interrompidos será de $(N-1)!{}$. Naturalmente, basta apenas dividir pelo número total de permutações, $N!{}$, para ter a probabilidade de isso acontecer, e ela é $\frac{1}{N}$. Como esperado, quanto maior o grupo de pessoas, mas difícil é obter uma configuração que forneça um jogo sem interrupções.

Depois desse post de combinatória um pouco árido, termino desejando a vocês um excelente ano novo, boas férias e todas as permutações possíveis daqueles votos de fim de ano que não canso de lhes desejar, mas que cansaria de escrever.