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:
- Há
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 papéis aos 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
nomes. Entre todas as permutações de
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
o número de tais permutações quando há
pessoas. Nosso objetivo é calcular
.
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
o conjunto de permutações em que a pessoa
tira o próprio nome. Pelo princípio da inclusão-exclusão, o número de permutações com nenhum ponto fixo é
Agora vamos interpretar cada termo combinatoriamente.
Passo 4
Contagem dos termos: se fixarmos exatamente
pessoas para que tirem o próprio nome (um conjunto qualquer de
pessoas), então o resto dos
nomes pode ser permutado livremente entre os
participantes restantes, dando
permutações. O número de escolhas do conjunto de
pessoas é
. Portanto o termo correspondente na inclusão-exclusão é
. Assim
Agora simplificamos cada termo:
. Logo
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
(para obter o resultado inteiro sem usar calculadora). Primeiro note que
. Escrevemos cada
com denominador
:
Somando os numeradores:
Portanto
Multiplicando por
obtemos
Passo 6
Verificação alternativa (recorrência): existe também uma recorrência útil que confirma o cálculo:
com
e
. Calculando sequencialmente:
A recorrência dá o mesmo resultado
, o que dá confiança na resposta.
Resposta
14833