|
|
Puzzles Many Ways To Walk Home 
Click to enlarge |
|
Sarah works in an office at the corner of Main and Center Streets. She lives on the corner of 4th Avenue and E Street (see the map at right). On her walks home from work she likes to try as many different routes as possible without making her trip any longer than needed. She has noticed that there are many different routes that will take her home with a walking distance of 9 blocks -- she merely chooses whether to go north or east at each intersection, taking care to never go north of 4th Avenue or east of E Street.
Your task is this: find the number of different routes that Sarah might use.
Here's a slight hint that might save you a lot of tedious counting: Sarah must travel east 5 blocks and north 4 blocks -- is there a formula you could use to count the number of routes if instead it was m blocks east and n blocks north?
Courtesy of Mark Nielsen | |
Social Bookmarking    
Comments | lydiaeniola2607 |  04:14:08, 10 May 08 |  Newbie
Group:Members
Points: 0
Posts: 0
Warn level: 0
| NNNNSSSSSN
| | | | terveloc | 19:39:43, 17 Nov 07 |  Newbie
Group:Members
Points: 0
Posts: 5
Warn level: 0
| There's a simple way to think about this. Write each path as a string of north and east turns. Each string will be 9 characters long. Also, each string will contain 4 N's and 5 E's. A possible path is then NENENENEE.
Now, simply count all *distinct* strings that fit the criteria. There are 9!/(5!*4!). These are all the possible distinct routes. Again, the answer is 126.
| | | | terveloc | 14:26:51, 17 Nov 07 | Newbie
Group:Members
Points: 0
Posts: 5
Warn level: 0
| anji_viper, some of those paths are identical
The answer is 126.
| | | | anji_viper | 09:07:12, 21 Oct 07 |  Newbie
Group:Members
Points: 0
Posts: 0
Warn level: 0
| From office to home:
5 east + 4 north
There are 5! ways that she can walk 5 blocks east, i.e. 120 ways.
There are 6! ways that she can walk 4 blocks north, i.e. 720 ways.
Total number of ways should hence be 120 + 720 = 840 ways.
Therefore, to walk m blocks east + n blocks north, total number of ways = m! + (m+1)!
| | | | Danik | 16:01:45, 10 Oct 07 | Newbie
Group:Members
Points: 0
Posts: 1
Warn level: 0
| I started to look at the simplest case of n=m=1. Then there are 2 ways.
If m=n=2, then there are 6 ways.
Since 2!=2 and 3!=6 I thoungt maybe the number of ways when m=n is (m+1)!
But for m=n=3 I got 20 ways and 4! is not 20 so that didnt hold.
I then realised this:
At each intersection the number of ways equals the sum of the number of ways at each of the two intersections to the north and east.
Writing it out in a diagram you get something like this:
1__1__1__1__1
5__4__3__2__1
15_10_6__3__1
35_20_10_4__1
Which is a tilted version of pascals triangle.
I got 126.
| | | | Jackson | 17:11:12, 09 Oct 07 | Newbie
Group:Members
Points: 0
Posts: 2
Warn level: 0
| 116,
Im my yahoo account (jellyfishshad@yahoo.com) and I will send you a proof for it and explain why it works in regular terms.
| | |
|
