A puzzle from Peter Winkler’s excellent Mathematical Puzzles (2021):
A certain island contains a network of roads. Each road segment (between one intersection and the next) has its own name. If d is the average number of road segments that meet at an intersection, show that it’s possible to take a drive on the island that traverses at least d road segments and hits them in alphabetical order.
|
SelectClick for Answer |
Each road has two ends, so the total number of road ends observed at the island’s intersections is twice the number of roads on the island. The number we’re calling d, the average number of road segments that meet at an intersection, is thus 2m/n, where m is the number of roads on the island and n is the number of intersections.
Station a pedestrian at each intersection. At time 1, let the pedestrians at either end of the alphabetically first road traverse it, changing places. At time 2, let the pedestrians who find themselves at either end of the alphabetically second road do the same. Continue this procedure until it’s been applied to all the roads. At the end of this exercise each pedestrian will have followed an alphabetical path (because we addressed the roads in alphabetical order). Each road is traversed twice, and the number of pedestrians equals the number of intersections on the island. So the average number of roads that each pedestrian traverses is 2m/n = d.
|
