Um caminhão precisa recolher o lixo das ruas de um certo bairro. Por questões econômicas e ambientais, a empresa IMJ, responsável pela coleta, planeja as rotas de recolhimento, de modo que o caminhão percorra a menor distância possível, passando em cada rua exatamente uma vez, entrando e saindo de cada ponto. Quando isso não é possível, busca-se repetir o menor número possível de ruas na rota. Na figura, temos um esquema no qual os pontos representam esquinas, e as linhas representam as ruas.
Considere que cada rua mede 150 m de comprimento e que a rota do caminhão comece e termine no ponto A, passando por todas as ruas do esquema.
A empresa conseguiu encontrar a melhor rota de recolhimento de lixo, na qual o caminhão percorre uma distância igual a
A) 2 400 m.
B) 2 550 m.
C) 2 700 m.
D) 2 850 m.
E) 3 300 m.
Matérias Necessárias para a Solução da Questão
- Teoria dos Grafos (Vértices, Arestas e Grau)
- Caminhos e Circuitos Eulerianos
- Raciocínio Lógico-Matemático
Tema/Objetivo Geral: Otimização de rotas (Problema do Carteiro Chinês).
Nível da Questão
Difícil – Esta questão vai além da matemática do ensino médio padrão, entrando na área da Teoria dos Grafos. Para resolvê-la corretamente, é preciso conhecer o conceito de Circuitos Eulerianos e entender a importância do grau dos vértices (se é par ou ímpar) para determinar a possibilidade de um percurso. A solução exige um raciocínio de otimização que não é trivial.
Gabarito
C) 2 700 m. – A alternativa está correta. O mapa possui 16 ruas, mas devido à existência de quatro “esquinas” com um número ímpar de saídas, é necessário repetir no mínimo 2 ruas para criar um percurso fechado, totalizando 18 segmentos de 150 m.
🔎 Passo 1: Análise do Comando e Definição do Objetivo
1.1 Transcrição Essencial
“A empresa conseguiu encontrar a melhor rota de recolhimento de lixo, na qual o caminhão percorre uma distância igual a…”
1.2 O que está sendo pedido?
O exercício pede para calcular a distância mínima total que o caminhão deve percorrer para passar por todas as ruas do bairro, começando e terminando no ponto A.
1.3 Objetivo Cristalino
Nosso objetivo é determinar o número total de segmentos de rua que o caminhão precisa atravessar (incluindo as repetições necessárias) e multiplicar esse número por 150 metros.
1.4 Pergunta de Atenção
Você percebeu que a rota ideal nem sempre passa por cada rua apenas uma vez? O segredo para resolver o problema está em descobrir se é preciso repetir ruas e, em caso afirmativo, qual o menor número de repetições!
📚 Passo 2: Explicação de Conceitos e Conteúdos Necessários
2.1 Definições e Fórmulas / explicação de termos
Para resolver este problema, precisamos de conceitos da Teoria dos Grafos, que estuda mapas e conexões.
- Grafo: É um nome matemático para um mapa como o da questão.
- Vértices: São os pontos do mapa (as “esquinas”).
- Arestas: São as linhas que conectam os vértices (as “ruas”).
- Grau de um Vértice: É o número de arestas (ruas) que se conectam a um vértice (esquina). Contar o grau é fundamental para resolver o problema.
- Vértice de grau PAR: Uma esquina onde chega/sai um número par de ruas (2, 4, 6…).
- Vértice de grau ÍMPAR: Uma esquina onde chega/sai um número ímpar de ruas (1, 3, 5…).
- Circuito Euleriano (A Rota Perfeita): É um caminho que passa por todas as arestas (ruas) de um grafo exatamente uma vez e termina no mesmo vértice (esquina) onde começou. Existe uma regra de ouro para saber se isso é possível:
- Regra de Euler: Um Circuito Euleriano só é possível se TODOS os vértices do grafo tiverem grau PAR.
- E se a Rota Perfeita não for possível? (O nosso caso):
Se existem vértices de grau ÍMPAR, é impossível fazer o percurso sem repetir ruas. Para encontrar a rota mais curta, precisamos repetir o menor número de ruas possível de forma a “transformar” todos os vértices ímpares em pares. Fazemos isso conectando os vértices de grau ímpar em pares pelos caminhos mais curtos.
📝 Passo 3: Tradução e Interpretação do Problema
3.1 Contextualização Simplificada
Vamos pensar como o planejador da rota. O caminhão precisa limpar todas as 16 ruas do bairro. O ideal seria passar em cada uma delas só uma vez e voltar para o ponto A. Para saber se isso é possível, precisamos checar as esquinas. Se todas as esquinas tiverem um número par de ruas, ótimo! Se não, teremos um problema: o caminhão ficará “preso” em algumas esquinas. Para resolver isso, ele terá que passar de novo em algumas ruas para continuar o trajeto. Nossa missão é descobrir qual é o número mínimo de ruas que ele precisa repetir para fazer o trabalho completo.
3.2 Estratégia Geral
Nosso plano de ataque será:
- Contar o número total de ruas no mapa.
- Analisar cada esquina e contar o número de ruas que chegam nela (o grau de cada vértice).
- Identificar quantas e quais esquinas têm um número ímpar de ruas.
- Com base na Regra de Euler, determinar o número mínimo de ruas que precisam ser repetidas para “consertar” o problema.
- Somar as ruas originais com as repetidas e multiplicar pela distância de 150 m.
🧮 Passo 4: Desenvolvimento do Raciocínio e Cálculos
4.1 Passo a Passo Detalhado
1. Contar o total de ruas (arestas):
Contando todas as linhas do mapa, encontramos um total de 16 ruas.
Se a rota perfeita fosse possível, a distância seria 16 * 150 = 2400 m.
2. Analisar as esquinas (vértices):
Vamos contar quantas ruas chegam em cada esquina:
- Ponto A: 3 ruas (grau ÍMPAR)
- Esquina à direita do ponto A: 3 ruas (grau ÍMPAR)
- Esquina central (abaixo de A): 6 ruas (grau PAR)
- Esquina à esquerda da central: 4 ruas (grau PAR)
- Esquina à direita da central: 4 ruas (grau PAR)
- Esquina inferior esquerda (externa): 2 ruas (grau PAR)
- Esquina inferior esquerda (interna): 3 ruas (grau ÍMPAR)
- Esquina inferior direita (interna): 3 ruas (grau ÍMPAR)
- Esquina inferior direita (externa): 2 ruas (grau PAR)
Temos 4 vértices de grau ÍMPAR.
3. Aplicar a Regra de Euler:
Como existem vértices de grau ímpar, não é possível percorrer todas as 16 ruas exatamente uma vez e voltar ao ponto A. O caminhão terá que repetir ruas.
4. Determinar o número de repetições:
Temos 4 esquinas “problemáticas” (de grau ímpar). Para resolver o problema, precisamos conectar essas esquinas em pares, adicionando um caminho (ruas repetidas) entre elas. Para minimizar a distância, conectamos os pares mais próximos:
- Par 1: O ponto A e a esquina à sua direita são vizinhos. Repetir a rua entre eles resolve o problema desses dois pontos. (1 rua repetida)
- Par 2: A esquina inferior esquerda interna e a esquina inferior direita interna também são vizinhas. Repetir a rua entre elas resolve o problema desses outros dois pontos. (1 rua repetida)
Assim, precisamos repetir no mínimo 2 ruas.
5. Calcular a distância total:
A rota ótima percorrerá todas as ruas originais mais as ruas repetidas.
Total de segmentos percorridos = 16 (originais) + 2 (repetidas) = 18 segmentos de rua
Distância Total = 18 * 150 m
Distância Total = 2700 m
4.2 Verificação Intermediária
A análise da teoria dos grafos nos mostrou que 2 ruas precisam ser repetidas para viabilizar um circuito que passe por todas as ruas, totalizando 18 trechos de 150 m.
4.3 Possível armadilha
A armadilha mais evidente é ignorar a impossibilidade do circuito e simplesmente calcular a distância total das ruas originais: 16 ruas * 150 m = 2400 m. Isso levaria à alternativa A, que está incorreta porque essa rota não é possível na prática.
4.4 Fechamento e expectativa
Nosso raciocínio nos levou a uma distância total de 2700 metros. Agora, vamos procurar este valor nas alternativas.
✅ Passo 5: Análise das Alternativas
5.1 Listagem das Alternativas
A) 2 400 m.
B) 2 550 m.
C) 2 700 m.
D) 2 850 m.
E) 3 300 m.
5.2 Justificativa Individual
- A) 2 400 m. (🔴) Incorreta. Este valor corresponde a percorrer apenas as 16 ruas originais (16 * 150), o que é impossível de se fazer em um circuito fechado devido aos vértices de grau ímpar.
- B) 2 550 m. (🔴) Incorreta. Corresponde a repetir apenas uma rua (17 * 150). Repetir uma rua não é suficiente para eliminar os quatro vértices de grau ímpar.
- C) 2 700 m. (🟢) Correta. Este valor corresponde a percorrer as 16 ruas originais mais as 2 ruas repetidas necessárias (18 * 150) para criar um circuito euleriano.
- D) 2 850 m. (🔴) Incorreta. Corresponde a repetir três ruas (19 * 150). É uma rota possível, mas não é a “melhor rota” (a mais curta).
- E) 3 300 m. (🔴) Incorreta. Corresponde a repetir seis ruas (22 * 150), uma rota muito ineficiente.
🏆 Passo 6: Conclusão e Justificativa Final
6.1 Resumo do Raciocínio
Analisamos o mapa como um grafo, identificando que ele possuía 4 vértices de grau ímpar. Pela Teoria dos Grafos, isso impede um circuito que passe por cada rua apenas uma vez. Para criar a rota mais curta possível, determinamos que era necessário repetir 2 ruas, totalizando 18 trechos a serem percorridos, resultando em uma distância final de 2700 m.
6.2 Gabarito Reafirmado
A alternativa correta é a C) 2 700 m.
6.3 Resumo Final para Revisão 🔍
Em problemas de rota que exigem passar por todas as “ruas”, sempre comece analisando as “esquinas”! Conte quantas ruas se conectam a cada uma. Se houver esquinas com um número ímpar de ruas, você obrigatoriamente terá que repetir alguns trechos para conseguir completar o percurso.
