Math Is Fun Forum

musician_14

Member

Registered: 2008-11-01

Posts: 4

Cominatorics- Man Walking....

Sam wants to go from one street corner in a city to another one nine blocks east and six blocks north. Assume the streets are laid out as a square grid,.

A) How many ways may Sam choose the fifteen block walk?

B) How many ways may Sam choose the firteen block walk, if he does not want to walk through the (3,3) intersection? (noted by "X")

        Here is a diagram for B).

               __ __ __ __ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __ __ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __ __ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __ __ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __X__ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __ __ __ __ __ __ __
              |   |   |    |   |   |   |    |   |   |
               __ __ __ __ __ __ __ __ __

Last edited by musician_14 (2008-11-01 15:29:05)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Cominatorics- Man Walking....

The answer to a) is 15C6 (or 15C9).
Sam can choose a path by selecting 6 different numbers from 1 to 15.
Then he relates this to his path by travelling south on the nth step whenever n is one of his 6 numbers, and east when it isn't.

Not the best explanation, but hopefully you get my meaning.

An alternative way of solving would be to label the grid using a Pascal's triangle-style method.

1-1-1-...
|  |  |
1-2-3-...
|  |  |
1-3-6-...
.  .  .
.  .  .

Each number represents the number of paths Sam can take to reach the intersection that the number lies on, and is made by adding the two numbers north and west of itself (with 1's along the north and west edges).
Extending this grid should get you the same answer as before.

That method is less efficient than the other one, but I mention it because a variation of it is the only way I can think of right now to solve b).

---

Why did the vector cross the road?
It wanted to be normal.