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.

I am beginning math student and encountered following task which I do not know how to solve: There is chessboard, ie 8x8 tiles. In the top left corner there is pawn. He cannot go diagonally and he can only move down and right.
1)How many steps will he need to reach the right bottom corner shortest way?
2)How many of these ways do exist?

Thank you in advance

share|improve this question
    
Why the downvote? –  Fabian Mar 25 '11 at 10:34
    
If this is a homework question, you should tag it as such (I'm not the one who downvoted, but maybe that was their motive). –  Pandora Mar 25 '11 at 10:40
    
No it is not, I have encounter it in a excercise book and there is no resolution. –  user8695 Mar 25 '11 at 10:42

3 Answers 3

up vote 4 down vote accepted

First you should think - Is there a way which is not the shortest? Now, He will have to move 7 steps right and 7 steps down. In how many ways can you construct such a path?

EDIT: After having come to the conclusion that the number of such paths is the number of combinations of 14 steps, 7 of which are down and the other 7 of which are right, we reduce the problem to the following: How many sequences of 7 "down"s and 7 "right"s are there?

How do we arrange such a sequence? If we know exactly on which 7 of the 14 steps the pawn went down, then we know that on the rest of the steps (that is, the other 7), he went right. So the problem is equivalent to finding in how many ways we can choose 7 places out of an ordered sequence of 14 places (those chosen ones will be the "down" steps). This number is denoted by $\binom{14}{7}$, or in general if you have $n$ objects out of which you want to choose $k$, then the number of such choices is denoted by $\binom{n}{k}$.

Now let's compute the value of $\binom{14}{7}$. You have 14 options for the first choice (since you can take either one of the 14), 13 options for the second, and so on until you choose the 7th one out of the remaining 8 options. To conclude, this equals to $14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8$, but then you also have to divide by the number of permutations of the 7th steps, since it is not important whether you, say, take the first step on the first choice and the second on the second choice, or the other way around, so you have $\frac{14!}{7!7!}$ (Why?) - Or in the general case, $\frac{n!}{k!(n-k!)}$.

share|improve this answer
1  
Well, looks like 16 steps everytime. –  user8695 Mar 25 '11 at 10:36
    
@Moccoa - That's correct. Now, look at such a path as a sequence of "right"s and "down"s. How many sequences are there? –  Pandora Mar 25 '11 at 10:39
    
@Moccoa: and how many paths with 16 steps you can construct? –  Fabian Mar 25 '11 at 10:39
    
Well if I can combine 8 ups with 8 rights, then it should be 64 (8^2) –  user8695 Mar 25 '11 at 10:41
    
The correct way to look at it is as follows: If you have 16 ordered places in which you would like to put these "down" and "right" steps, you have $\binom{16}{8}$ places to put, say, the "down"s (why?), and then the rest of the places will be taken by the "right"s. –  Pandora Mar 25 '11 at 10:46

Hint:

  1. Can you find any route? How many steps? How about another? And another? Any pattern?
  2. Slightly harder. Can you find how many routes there are to squares near the start? How about slightly further away? How about each square on the chaessboard?
share|improve this answer
    
No clue what you are talking about :) The shortest way is surely one steop right, down, right, down till the final destination. But I have no clue how to mathematically write it. –  user8695 Mar 25 '11 at 10:35
    
So that is 14 steps (at least when I count it, though you seem to have got 16). Now try some easier questions. How many routes to the tile under the starting tile? The one to the right of the starting tile? The one down one and right one? The others nearby? –  Henry Mar 25 '11 at 10:58
    
Hmm from each tile I have always 2 possible routes...but not when I am on the very left column. –  user8695 Mar 25 '11 at 11:04
1  
So draw an $8\times 8$ grid. Put 1 in the top left square, in fact in each square in the top row, as there is only one way to get to those squares. Do the same in the left column. Now start filling in the other squares, starting with the highest rows and left-most columns. For example there are just 2 routes to the tile diagonally touching the starting tile, and 3 to the tile to its right. –  Henry Mar 25 '11 at 11:12

You can also solve it using an integral equation method. The number of rights or ups will always be $8$, let $x_1$ be the number of steps moved in 1st row, $x_2$ in 2nd, ..., $x_8$ in eighth. Sum $x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8=8$ ($x_i \geq 0$ where $i=1,2,...,8$). Every integral solution corresponding to this equation will give you a method. Number of solutions is 16c8.

share|improve this answer

Your Answer

 
discard

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