5
$\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

$\endgroup$
0

3 Answers 3

Reset to default
6
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ Well, looks like 16 steps everytime. $\endgroup$
    – user8695
    Mar 25, 2011 at 10:36
  • $\begingroup$ @Moccoa - That's correct. Now, look at such a path as a sequence of "right"s and "down"s. How many sequences are there? $\endgroup$
    – Pandora
    Mar 25, 2011 at 10:39
  • $\begingroup$ @Moccoa: and how many paths with 16 steps you can construct? $\endgroup$
    – Fabian
    Mar 25, 2011 at 10:39
  • $\begingroup$ Well if I can combine 8 ups with 8 rights, then it should be 64 (8^2) $\endgroup$
    – user8695
    Mar 25, 2011 at 10:41
  • $\begingroup$ 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. $\endgroup$
    – Pandora
    Mar 25, 2011 at 10:46
3
$\begingroup$

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?
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user8695
    Mar 25, 2011 at 10:35
  • $\begingroup$ 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? $\endgroup$
    – Henry
    Mar 25, 2011 at 10:58
  • $\begingroup$ Hmm from each tile I have always 2 possible routes...but not when I am on the very left column. $\endgroup$
    – user8695
    Mar 25, 2011 at 11:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Henry
    Mar 25, 2011 at 11:12
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.