4
$\begingroup$

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

3 Answers 3

5

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!)}$.

  • 1
    Well, looks like 16 steps everytime.2011-03-25
  • 0
    @Moccoa - That's correct. Now, look at such a path as a sequence of "right"s and "down"s. How many sequences are there?2011-03-25
  • 0
    @Moccoa: and how many paths with 16 steps you can construct?2011-03-25
  • 0
    Well if I can combine 8 ups with 8 rights, then it should be 64 (8^2)2011-03-25
  • 0
    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.2011-03-25
  • 0
    @Moccoa: this is not correct. So you need 16 steps to reach the bottom out of which 8 times you should go down (and correspondingly 8 times right). How many ways are there to choose the 8 downward steps from the 16 total steps?2011-03-25
  • 0
    Pandora, thanks but I am not familiar with the english math expressions :( I am thinking about it, is it not just the number of possible combinations between these 16 steps?2011-03-25
  • 0
    @Moccoa - I'll add an explanation in the answer.2011-03-25
  • 0
    By the way, as Henry pointed out, it's actually 14 steps.2011-03-25
3

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?
  • 0
    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.2011-03-25
  • 0
    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?2011-03-25
  • 0
    Hmm from each tile I have always 2 possible routes...but not when I am on the very left column.2011-03-25
  • 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.2011-03-25
1

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.