Exercício 22. Considere 4 cidades A, B, C e D. Ana e João pensam fazer um passeio pelas 4 cidades, passando por cada uma delas apenas uma vez.
(a) Se eles podem começar por qualquer cidade e terminar em qualquer cidade, quantos trajetos são possíveis?
(b) Se eles devem começar pela cidade A, quantos caminhos são possíveis?
(a) Se eles podem começar por qualquer cidade e terminar em qualquer cidade, quantos trajetos são possíveis?
(b) Se eles devem começar pela cidade A, quantos caminhos são possíveis?
Passo 1
O enunciado pede para contar de quantas maneiras Ana e João podem percorrer as quatro cidades
,
,
e
passando por cada uma exatamente uma vez. Esse é um problema de análise combinatória que se resolve com permutações de elementos distintos.
Passo 2
Para permutar
elementos distintos, o número total de sequências em que eles podem aparecer é dado por
Isso vem da escolha sequencial: na primeira posição há
opções, na segunda
, e assim por diante.
Passo 3
(a) Aqui não há restrição de cidade inicial ou final, portanto basta permutar as
cidades:
Logo, existem
trajetos possíveis.
Passo 4
(b) Se o passeio deve começar em
, fixamos
na primeira posição e permutamos as outras
cidades:
Portanto, há
caminhos possíveis começando por
.
Resposta
(a)
(b)
(b)