Arquivo da tag: Amigo secreto

Amigo secreto

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:

hats2

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:

hats1

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:

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

\displaystyle = \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:

\displaystyle 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:

hat_check_graph

É 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.

Anúncios