As you’ll likely recall, last weekend I ran every single block in Ditmas Park. I’m nothing if not prepared, of course, so I spent a bit of time figuring out how best to do this.

When I looked at the map, I figured it would probably be around 10 miles. No sweat; I was looking to do at least 16, and getting to and from the area would require at least 4-5 more. Any remaining mileage could be made up.

Ditmas Park is about as grid-ified as you’ll get in Brooklyn, with no real angular avenues like Flatbush, to the east. As the neighborhood expands slightly from Foster Avenue up to Beverley Road, it adds a north-south Road (Stratford) and a few small connectors (Lewis Place, Matthew Court, Slocum Place). These would throw a kink into my planning.

I figured the easiest way to cover the ground would be a zigzag pattern: north, east, south, east, left, right, left, right, B, A, start. I’d also have to run the border of the neighborhood.

Then back and forth and repeat until done. Without duplicating routes in the neighborhood, this is the best I could do.

Two mathematical problems came to mind. First, the Königsberg Bridge Problem: how do you cross each of these seven bridges exactly once?

Source: Wolfram Alpha

According to graph theory, you can’t. If we look at each borough as a “node”, and each bridge as an “edge” between two nodes, we see the following graph:

Source: Wolfram Alpha

In short, to craft a once-and-exactly-once route, we can have no more than two nodes with an odd “degree” – that is, an odd number of edges connecting to it. Here, all four nodes have odd degree: A has degree 5, while B, C, and D have degree 3.

Think about it this way. If you take a bridge into the island at center, you need to take a second bridge out to continue on your way. (The exception is if you’re starting or ending on the island. That’s why two of the nodes can be of odd degree.)

Here’s Ditmas Park as a graph:

By restricting my route to just the neighborhood proper, I introduce a huge number of odd-degree nodes: basically, anything along the border, and a few other spots. That means I’ll have to duplicate several stretches.

This leads to the second math problem:

You have a chess queen, a piece that can move an unlimited number of squares in any one direction in a single turn. How do you get the queen to cross or land on all of the squares in this 3×3 area in just four moves?

Give this one a try. Bet you can’t get it to work.

This one’s a dirty trick, I admit. The answer is to move her outside the 3×3 grid, into adjoining (but hidden) territory.

I briefly considered extending my tour one block in every direction so as not to repeat myself. But unlike the queen, this would require real energy – not just an extension of the same move. Scrapped.

In the end, I duplicated a few too many edges – most in the upper left corner, and the one on the upper right. This is the price I pay for entering the neighborhood at an even-degreed node instead of an odd-degreed one. (The total cost here, really, was only around 0.3 miles of extra running.)

Perhaps one of my mathematician friends can find the optimal route.

Google+

Keith Williams