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
A) 60 min.
B) 90 min.
C) 120 min.
D) 180 min.
E) 360 min.
Matérias Necessárias para a Solução da Questão
- Análise Combinatória (Permutação)
- Interpretação de Texto e Problemas
Tema/Objetivo Geral:
Contagem de possibilidades (trajetos) com restrições, utilizando conceitos de permutação e, em seguida, cálculo do tempo total consumido.
Nível da Questão
Médio – A questão é considerada de nível médio pois envolve uma combinação de conceitos. Primeiro, é preciso identificar que o problema se refere à permutação (ordem importa), e em seguida aplicar uma restrição de simetria para reduzir o número de possibilidades. A partir disso, é necessário calcular o tempo total.
Gabarito
B) 90 min. – Este valor é o tempo total que João leva para analisar todas as sequências possíveis, considerando que ele gasta 1 minuto e 30 segundos (1,5 minutos) por sequência. O cálculo é feito determinando-se o número de permutações possíveis (60) e multiplicando-se pelo tempo gasto por sequência (1,5 minutos).
🔎 Passo 1: Análise do Comando e Definição do Objetivo
1.1 Transcrição Essencial
“O tempo mínimo necessário para João verificar todas as sequências possíveis no problema é de”
1.2 O que está sendo pedido?
O exercício quer saber quanto tempo João levará para analisar todos os trajetos possíveis, levando em consideração que cada análise leva 1 minuto e 30 segundos.
1.3 Objetivo Cristalino
Nosso objetivo é: 1) Calcular o número total de trajetos diferentes que João precisa analisar. 2) Multiplicar esse número pelo tempo gasto em cada trajeto (1 minuto e 30 segundos) para descobrir o tempo total.
1.4 Pergunta de Atenção
Você notou que os trajetos ABCDEFA e AFEDCBA são considerados iguais? É fundamental saber lidar com essa simetria, pois ela simplifica muito o cálculo.
📚 Passo 2: Explicação de Conceitos e Conteúdos Necessários
2.1 Definições e Fórmulas
- Permutação: É o número de maneiras diferentes de organizar um conjunto de objetos em uma ordem específica.
- Permutação Simples: Se temos ‘n’ objetos e queremos organizar todos eles, o número de permutações possíveis é n! (n fatorial). n! = n * (n-1) * (n-2) * … * 2 * 1.
- Exemplo: Se temos 3 letras (A, B, C), podemos organizá-las de 3! = 3 * 2 * 1 = 6 maneiras diferentes: ABC, ACB, BAC, BCA, CAB, CBA.
- Simetria em Trajetos: No problema, os trajetos são simétricos porque ir de A para B, depois para C é o mesmo que ir de A para C, depois para B (a ordem importa!). Se um trajeto e seu inverso custam o mesmo, precisamos descontar a contagem.
- Tempo Total: Para calcular o tempo total, multiplicamos o número de trajetos pelo tempo gasto em cada trajeto.
Tempo Total = Número de Trajetos * Tempo por Trajeto
📝 Passo 3: Tradução e Interpretação do Problema
3.1 Contextualização Simplificada
João é um vendedor que precisa visitar 5 clientes (B, C, D, E, F), mas ele quer economizar tempo. Ele sabe que o trajeto ABCDEFA é o mesmo que o AFEDCBA. Nossa missão é: 1) Descobrir quantas rotas diferentes ele pode fazer (ignorando a ordem, por causa da simetria). 2) Multiplicar esse número de rotas pelo tempo que ele leva para analisar cada uma (1 minuto e 30 segundos).
3.2 Estratégia Geral
Nosso plano de ataque será:
- Entender que a cidade A é o ponto de partida e chegada, então os trajetos sempre começam e terminam em A.
- Considerar que temos que organizar as 5 cidades restantes (B, C, D, E, F) em uma ordem específica.
- Calcular o número total de permutações possíveis das 5 cidades (5!).
- Dividir o resultado por 2, pois cada trajeto tem um “gêmeo” simétrico, que custa o mesmo.
- Multiplicar o número de trajetos pelo tempo por trajeto (1,5 minutos).
🧮 Passo 4: Desenvolvimento do Raciocínio e Cálculos
4.1 Passo a Passo Detalhado
Vamos seguir nossa estratégia.
1. Definindo as Posições:
- João sempre sai da cidade A e volta para a cidade A. Podemos visualizar o trajeto assim:
A _ _ _ _ _ A
Temos 5 “casas” para distribuir as 5 cidades (B, C, D, E, F).
2. Calculando o Número de Permutações:
- O número de maneiras de organizar 5 cidades em 5 posições é 5! (5 fatorial).
5! = 5 * 4 * 3 * 2 * 1 = 120
Isso significa que, sem considerar a simetria, há 120 trajetos possíveis.
3. Considerando a Simetria:
- Como os trajetos ABCDEFA e AFEDCBA têm o mesmo custo, cada trajeto tem um “gêmeo”. Para eliminar a contagem duplicada, dividimos o número de permutações por 2.
Número de Trajetos = 120 / 2 = 60
4. Calculando o Tempo Total:
- Tempo gasto por trajeto = 1 minuto e 30 segundos = 1,5 minutos.
- Tempo Total = Número de Trajetos * Tempo por Trajeto
Tempo Total = 60 * 1,5
Tempo Total = 90 minutos
4.2 Verificação Intermediária
Calculamos o número de trajetos (60), considerando a simetria, e multiplicamos pelo tempo de cada análise (1,5 minutos), obtendo 90 minutos.
4.3 Possível armadilha
A principal armadilha é esquecer de dividir por 2 o número de permutações para levar em conta a simetria. Se você não fizesse isso, acharia que 120 * 1,5 = 180 minutos, levando a uma alternativa incorreta.
4.4 Fechamento e expectativa
Nosso raciocínio nos levou a um tempo total de 90 minutos. Agora, vamos procurar este valor nas alternativas.
✅ Passo 5: Análise das Alternativas
5.1 Listagem das Alternativas
A) 60 min.
B) 90 min.
C) 120 min.
D) 180 min.
E) 360 min.
5.2 Justificativa Individual
- A) 60 min. (🔴): Incorreto. Este valor poderia ser obtido por um erro de contagem ou por um problema na divisão pela simetria.
- B) 90 min. (🟢): Correto. Este é o valor exato que encontramos para o tempo total.
- C) 120 min. (🔴): Incorreto. Este valor seria o resultado se você esquecesse de dividir pela simetria (120 trajetos * 1 minuto e 30 segundos).
- D) 180 min. (🔴): Incorreto. Este valor pode ter sido calculado multiplicando o número de combinações sem levar em conta a simetria pelo tempo gasto em cada trajeto.
- E) 360 min. (🔴): Incorreto. Este valor não corresponde a um erro de cálculo previsível no processo correto.
🏆 Passo 6: Conclusão e Justificativa Final
6.1 Resumo do Raciocínio
Para resolver o problema, identificamos que o número de trajetos possíveis envolvia uma permutação das 5 cidades. Reconhecemos a simetria (ABCDEFA é o mesmo que AFEDCBA) e dividimos o resultado da permutação por 2. Multiplicamos o número de trajetos pelo tempo gasto em cada análise para obter o tempo total.
6.2 Gabarito Reafirmado
A alternativa correta é a B), pois o tempo mínimo necessário é de 90 minutos.
6.3 Resumo Final para Revisão 🔍
Em problemas de roteamento com restrições, comece visualizando o problema. Identifique as repetições (trajetos simétricos) e ajuste os cálculos para evitar a contagem duplicada.
