Max/Min question

[phannux]

I have accepted a route in the city. I requested that my employer find me a
home less than one mile away from my workplace so that I could bicycle to work
every day. I also wanted my home to be placed so that my trips to work could
be along a different route for every day of my contract. My contract is for
five years. I will work five days a week, five weeks a year, for five years.
The streets in this area form a grid of squares each 1/16 mile on each side-
so my home must be fewer than 16 blocks from work. In order to be efficient, I
only travel routes in which each block gets me closer to work.

a) At how many different sites could my home be located?
b) What is the nearest that I can live to my place of work and still have
access to enough different routes?
c) At what site(s) could I get the maximum number of routes to work?
d) How many years could I work at this job and ride to work along a different
route each day if my home is located at a site of maximum routes?

 

[pka]

I have accepted a route in the city. I requested that my employer find me a
home less than one mile away from my workplace so that I could bicycle to work
every day. I also wanted my home to be placed so that my trips to work could
be along a different route for every day of my contract. My contract is for
five years. I will work five days a week, five weeks a year, for five years.
The streets in this area form a grid of squares each 1/16 mile on each side-
so my home must be fewer than 16 blocks from work. In order to be efficient, I
only travel routes in which each block gets me closer to work.

This is an interesting problem. Bu I don't want waste time if there is a typo.
Are you sure that the 'five weeks a year' is correct?

 

[pka]

I have accepted a route in the city. I requested that my employer find me a
home less than one mile away from my workplace so that I could bicycle to work
every day. I also wanted my home to be placed so that my trips to work could
be along a different route for every day of my contract. My contract is for
five years. I will work five days a week, five weeks a year, for five years.
The streets in this area form a grid of squares each 1/16 mile on each side-
so my home must be fewer than 16 blocks from work. In order to be efficient, I
only travel routes in which each block gets me closer to work.

This is an interesting problem. But I don't want waste time if there is a typo.
Are you sure that the 'five weeks a year' is correct?

Fifty weeks is usual.

 

[phannux]

Yes...that is the way I received the question!

 

[Denis]

First, have a look at a few sites here:
http://www.google.ca/search?hl=en&sourc ... =&aq=f&oq=

Then re-word your problem: be as simple as possible, like use 125 instead of silly stuff like 5days:5 weeks:5 years.

 

[pka]

Well we will go with it. And I thought university teaching at 36 weeks a year was great.

Think of a \(\displaystyle 16\times 16\) grid where \(\displaystyle (0,0)~\&~(16,16)\) are the opposite vertices. Standing at \(\displaystyle (0,0)\) we must go to the right 16 places and 16 places up to land on \(\displaystyle (16,16)\) making steady progress.
Any string of 16 R’s and 16 U’s will represent a path we can take.
There are \(\displaystyle \frac{32!}{(16!)^2}=601080390\) possible pathways to take.
Now all we need \(\displaystyle 5\times 5\times 5=125\). You are only working 125 days in five years.
From any point in that grid, say \(\displaystyle (j,k),~j<16~\&~k<16\) the are \(\displaystyle \frac{(32-j-k)!}{(16-j)!\cdot (16-k)!}\) ways to get to \(\displaystyle (16,16)\)
If you are at either \(\displaystyle (11,12)\) or \(\displaystyle (12,11)\) there are 126 paths to take.

I will leave it with you at this point.
I will say, I think you should consider the employer being located at the center of a \(\displaystyle 32\times 32\) grid because you could live in any one of the four \(\displaystyle 16\times 16\) sub-grids.

 

[Denis]

So general case formula is (2n)! / (n!)^2, right?

 

[daon]

It wasn't described here what geometry was to be used. If it were taxi-cab, then we would have a diamond shape making equidistant paths of 1 mile being 16 "moves" from the center. Here's a picture I came up with:

The white/turquoise area are all the places this person may live to be within 1 "taxicab-mile" from work.