On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Grid City is a small planned city laid out on a completely regular six-by-five grid with streets going north-south and east-west. There is one building per city block.
Grid occasionally suffers major snowstorms. The Grid City Snow Clearing Department (GridClear) wishes to make it possible for residents to move about on paved roads but the effort to move the snow is so great that they want to minimize plowing as well as danger to the public. This means that the path itself may snake through the city and may even loop, but the plows won't double back on a paved road for fear of running over the many pedestrians.
The head of GridClear consults you to help plan the path. You are told the path must start somewhere on the outside boundary of the grid, but you can choose where, because Grid City has many garages available. The goal is to ensure that for any two blocks that neighbor each other north-south or east-west, a resident will need to travel over only a few streets (or through a few buildings) along the cleared path. The "score" of a path is the worst case, that is, the largest number of such streets/buildings that going to a neighbor would require. Crossing a plowed intersection costs nothing, but it is impossible to cross an unplowed intersection or street.
You may assume that each building block has an entrance at every corner and that walking through a building to any other corner (even to the diagonally opposite one) costs the same as walking one city block along a plowed street. You accept this simplification, because there is no ice inside the buildings.
In the warm-up problem and questions to follow, you may find it helpful to look at the very nice applet developed by Arefin Huq, with whom I have worked on this puzzle.
http://www.cims.nyu.edu/~ah203/SnowWalkers.html
All the screen shots that follow are from that applet.
Warm-up Puzzle:
Suppose the city were smaller and set up on a three-by-four city grid like so:
http://cs.nyu.edu/cs/faculty/shasha/papers/warmup3x4.tiff
Try to find a route that requires plowing only five streets, so pedestrians can walk from any block to a neighboring one by crossing at most two streets.
Solution to Warm-up Puzzle
Recall that our city is six by five, as illustrated here:
http://cs.nyu.edu/cs/faculty/shasha/papers/oneplow6x5.tiff
It's still the case that every block has an entrance at every corner and you must begin plowing from the outside of the grid.
Problem 1. Assuming you have just one plow, can you arrange a path of 15 or fewer streets and guarantee that a pedestrian on any block can reach any east-west or north-south neighbor by walking at most eight blocks? What does your path look like?
Solution to Problem 1
Problem 2. Still with just one plow, what is the minimum-length path you can design that will guarantee that a pedestrian can walk from any block to any neighboring one across a cleared intersection (yielding a cost of 0)?
Solution to Problem 2
Problem 3. A nearby city has just given you another plow. You can therefore use two but both must start from the outside of the grid and neither can drive on a city block already plowed by the other (although they can cross at an intersection). Can you figure out a way to use two plows such that each plows nine streets and a pedestrian can walk from any block to any neighboring one across a cleared intersection?
Solution to Problem 3