Questão 178 do ENEM 2011 — Matemática

Entendendo o problema

O caminhão de lixo deve percorrer todas as ruas do esquema e voltar ao ponto de partida A, com a menor distância possível. Isso é o clássico Problema do Carteiro Chinês da Teoria dos Grafos, em que as ruas são as arestas e os cruzamentos são os vértices.

O critério do circuito euleriano

É possível sair de A, passar por cada rua exatamente uma vez e voltar a A somente quando todos os cruzamentos têm grau par (número par de ruas ligadas a eles). Se algum cruzamento tem grau ímpar, o caminhão é obrigado a repetir alguma rua para conseguir entrar e sair dele.

Analisando o esquema

Contando as ruas do desenho, há $16$ ruas ao todo. Verificando o grau (número de ruas) de cada cruzamento, encontramos $4$ cruzamentos de grau ímpar — os demais têm grau par.

Como existem cruzamentos ímpares, o caminhão terá que repetir algumas ruas. Para a rota ser a menor possível, emparelhamos os cruzamentos ímpares dois a dois e repetimos os trechos que os ligam pelo caminho mais curto. Com os $4$ vértices ímpares formando $2$ pares de cruzamentos vizinhos, basta repetir $2$ ruas.

Calculando a distância total

O percurso mínimo cobre as $16$ ruas originais mais as $2$ ruas repetidas, ou seja, $18$ trechos. Cada rua mede $150\text{ m}$: $D = 18 \times 150 = 2\,700\text{ m}$

Portanto, a melhor rota tem $2\,700\text{ m}$.

A resposta correta é a alternativa C.