Questão 173 do ENEM 2010 — Matemática
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
Resolução comentada
Saindo de A e voltando para A, as 5 cidades intermediárias podem ser visitadas em qualquer ordem: são 5! = 120 sequências possíveis. Como cada trajeto e o seu inverso têm o mesmo custo, basta examinar metade: 60 sequências. A 1min30s (1,5 min) cada: 60 × 1,5 = 90 minutos.
O valor 180 min esquece de descartar as sequências simétricas e examina as 120 (120 × 1,5 = 180) — justamente a economia que o enunciado manda aproveitar.