Questão 173 do ENEM 2010 comentada
Veja como contar trajetos diferentes quando a ida e a volta têm o mesmo custo.
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
- A60 min.
- B90 min.
- C120 min.
- D180 min.
- E360 min.
Tente resolver antes de abrir. Errar aqui é de graça.
Ver a resposta e a resolução
O que a questão cobra
A questão cobra o princípio multiplicativo e a contagem de permutações. Também exige reconhecer que um trajeto e seu inverso têm o mesmo custo.
Resolução
João parte da cidade A, visita os cinco clientes em alguma ordem e volta para A. Como os clientes estão em cidades diferentes, há 5! ordens possíveis para visitá-los.
somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo.
A figura representa os custos dos deslocamentos entre as cidades. Para esta pergunta, não é necessário somar esses custos: o que importa é que percorrer as mesmas ligações na ordem inversa mantém o custo total. Assim, cada trajeto e seu inverso formam um par, e basta examinar um deles.
5! = 120 sequências
120 ÷ 2 = 60 sequências a verificar
Cada verificação leva 1 min 30 s, ou 1,5 minuto.
60 × 1,5 = 90 minutos
Portanto, o tempo mínimo para verificar todas as possibilidades relevantes é de 90 minutos.
Alternativa por alternativa
- A
60 minutos permitem verificar 40 sequências, pois cada uma leva 1,5 minuto. Isso não cobre as 60 sequências necessárias.
- B
Correta. É a correta: há 60 sequências distintas após agrupar cada trajeto com seu inverso, e verificá-las leva 90 minutos.
- C
120 minutos permitem verificar 80 sequências. Como são necessárias 60 verificações de 1,5 minuto cada, esse tempo não é o mínimo.
- D
180 minutos permitem verificar 120 sequências. Porém, os trajetos em sentidos inversos têm o mesmo custo, então basta verificar 60.
- E
360 minutos permitem verificar 240 sequências. Esse número excede as 60 verificações necessárias, mesmo sem considerar as simetrias.
Para lembrarSe cada trajeto tem um inverso com o mesmo custo, conte os trajetos distintos dividindo o total por 2.
Resolução escrita com ajuda de IA a partir do gabarito oficial e revisada por um segundo modelo antes de ir ao ar. Achou erro? Avise a gente.
Essa caiu. Outras do mesmo assunto também vão.
No enemjuntos você treina Princípios de contagem com questões oficiais do mesmo assunto, e o app te chama para revisar antes de você esquecer.
Treinar esse assunto grátis →