Questão 81. Oito amigos brincam entre si de amigo-secreto (ou amigo-oculto). Cada nome é escrito em um pedaço de papel, que é colocado em uma urna, e cada participante retira um deles ao acaso. De quantos modos nenhum dos colegas pode ter retirado o seu próprio nome?

Passo 1

O enunciado dá as seguintes informações e pede isto:
  • 8 amigos; cada nome é escrito num papel, os papéis vão para uma urna e cada participante retira um papel ao acaso (ou seja, consideram-se todas as atribuições possíveis dos 8 papéis aos 8 participantes).
  • Pergunta: de quantos modos nenhum dos colegas pode ter retirado o seu próprio nome? (ou seja, contar as atribuições em que ninguém recebe o próprio nome).

Passo 2

Vamos entender o que precisamos contar (sem resolver ainda). Cada maneira de distribuir os papéis corresponde a uma permutação dos 8 nomes. Entre todas as permutações de 8 elementos, queremos apenas aquelas que não deixam nenhum elemento no seu lugar original (nenhum amigo recebe seu próprio nome). Essas permutações são chamadas de permutações sem pontos fixos. Denotarei por !8 o número de tais permutações quando há 8 pessoas. Nosso objetivo é calcular !8.

Passo 3

Estratégia principal (inclusão-exclusão): é mais fácil contar o total de permutações e subtrair as que têm pelo menos uma pessoa tirando o próprio nome. Seja A_i o conjunto de permutações em que a pessoa i tira o próprio nome. Pelo princípio da inclusão-exclusão, o número de permutações com nenhum ponto fixo é
!8 = 8! - \sum_{i}\lvert A_i\rvert + \sum_{i<j}\lvert A_i\cap A_j\rvert - \sum_{i<j<k}\lvert A_i\cap A_j\cap A_k\rvert + \cdots + (-1)^8 \lvert A_1\cap\cdots\cap A_8\rvert.
Agora vamos interpretar cada termo combinatoriamente.

Passo 4

Contagem dos termos: se fixarmos exatamente k pessoas para que tirem o próprio nome (um conjunto qualquer de k pessoas), então o resto dos 8-k nomes pode ser permutado livremente entre os 8-k participantes restantes, dando (8-k)! permutações. O número de escolhas do conjunto de k pessoas é \binom{8}{k}. Portanto o termo correspondente na inclusão-exclusão é (-1)^k \binom{8}{k}(8-k)!. Assim
!8 = \sum_{k=0}^{8} (-1)^k \binom{8}{k} (8-k)!.
Agora simplificamos cada termo: \binom{8}{k}(8-k)! = \dfrac{8!}{k!}. Logo
!8 = 8! \sum_{k=0}^{8} \frac{(-1)^k}{k!}.
Essa é a fórmula padrão por inclusão-exclusão que vamos calcular explicitamente.

Passo 5

Cálculo direto da soma em frações com denominador 8! (para obter o resultado inteiro sem usar calculadora). Primeiro note que 8! = 40320. Escrevemos cada \dfrac{(-1)^k}{k!} com denominador 40320:
\begin{aligned} 1 &= \dfrac{40320}{40320},\\\\ - \dfrac{1}{1!} &= -\dfrac{40320}{40320},\\\ \dfrac{1}{2!} &= \dfrac{20160}{40320},\\\\ - \dfrac{1}{3!} &= -\dfrac{6720}{40320},\\\ \dfrac{1}{4!} &= \dfrac{1680}{40320},\\\\ - \dfrac{1}{5!} &= -\dfrac{336}{40320},\\\ \dfrac{1}{6!} &= \dfrac{56}{40320},\\\\ - \dfrac{1}{7!} &= -\dfrac{8}{40320},\\\ \dfrac{1}{8!} &= \dfrac{1}{40320}. \end{aligned}
Somando os numeradores:
40320 -40320 +20160 -6720 +1680 -336 +56 -8 +1 = 14833.
Portanto
\sum_{k=0}^{8} \frac{(-1)^k}{k!} = \frac{14833}{40320}.
Multiplicando por 8! obtemos
!8 = 8! \cdot \frac{14833}{40320} = 14833.

Passo 6

Verificação alternativa (recorrência): existe também uma recorrência útil que confirma o cálculo:
!n = (n-1)\bigl(!(n-1) + !(n-2)\bigr),
com !1=0 e !2=1. Calculando sequencialmente:
\begin{aligned} !3 &= 2(!(2)+!(1)) = 2(1+0)=2,\\\ !4 &= 3(2+1)=9,\\\ !5 &= 4(9+2)=44,\\\ !6 &= 5(44+9)=265,\\\ !7 &= 6(265+44)=1854,\\\ !8 &= 7(1854+265)=7\cdot2119=14833. \end{aligned}
A recorrência dá o mesmo resultado 14833, o que dá confiança na resposta.

Resposta

14833

Exercícios relacionados