Thread: Walking to Work

I have accepted a job in a major metropolitan area. I have requested that my employer find me an apartment less than a mile from the office so that I can walk to work everyday. I also want my home to be located so that I can take a different route every day for 5 years. I work 5 days a week, 50 weeks a year. Streets in the area are on a grid of squares, each 1/16 mile on the side, so my home must be fewer than 16 blocks from work. (Assume paths do not overlap themselves, and each "step" must decrease the distance between me and the office.)

a. At how many different sites could my apartment be located?
b. What is the nearest I can live to my office and still have access to enough different routes?
c. At which sites could I get the most number of routes? For how long could I work before running out of routes if my apartment is located at a site of maximum routes?


Honestly, I'm terrible at these kinds of problems and I have no clue how to even begin this. Any help would be greatly appreciated.

First of all, you can simplify the problem a bit by recognizing that the total number of sites is 4 times the number of sites to, say, the northwest of the office (in other words, you only need to solve for the number of sites that involve going south and east, and then multiply this by 4). Also, I'd suggest drawing it out on graph paper.

The number of paths from one corner to another of a rectangular grid is , where n is the total distance from one corner to the other (i.e. the number of steps needed), and k is the distance travelled in one direction (for example, the number of steps that must be going south, so if you lived 5 blocks north of your office and an arbitrary number of blocks west, k would be 5). So you need the number of cases where and (since you need 1250 different routes with a maximum distance of 16 (well, a maximum distance of 1 mile, but it's easier to do if you consider each step 1 unit)).

To find the nearest you can live to your office, minimise n.

The place with the most routes will be the square with n=16 and k=8.