counting direction

[venkat jothi]

A person X standing at a point P on a flat plane starts walking.
At each step, he walks exactly 1 foot in one of the directions North,
South, East or West. Suppose that after 6 steps X comes to the
original position P. Then the number of distinct paths that X can
take is

Source: B.Stat, Hons -2010 UGA  - 8th problem

[Shirsendu Roy]

After three moves, the person has to be at less than 3 moves from the center.

here four such cases, 1 point has 9 ways to get there, two others have 3 ways of getting there and the last one has only 1 way.

For the way back there are as many possibilities, so sum of squares 9^2+3^2+3^2+1^2=100 multiplied by four because of symmetry=400 different paths.

If you consider a path is same as an other if it is taken in an other order then divide by 2 gives 200.

[Author]

Posts