Snowwalkers Dennis E. Shasha, Courant Institute of Mathematical Sciences, New York University. Grid City is a small planned city laid out at a completely regular 6 by 5 grid with streets going north-south and east-west. There is one building per city block. Grid occasionally suffers major snow storms. The Grid City Snow Clearing Department (GridClear) wishes to make it possible to reach each city block but the effort to move the snow is so great that they resolve to make it possible to go from any block to any other through paved paths. 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 one another 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, i.e. the largest number of such streets/buildings. 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 simplication, because there is no ice inside the buildings. Note: In the warm-up and questions to follow, you may find it helpful to look at the very nice applet of Arefin Huq with whom I have worked on this puzzle. http://www.cims.nyu.edu/~ah203/SnowWalkers.html All screenshots are from that applet. Warm-Up: Suppose the city were smaller. Given the 3 by 4 city grid of http://cs.nyu.edu/cs/faculty/shasha/papers/warmup3x4.tiff try to find a route requiring plowing only five streets, so pedestrians can walk from any block to a neighbor across at most two streets. Solution to warm-up: As the figure http://cs.nyu.edu/cs/faculty/shasha/papers/warmup3x4-5.tiff shows, for most blocks, a pedestrian can walk from a corner across the street to a corner of the neighboring building. The two blocks marked with 2 require walking through two buildings to travel to one another. For example, to go from (1,0) to (2,0), go to the northeast corner of (1,0), cross to (1,1), then go diagonally to the southeast corner of (1,1) and then cross the plowed street to the northeast corner of (2,1). From there go to the southwest corner of (2,1) and then into the block (2,2). End of Warm-Up. Recall that our city is 6 by 5 as illustrated in 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. 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? 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 its neighbor across a cleared intersection (cost of 0)? A neighboring 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 (though it can cross an intersection). 3. Can you figure out a way to use two plows, such that each plows nine streets, in such a way that that a pedestrian can walk from any block to its neighbor across a cleared intersection (cost of 0)? Solutions: 1. As you can see in the solution of http://cs.nyu.edu/cs/faculty/shasha/papers/oneplow6x5-14.tiff plowing just 14 streets is enough and the maximum number of blocks traveled is just 6. 2. The solution of http://cs.nyu.edu/cs/faculty/shasha/papers/oneplow6x5-18.tiff requires plowing 18 streets. That's the best I know of. 3. In the solution of http://cs.nyu.edu/cs/faculty/shasha/papers/twoplows6x5-9-9.tiff each vehicle plows nine streets of Grid City. All these solutions and the applet are the work of Arefin Huq.