Posição nos cadernos
Enem 2010
João mora na cidade A e precisa [...]
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 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
Selecione uma alternativa antes de responder.
Resolução comentada
Para resolver este problema, precisamos calcular o número total de sequências possíveis e depois considerar a simetria mencionada.
Primeiramente, identificamos que João sai de A, visita 5 cidades diferentes (B, C, D, E, F) em alguma ordem, e retorna a A. O número de maneiras de organizar 5 cidades em ordem é 5! = 120 sequências diferentes.
No entanto, a questão menciona que trajetos simétricos (como ABCDEFA e AFEDCBA) têm o mesmo custo. Isso ocorre porque o percurso de volta é idêntico ao de ida, apenas em direção oposta. Portanto, cada par de trajetos simétricos pode ser considerado como uma única sequência para análise. Isso divide o total por 2: 120 ÷ 2 = 60 sequências únicas a examinar.
Se João gasta 1 min30s (ou 1,5 minutos) para examinar uma sequência e descartar sua simétrica, o tempo total necessário é: 60 × 1,5 = 90 minutos.
Conceito-chave
Este problema envolve a Análise Combinatória, especificamente o conceito de permutações e simetria em problemas de otimização de rotas (relacionado ao Problema do Caixeiro Viajante). A permutação de n elementos é calculada como n!, representando todas as formas diferentes de organizar esses elementos em sequência.
A simetria mencionada é um conceito importante em otimização: quando um trajeto e seu reverso têm custos idênticos (como é o caso em grafos não-direcionados com custos simétricos), podemos reduzir pela metade o espaço de busca. Isso é uma estratégia eficiente para diminuir o tempo computacional necessário para encontrar a solução ótima. Reconhecer padrões simétricos é fundamental para otimizar algoritmos de busca.
Análise da questão
Alternativa: 360 min - Esta é uma resposta incorreta. Se multiplicássemos 120 sequências × 1,5 minutos = 180 minutos, não chegaríamos a 360. Ou se considerássemos 240 sequências (erro no cálculo de simetria) × 1,5 = 360 min. Esta alternativa parece resultar de um erro ao não considerar adequadamente a divisão por 2 da simetria, ou de considerar duplicações desnecessárias.
A resposta correta deveria ser 90 minutos, calculado como: (5! ÷ 2) × 1,5 min = 60 × 1,5 = 90 min. Isso ocorre porque temos 120 sequências totais de 5 cidades, mas como cada trajeto e seu simétrico têm o mesmo custo, consideramos apenas 60 sequências únicas, gastando 1,5 minutos em cada uma.
Descubra seu nível em Matemática e suas Tecnologias
Faça um diagnóstico rápido e veja quais temas você já domina e quais precisam de mais prática.
Começar grátis →Entre para comentar!