Em uma cidade de n+1 habitantes, uma pessoa conta um boato a uma segunda, a qual, por sua vez, o repete a uma terceira, etc. A cada passo a pessoa que recebe o boato é escolhida aleatoriamente dentre as n pessoa disponíveis. Ache o número de resultados em que o boato seja transmitido r vezes
a) sem voltar à primeira pessoa que o contou;
b) sem que seja repetido a nenhuma pessoa.

Passo 1

Então, o enunciado diz o seguinte: numa cidade com pessoas, a pessoa 1 conta um boato para alguém; depois, quem recebeu conta para outra pessoa, e assim por diante, sempre escolhendo aleatoriamente entre as pessoas que não foram as últimas a falar. A gente quer contar de quantas maneiras isso pode acontecer em transmissões, em dois cenários:
a) o boato nunca volta pra pessoa 1;
b) o boato nunca é contado para alguém que já ouviu antes (ou seja, sem repetição de público).
Conteúdo usado: princípio multiplicativo de contagem e permutações simples.

Passo 2

Resolvendo o item (a): “sem voltar à primeira pessoa”.
  1. Teoria envolvida: sempre que numa sequência de escolhas cada passo tem certo número de opções independentes dos outros, a gente multiplica essas quantidades (princípio multiplicativo).
  2. No primeiro passo (quem vai ouvir o boato da pessoa 1), como ela não pode se contar a si mesma, existem exatamente n times (n-1)^,r-1 opções.
  3. A partir do segundo passo até o -ésimo, quem está contando nunca pode voltar para a pessoa 1 nem para quem acabou de contar. Mas, como a pessoa 1 já foi excluída de vez no passo 1, todos os contadores a partir daí não são a pessoa 1; isso significa que, em cada um desses passos, excluímos 2 pessoas (o contador atual e a pessoa 1), sobrando opções.
  4. Pelo princípio multiplicativo, o total é

Passo 3

Resolvendo o item (b): “sem repetir a nenhuma pessoa”.
  1. Agora, além da regra de não falar para quem acabou de falar, queremos nunca falar para quem já ouviu antes. Ou seja, em cada transmissão a gente escolhe alguém que ainda não apareceu na cadeia de boato.
  2. No passo 1 (de 1 para o próximo), temos n times (n-1)times (n-2)times cdots times (n+1 - r) ;=; n!(n - r)!,, opções (todas menos a pessoa 1).
  3. No passo 2, sobram pessoas que ainda não ouviram; no passo 3, pessoas, e assim por diante.
  4. No -ésimo passo (contagem de 1 a ), sobram exatamente pessoas “novas”.
  5. Logo, o número total de sequências é
que é a permutação de elementos tomados de em .

Resposta

a)
b)

Exercícios relacionados