Parades – 1
Parades wish to visit each street on their route exactly once. In these two examples, the first one is a successful parade route and the second one is not (one street is left out).
THE CHALLENGE
For each street layout, either find a parade route that visits each street exactly once or decide that it is impossible. For street layouts that have a parade, which ones allow parades to start and end at the same place? Can you find a pattern in your results?
Notes
THE CHALLENGE
The key idea is to keep track of where parades start and end, if they exist at all for a street map. Some parades can start and end anywhere, and some must start or end at very specific locations.
After looking at lots of examples, the following observation emerges. It is not important for young children to prove these things.
Result 1: If a corner has an odd number of streets coming to it, the parade must start or end there.
The reason for this is simple. Every time a parade goes into and back out of a corner, that accounts for an even number of streets coming to that corner. Therefore, corners with an odd number of streets must be the start or end of the parade.
Result 2: If there are more than two corners with an odd number of streets coming into them, then this map cannot have a parade.
Result 3: If there are exactly two corners with an odd number of streets, then any parade must begin at one of them and end at the other. In particular, it is impossible to have a parade that begins and ends at the same place.
Result 4: If there are no corners with an odd number of streets, then a parade can start anywhere, and it must start and end at the same place.