Em uma cidade de
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
pessoa disponíveis. Ache o número de resultados em que o boato seja transmitido
vezes sem que seja repetido a nenhuma pessoa.
Passo 1
Beleza, vamos lá! O enunciado diz o seguinte: numa cidade com
pessoas, alguém começa um boato e passa pra outra pessoa, que passa pra outra, e assim por diante, fazendo exatamente
transmissões. A cada passo, a pessoa que vai ouvir é sorteada aleatoriamente entre as
possíveis (a gente não conta quem tá falando). A gente quer contar de quantas formas isso pode acontecer sem nunca repetir quem já ouviu o boato antes.
Conteúdo: combinatória básica, mais precisamente o princípio fundamental da contagem e permutações simples. Vamos precisar usar a ideia de “multiplicar as opções de cada etapa” e reconhecer que isso dá uma permutação de elementos tomados
a
.
Conteúdo: combinatória básica, mais precisamente o princípio fundamental da contagem e permutações simples. Vamos precisar usar a ideia de “multiplicar as opções de cada etapa” e reconhecer que isso dá uma permutação de
Passo 2
Primeiro, pense no passo 1 de transmissão:
- O boato parte de quem começa (fixo) e vai pra mais uma pessoa.
- Quem recebe pode ser qualquer uma das
pessoas restantes.
Logo, temosopções para a 1ª transmissão.
Passo 3
Agora, na 2ª transmissão:
- Quem acabou de ouvir (chama ele de “locutor atual”) não pode ser escolhido de novo, então a gente olha só pras outras pessoas.
- Dessas
possíveis, já teve uma que ouviu na transmissão 1 e não pode repetir.
Isso deixaopções para a 2ª transmissão.
Passo 4
Repetindo essa lógica, na k-ésima transmissão (até chegar em
):
- O locutor atual não conta, e também não podem ser escolhidas nenhuma das já ouvidas antes.
- Então, no passo
, as opções restantes são .
Passo 5
Pela regra do produto (princípio fundamental da contagem), o total de maneiras sem repetir é:
Isso é exatamente a permutação de
elementos tomados
a
, que escrevemos como