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.

Ler o texto da imagem
Grafo com as seis cidades A, B, C, D, E e F, todas ligadas entre si; cada ligação tem um número que indica o custo do deslocamento (valores entre 2 e 13).
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 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
Ver gabarito e resolução
No ENEM 2010, 28% dos candidatos acertaram esta questão; 23% marcaram a C. Fonte: microdados do INEP.
As cidades B, C, D, E e F podem ser visitadas em 5! = 120 ordens. Como cada trajeto e seu inverso têm o…
Toque para ler o resto
O resto da resolução fica na sua conta. O passo a passo inteiro e por que cada alternativa está certa ou errada. Criar a conta é grátis e leva menos de um minuto.