Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here is a puzzle about combinatorics.

Suppose you have a square grid with $n^2$ points. You want to go from the origin $(0, 0)$ to $(n-1, n-1)$. Assuming you can only go right or up, in how many ways can you reach destination?

share|improve this question
    
Now that you know how to deal with squares, generalize. In how many ways can you get from $(0,0)$ to $(6,10)$ only going right or up, if you must follow grid lines? –  André Nicolas Jun 15 '11 at 22:18
    
Are you restricted to moving one unit at a time or can you go directly to any point that is right and/or up from the current one? –  Mitch Jun 16 '11 at 15:29
add comment

3 Answers 3

up vote 1 down vote accepted

Its a very common problem. Using google just for a bit would already have brought you very detailed answers: http://www.joaoff.com/2008/01/20/a-square-grid-path-problem/

share|improve this answer
add comment

Hint: start filling in a piece of graph paper with the number of ways to get to points near (0,1). How many ways are there to get to (0,2)? to (1,1)? to (2,0)? Can you see a pattern?

share|improve this answer
add comment

Hint: Since you can move either right or up at each step, you can encode a path from $(0,0)$ to $(n-1,n-1)$ using a sequence of letters R and U. For example, if you have a $4 \times 4$ grid, a sequence R,U,R,U,R,U will take you from $(0,0)$ to $(3,3)$. Now try and generalize to the $n \times n$ grid and count the number of possible strings.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.