```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.
```