Aptitude puzzle

Question

Consider a point P(n,n) in the cartesian co-ordinate system. A robot has to start from the origin and reach this point. The only steps the robot can take are :

• 1 unit right
• 1 unit up.

How many different paths can the robot take to point P?

Is there an optimal path to point P? (Both up and right steps incur the same cost).

Answer 1

It has to be (2n!)/(n!*n!) .

Explanation :

You have to reach from origin(0,0) to (n,n) Lets say v is the 1 unit vertical up and h is the 1 unit horizonatally right. All the paths will look like this - {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........) with v and h spread over a length of number of v's + number of h's and that has to be the

n + n = 2n.

Now total number of paths will be the combiantion of vs and hs in 2n places That will be equal to

(n+n)!/(n!*n!)

since v and h are repeated. Had there been some other unit like a or b it would have been considered in that as well. I think it will not be a catalan number as pointed . Rgds, Softy

Answer 2

The total number of paths is

(2n choose n)

since you must make n right steps and n up steps to end at the point (n,n), but the order in which you make the steps is irrelevant.

So there are 2n total steps, of which n are right and n are up. Choose the positions for the right steps in (2n choose n) ways, and the remaining steps must be up steps.

No path is better than any other since all paths use the same number of up and right steps (both n).

Answer 3

Scroll on this Wikipedia article (Catalan number) until you reach the following picture. The answer is there.

Thus, total number of paths is

Note: this forumal is only for monotonic paths, not crossing the diagonal. If you want to allow crossing the diagonal it needs to change a little. Use recursion for that :)

Hope it's useful.