A rota do caminhão de lixo
O caminhão de lixo precisa passar por todas as ruas do bairro uma vez só e voltar para onde começou. Isso sempre dá?
- Em cada mapa, registre seu palpite na tarefa: dá ou não dá?
- Toque numa esquina para pôr o caminhão lá.
- Toque nas ruas, uma depois da outra. Cada rua só pode ser usada uma vez.
Mapa e tarefas
1. Vila Esperança
Rota: ainda não começou.
Faça seu palpite primeiro. O mapa abre quando você registrar o palpite na tarefa.
Responda às perguntas da tarefa primeiro. Depois, Mostrar contagem mostra as ruas de todas as esquinas.
Mapa 1: Vila Esperança
Dá para o caminhão passar por todas as ruas uma vez só e voltar para onde começou?
Depois do palpite, toque numa esquina do mapa e siga pelas ruas.
Mapa 2: Jardim Paraíso
E neste bairro, dá para passar por todas as ruas uma vez só e voltar para onde começou?
Se o caminhão ficar preso, desfaça ou recomece de outra esquina.
Mapa 3: Centro
E no Centro, dá para passar por todas as ruas uma vez só e voltar para onde começou?
Conte as ruas de cada esquina
Conte no mapa as ruas que chegam na esquina pedida. Depois, Mostrar contagem, embaixo do mapa, mostra as ruas de todas as esquinas e completa a última coluna da tabela. Esquinas ímpares são as que têm número ímpar de ruas.
| Mapa | Seu palpite | O que aconteceu | Esquinas ímpares |
|---|
Desafio: abrir uma rua nova
No bairro Vila Nova, o caminhão não consegue fazer o circuito. A prefeitura pode abrir uma rua nova, numa das linhas tracejadas. Qual rua faz o circuito existir?
Depois do palpite, abra a rua nos botões embaixo do mapa e trace o circuito para provar.
Decida só contando
Três bairros novos. Em cada um, conte as ruas de cada esquina e decida o que dá para fazer, antes de traçar.
Depois de registrar, trace a rota para conferir. A tarefa fica feita quando os três bairros tiverem decisão.
Desafio extra: Centro
No Centro, qual é o menor número de ruas novas que fecha o circuito? Abra as ruas e trace para provar.
O que está acontecendo
Esta parte abre quando você terminar a tarefa de contar as ruas de cada esquina.
O número de ruas que chegam numa esquina é o grau da esquina. Na matemática, o mapa é um grafo: as esquinas são os vértices, e as ruas são as arestas.
Toda vez que o caminhão passa por uma esquina, ele chega por uma rua e sai por outra. As ruas daquela esquina vão sendo gastas de duas em duas. Se o grau é ímpar, sobra uma rua no fim: ou o caminhão sai por ela e não volta, ou chega por ela e fica preso. Por isso só a esquina onde a rota começa e a esquina onde ela termina podem ter grau ímpar.
Uma rota que passa por todas as ruas uma vez só e volta ao início é um circuito euleriano. Uma rota que passa por todas as ruas uma vez só, mas termina em outra esquina, é um caminho euleriano. Os nomes homenageiam Leonhard Euler, que no século 18 resolveu um problema parecido, o das sete pontes da cidade de Königsberg. A regra, para um bairro em que dá para ir de qualquer esquina a qualquer outra:
- todas as esquinas com grau par: tem circuito euleriano, começando em qualquer esquina;
- exatamente duas esquinas com grau ímpar: não tem circuito, mas tem caminho euleriano, de uma dessas esquinas até a outra;
- mais de duas esquinas com grau ímpar: não tem nem um, nem outro.
Depois, volte às tarefas para os desafios: abrir uma rua nova e decidir três bairros só contando.
Para o professor
Objetivo
Ao final, o aluno consegue decidir, contando as ruas de cada esquina, se um mapa tem uma rota que passa por todas as ruas uma vez só e volta ao início. É o teorema de Euler para circuitos (seção 12.5 do livro), com o caso de exatamente duas esquinas ímpares, o caminho euleriano da seção 12.6, como extensão. O problema de quem recolhe lixo, entrega cartas ou varre ruas é o problema do carteiro chinês, citado no livro.
Pré-requisitos
Saber o que é número par e ímpar e ler um mapa simples. Não é preciso ter visto grafos antes; os termos grau, vértice, aresta, circuito euleriano e caminho euleriano aparecem na explicação, depois que o aluno já mexeu.
Como usar em aula
Uns 25 minutos. Projete o mapa 1 e peça um palpite da turma antes de traçar; um aluno vai ao quadro (ou dita as esquinas) e fecha o circuito. Deixe as duplas tentarem os mapas 2 e 3 por uns 6 minutos, anotando palpite e resultado. Pergunte: em qual mapa ninguém conseguiu? Alguém terminou a casinha em outra esquina? De onde saiu? Peça então que contem as ruas de cada esquina e só depois ligue "Mostrar contagem" na projeção. Leia a explicação com a turma, faça o desafio da Vila Nova e feche com os três bairros da última tarefa: cada dupla decide só contando, diz em voz alta, e só então alguém traça. Quem terminar antes vai para o desafio extra.
Erros comuns
Achar que não deu por falta de tentativa: o aluno que insiste no Centro sem contar está nesse erro, e a contagem mostra que o problema é o mapa. Achar que tanto faz a esquina de partida: na casinha (Jardim Paraíso), só dá começando em E ou F, as duas esquinas ímpares. Voltar ao início cedo demais na Vila Esperança (de A para C, D e de volta a A) e concluir que é impossível: ali todas as esquinas são pares, então o erro é a ordem das ruas. Confundir passar por todas as esquinas com passar por todas as ruas; o ODA avisa quando isso acontece. No desafio extra, achar que abrir mais ruas sempre ajuda: abrir as quatro diagonais deixa quatro esquinas ímpares de novo.
Perguntas para discussão
- Por que só as esquinas do começo e do fim da rota podem ter número ímpar de ruas?
- Existe bairro com exatamente uma esquina ímpar? (Dica: some os graus de todas as esquinas. Cada rua entra na soma duas vezes, então a soma é sempre par.)
- Se um bairro não tem circuito, o caminhão precisa repetir algumas ruas. Como escolher quais repetir para andar o mínimo?
- Que outros serviços da cidade têm o mesmo problema do caminhão de lixo? E quais precisam passar por todas as esquinas, e não por todas as ruas?
Baseado em Contemporary Mathematics, OpenStax, seções 12.5 e 12.6, sob licença CC BY-NC-SA 4.0. Este ODA está sob a mesma licença. Acesse o livro gratuitamente em openstax.org.