Questão 30524
ENEM 2010
(Enem 2010) 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 saíra 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.
Examinando a figura, percebe que precisa considerar somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo. Ele gasta 1 min30s 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
60 min.
90 min.
120 min.
180 min.
360 min.
Gabarito:
90 min.
Resolução:
5! = 120 trajetos possíveis para se visitar as 5 cidades. Desconsiderando as simétricas, temos 60 trajetos para visitar as cidades, logo o tempo necessário será de 1,5. 60 = 90 minutos.
Alternativa letra B.