O Quebra-Cabeça do Papai Noel Secreto

Você deve se lembrar que, no boletim informativo de 26 de outubro de 2023, escrevi sobre um programa de jogos que acontecia no navio, chamado "Deal or No Deal". Nesse jogo, cada jogador podia comprar cartões para ter a chance de jogar no palco. No entanto, cada cartão tinha a chance de ganhar prêmios de consolação. O funcionamento dos prêmios de consolação era o seguinte: cada cartão continha 20 malas com 20 prêmios em dinheiro diferentes, colocados aleatoriamente atrás das 20 caixas. As malas eram abertas levantando-se abas. O jogador ganhava de acordo com a quantidade de prêmios em seu cartão que correspondiam a uma mistura aleatória dos mesmos prêmios exibida em uma tela. Um problema não resolvido daquele boletim informativo era a probabilidade de qualquer número de acertos.

Esse problema é geralmente chamado de Amigo Secreto. O nome vem da brincadeira de Natal em que um grupo de pessoas, geralmente do mesmo escritório, sorteia um nome de um chapéu com todos os colegas para decidir quem receberá o presente. Um problema do jogo é que existe a possibilidade de o nome sorteado ser o seu próprio, o que não é nada divertido. Em média, isso acontece com pelo menos um jogador em cada escritório, independentemente do número de funcionários. Uma das perguntas que busco responder nesta newsletter é a probabilidade exata de ninguém sortear o próprio nome.

Na época em que escrevi o boletim informativo de 26 de outubro, eu não sabia exatamente como resolver o problema matemático, então usei a função de Poisson para fazer estimativas. No entanto, o problema tem me incomodado desde então. Sempre achei as estimativas intelectualmente insatisfatórias.

Primeiro, escrevi um programa de computador para percorrer todas as ordens possíveis de prêmios e contar o número de acertos em cada permutação. No entanto, com 13 malas, esse programa levou cerca de um dia para percorrer todas as 6.227.020.800 permutações. Com 20 malas, seriam 2.432.902.008.176.640.000 permutações, o que levaria cerca de um milhão de anos para ser concluído.

Em segundo lugar, fui ao Excel e tentei resolver o problema recursivamente. Foi muito mais fácil do que eu esperava. Eu deveria ter feito assim desde o início.O restante desta newsletter explicará a lógica por trás dessa abordagem.

Presumo que o leitor esteja familiarizado com a função COMBIN(x,y) do Excel, que indica o número de maneiras de escolher y itens dentre x. A equação exata é x!/(y!*(xy)!).

Vamos começar com alguns casos óbvios.

1. 1. Com um único Papai Noel, é óbvio que ele terá seu próprio nome.
2. 2. Com dois Papais Noéis, há 50% de chance de cada um receber seu próprio nome ou o nome do outro.
3. 3. Com três Papais Noéis, há 1 maneira de cada um ter seu próprio nome. Não há maneiras de duas pessoas terem seus próprios nomes, porque se isso acontecesse, a última pessoa também teria seu nome sorteado, já que seria o único que sobraria. Há 3 maneiras de uma pessoa ter seu próprio nome, uma para cada uma das 3 pessoas, e 1 maneira de as outras duas terem os nomes uma da outra. 3 * 1 = 1. Há um total de 3! = 6 maneiras possíveis de ordenar os 3 nomes. O número de maneiras de 0 pessoas terem seus próprios nomes é o que sobrar: 6 - 1 - 3 = 2.

Eis o ponto em que nos encontramos até agora:

Partidas	3 Papais Noéis	2 Papais Noéis	1 Papai Noel
3	1
2	0	1
1	3	0	1
0	2	1	0
Total	6	2	1

Em seguida, vamos passar para 4 Papais Noéis.

4 partidas: Sempre há uma maneira de todos conseguirem seu próprio nome.

3 combinações: É sempre impossível que todos tirem seus nomes, exceto uma pessoa. Depois que todos, menos uma pessoa, tiverem seus nomes combinados, restará apenas uma pessoa e um nome, que deverão ser iguais.

2 combinações: Existem combin(4,2)=6 maneiras de escolher 2 pessoas dentre 4 para combinar. Com as outras 2, existe 1 maneira de elas não combinarem, sorteando o nome uma da outra.

1 combinação: Existem 4 maneiras de escolher o Papai Noel que combina consigo mesmo. Podemos ver no caso dos 3 Papais Noéis que existem 2 maneiras pelas quais os outros 3 Papais Noéis não combinam, o que teria que acontecer. Portanto, o número de combinações para 1 combinação é 4 * 2 = 8.

0 correspondências: Novamente, subtraímos todas as outras possibilidades do total de permutações. 4! – 1 – 6 – 8 = 24-15=9.

Agora estamos em:

Partidas	4 Papais Noéis	3 Papais Noéis	2 Papais Noéis	1 Papai Noel
4	1
3	0	1
2	6	0	1
1	8	3	0	1
0	9	2	1	0
Total	24	6	2	1

A seguir, vamos falar sobre 5 Papais Noéis.

5 combinações: Sempre há uma maneira de todos conseguirem seu próprio nome.

4 partidas: Impossível, pelas razões expostas no caso dos 4 Papais Noéis.

3 combinações: Existem combin(5,3)=10 maneiras de escolher 3 pessoas dentre 5 para combinar entre si. Existe 1 maneira de as outras duas pessoas conseguirem os nomes uma da outra. Portanto, existem 10 maneiras de se obterem 3 combinações.

2 combinações: Existem combin(5,2)=10 maneiras de escolher 2 pessoas dentre 5 para combinar. Com as outras 3, existem 2 maneiras de elas não combinarem, como podemos ver no caso dos 3 Papais Noéis. Portanto, existem 10*2=20 maneiras de 2 combinações.

1 combinação: Existem 5 maneiras de escolher o Papai Noel que combina consigo mesmo. Podemos ver, no caso dos 4 Papais Noéis, que existem 9 maneiras pelas quais os outros 4 Papais Noéis não combinam, o que teria que acontecer. Portanto, o número de combinações para 1 combinação é 5 * 9 = 45.

0 correspondências: Novamente, subtraímos todas as outras possibilidades do total de permutações. 5! – 1 – 0 – 10 – 20 – 45 = 44.

Agora estamos em:

Partidas	5 Papais Noéis	4 Papais Noéis	3 Papais Noéis	2 Papais Noéis	1 Papai Noel
5	1
4	0	1
3	10	0	1
2	20	6	0	1
1	45	8	3	0	1
0	44	9	2	1	0
Total	120	24	6	2	1

Seguindo a mesma lógica, obtemos a seguinte tabela para até 10 Papais Noéis.

Esteira.	10 Papais Noéis	9 Papais Noéis	8 Papais Noéis	7 Papais Noéis	6 Papais Noéis	5 Papais Noéis	4 Papais Noéis	3 Papais Noéis	2 Papais Noéis	1 Papai Noel
10	1
9	0	1
8	45	0	1
7	240	36	0	1
6	1890	168	28	0	1
5	11088	1134	112	21	0	1
4	55650	5544	630	70	15	0	1
3	222480	22260	2464	315	40	10	0	1
2	667485	66744	7420	924	135	20	6	0	1
1	1334960	133497	14832	1855	264	45	8	3	0	1
0	1334961	133496	14833	1854	265	44	9	2	1	0
Total	3628800	362880	40320	5040	720	120	24	6	2	1

Note que o número de permutações para 0 e 1 correspondências está sempre dentro de uma unidade uma da outra. O total de 0 correspondências é uma a mais do que 1 correspondência para um número par de Papais Noéis e uma a menos para um número ímpar. Se aceitarmos que este é sempre o caso, o que de fato é, podemos determinar rapidamente o número de 0 correspondências para 11 ou mais Papais Noéis, da seguinte forma.

11 Papais Noéis: Para uma combinação, existem 11 Papais Noéis que podem ser o par e 133.496 maneiras de os outros 10 não combinarem, considerando o caso dos 10 Papais Noéis. O número de permutações para 1 combinação é, portanto, 11 * 133.496 = 14.684.571. Como 11 é ímpar, o número de permutações para 0 combinações é um a menos, ou seja, 14.684.571 – 1 = 14.684.570.

12 Papais Noéis: Para uma combinação, existem 12 Papais Noéis que podem ser o par e 14.684.570 maneiras de os outros 11 não combinarem, considerando o caso dos 11 Papais Noéis. O número de permutações para 1 combinação é, portanto, 12 * 14.684.570 = 176.214.840. Como 12 é par, o número de permutações para 0 combinações é um a mais, ou seja, 176.214.840 + 1 = 176.214.841.

Seguindo a mesma lógica, aqui está o número de permutações para 0 correspondências para 1 a 20 Papais Noéis, incluindo o total de permutações e a probabilidade.

Papais Noéis	0 partidas	Permutações totais	Probabilidade
20	895.014.631.192.902.000	2.432.902.008.176.640.000	0,367879
19	44.750.731.559.645.100	121.645.100.408.832.000	0,367879
18	2.355.301.661.033.950	6.402.373.705.728.000	0,367879
17	130.850.092.279.664	355.687.428.096.000	0,367879
16	7.697.064.251.745	20.922.789.888.000	0,367879
15	481.066.515.734	1.307.674.368.000	0,367879
14	32.071.101.049	87.178.291.200	0,367879
13	2.290.792.932	6.227.020.800	0,367879
12	176.214.841	479.001.600	0,367879
11	14.684.570	39.916.800	0,367879
10	1.334.961	3.628.800	0,367879
9	133.496	362.880	0,367879
8	14.833	40.320	0,367882
7	1.854	5.040	0,367857
6	265	720	0,368056
5	44	120	0,366667
4	9	24	0,375000
3	2	6	0,333333
2	1	2	0,500000
1	0	1	0,000000

Observe como a probabilidade de 0 acertos se aproxima de 0,367879. Esse número lhe parece familiar? Deveria! É 1/e. Eu poderia escrever um livro inteiro sobre a estimativa de Poisson neste ponto, mas este boletim informativo já está muito longo. Para saber mais sobre isso, recomendo o livro "Sharp Sports Betting" de Stanford Wong, que explica como usar a função de Poisson para analisar apostas de proposição no Super Bowl.

Vamos voltar ao jogo Deal or No Deal, que é equivalente ao caso dos 20 Papais Noéis. Queremos saber o número de combinações possíveis entre 0 e 20.

O número de combinações para m correspondências entre 20 Papais Noéis é combin(20,m)*z(m), onde z(m) = número de combinações de zero correspondências para m Papais Noéis. A tabela a seguir usa esse método para encontrar o número de permutações para 0 a 20 correspondências com 20 Papais Noéis.

Partidas	Permutações	Probabilidade
20	1	0,000000
19	-	0,000000
18	190	0,000000
17	2.280	0,000000
16	43.605	0,000000
15	682.176	0,000000
14	10.271.400	0,000000
13	143.722.080	0,000000
12	1.868.513.010	0,000000
11	22.421.988.160	0,000000
10	246.642.054.516	0,000000
9	2.466.420.377.200	0,000001
8	22.197.783.520.770	0,000009
7	177.582.268.088.640	0,000073
6	1.243.075.876.659.240	0,000511
5	7.458.455.259.939.930	0,003066
4	37.292.276.299.704.500	0,015328
3	149.169.105.198.817.000	0,061313
2	447.507.315.596.451.000	0,183940
1	895.014.631.192.902.000	0,367879
0	895.014.631.192.902.000	0,367879
Total	2.432.902.008.176.640.000	1.000000

Se você comparar essas probabilidades com minhas estimativas de Poisson no boletim informativo de 26 de outubro de 2023, verá que todas concordam com as seis casas decimais fornecidas, o que demonstra a utilidade da função de Poisson e do número e.

Na próxima semana, pretendo aprofundar este tópico e apresentar uma fórmula geral para o número de permutações para qualquer número de Papais Noéis.

Escrito por: Michael Shackleford