Ano 2010#matematica

Sobre o tema

O problema do caixeiro-viajante é um clássico da matemática combinatória e da otimização, onde se busca o menor trajeto que visita um conjunto de cidades exatamente uma vez e retorna ao ponto de partida. Nesta questão do ENEM 2010, João precisa visitar cinco clientes partindo da cidade A, com custos de deslocamento entre as cidades dados em um grafo. A análise envolve o cálculo do número de permutações possíveis para os trajetos, considerando que trajetos simétricos (como ABCDEFA e AFEDCBA) têm o mesmo custo e são descartados. O tempo gasto para examinar cada sequência é de 1 minuto e 30 segundos, e o objetivo é determinar o tempo mínimo necessário para verificar todas as sequências possíveis. Esse problema ilustra a aplicação de fatorial e simetria em problemas de contagem, sendo relevante para vestibulandos que desejam dominar análise combinatória.

Tópicos relacionados

  • Problema do caixeiro-viajante
  • Permutações e fatorial
  • Simetria em trajetos
  • Análise combinatória no ENEM
  • Otimização de rotas

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.

![](https://enem.dev/2010/questions/173/32cafe03-6732-45ee-85e9-d97f56364ee2.jpg)

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

Alternativas

  • A)

    60 min.

  • B)

    90 min.

  • C)

    120 min.

  • D)

    180 min.

  • E)

    360 min.

0.0 (0 avaliacoes)

Avaliar: +1 XP. Favoritar: salva pra revisar. Comentar: +5 XP + 1 credito IA.

Comentarios (0)

Login obrigatorio

Carregando comentarios...

Perguntar pra IA

Perguntas frequentes

O que é o problema do caixeiro-viajante?

É um problema de otimização que busca a rota mais curta para visitar um conjunto de cidades exatamente uma vez e retornar ao ponto de partida.

Como calcular o número de trajetos possíveis em um problema do caixeiro-viajante com n cidades?

O número de rotas possíveis é (n-1)!/2, considerando que a cidade inicial é fixa e que rotas simétricas (sentido inverso) são equivalentes.

Por que trajetos simétricos são descartados no problema?

Porque o custo de um trajeto é o mesmo independentemente do sentido percorrido (ida ou volta), então eles representam a mesma rota.

Questões relacionadas