Questão 173 – Análise Combinatória
João mora na cidade A e precisa visitar cinco clientes, localizados em cidades diferentes da sua. Cada trajeto possível pode ser representado por uma sequência de 7 letras. Por exemplo, o trajeto ABCDEFA, informa que ele sairá da cidade A, visitando as cidades B, C, D, E e F nesta ordem, voltando para a cidade A. Além disso, o número indicado entre as letras informa o custo do deslocamento entre as cidades. A figura mostra o custo de deslocamento entre cada uma das cidades.
Como João quer economizar, ele precisa determinar qual o trajeto de menor custo para visitar os cinco clientes. somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo. Ele gasta 1min30s para examinar uma sequência e descartar sua simétrica, conforme apresentado.
O tempo mínimo necessário para João verificar todas as sequências possíveis no problema é de
A) 60 min.
B) 90 min.
C) 120 min.
D) 180 min.
E) 360 min.
Solução
Considerando que ele sempre vai sair da cidade A e chegar na cidade A, supondo que ele vai passar por 7 lugares, fixamos o primeiro e o último como A.
A _ _ _ _ _ A
Vamos distribuir as 5 letras restantes entre as casas restantes, ficando
A 5 . 4 . 3 . 2 . 1 A
5! = 120
Como cada um tem um simétrico dividimos esse número ao meio
120/2 = 60
Para descartar cada simétrico, ele gasta 1 min e 30, que é 1,5 min
60 . 1,5 = 90 minutos
Alternativa B
