Enunciado
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. 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 \mathrm{1 min 30 s} 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)\mathrm{60}\mathrm{\,}\mathrm{min}.
B)\mathrm{90}\mathrm{\,}\mathrm{min}.
C)\mathrm{120}\mathrm{\,}\mathrm{min}.
D)\mathrm{180}\mathrm{\,}\mathrm{min}.
E)\mathrm{360}\mathrm{\,}\mathrm{min}.
Fonte: INEP · ENEM 2010 · 1ª aplicação · Dia 2 · Caderno azul.
Dia 2 · Caderno azul · 1ª aplicação
As cidades de saída e chegada são fixas em A. A ordem dos cinco clientes pode variar de 5! = 120 maneiras.
Cada percurso e seu inverso têm o mesmo custo. Como os cinco clientes são distintos, cada par reúne duas sequências diferentes, então basta examinar 120/2 = 60 representantes.
Cada exame leva um minuto e meio. O tempo mínimo é 60 × 1,5 = 90 minutos, alternativa B. Os valores das arestas não precisam ser somados para contar quanto tempo levará a comparação de todas as rotas.