PRÁTICA COM QUESTÕES OFICIAIS

Questão 178 do ENEM PPL 2011

2º dia · Matemática · Matemática: Lógica e raciocínio lógico

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.

Grafo que esquematiza as ruas e esquinas de um bairro, formado por triângulos conectados e um quadrado na parte inferior. Os vértices representam as esquinas, sendo um vértice no topo destacado com preenchimento em preto e identificado pela letra A; os demais vértices são círculos vazados.

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

  1. A
    2 400 m.
  2. B
    2 550 m.
  3. C
    2 700 m.
  4. D
    2 850 m.
  5. E
    3 300 m.
Escolha uma alternativa para conferir o gabarito.
Reportar erro na questão
O que está errado?
Sem cadastro: não guardamos quem enviou.
Resolução comentada

Para percorrer todas as ruas e voltar ao ponto de partida sem repetir nenhuma, o grafo precisa ter todos os vértices de grau par (circuito euleriano). Quando isso não ocorre, é preciso repetir ruas.

Contando no esquema:

  1. Número de ruas (arestas): são 17.
  2. Grau de cada esquina: A = 2, o vértice do meio da linha superior (C) = 7, o vértice à sua esquerda = 4, o vértice da direita = 2, os dois vértices do triângulo superior direito = 2 cada, o vértice da extremidade esquerda = 2, o vértice central da linha inferior (H) = 5, o vértice à direita dele = 4, e os dois vértices inferiores do quadrado = 2 cada.
  3. Vértices de grau ímpar: apenas C (grau 7) e H (grau 5).

Com dois vértices ímpares, basta repetir o menor caminho entre eles. C e H estão ligados diretamente por uma rua, então repete-se só essa rua. Com ela duplicada, todos os graus ficam pares e existe um circuito que começa e termina em A.

Total de ruas percorridas: 17 + 1 = 18.

Distância: 18 \times 150 = 2\,700\ \text{m}.

Alternativa C.

Por que as outras alternativas estão erradas

  • ACorresponde a 16 ruas, menos do que as 17 existentes, o que é impossível.
  • BCorresponde a 17 ruas, sem repetir nenhuma, mas há dois vértices de grau ímpar, então é preciso repetir uma.
  • DCorresponde a 19 ruas, repetindo duas, quando basta repetir uma.
  • ECorresponde a 22 ruas, um excesso que não é mínimo.

Assunto: Lógica e raciocínio lógico.

Reportar erro na resolução
O que está errado?
Sem cadastro: não guardamos quem enviou.
Ver como caiu na prova Questão 178 no caderno Cinza do ENEM PPL 2011