Problem:
A king is placed in the left bottom corner of the chessboard. At each step it can either move one square up, or one square to the right, or diagonally - one up and one to the right. How many ways are there for the king to reach the top right corner of the board?
Solution
Solution:
We shall make a table. In each cell of the table we will write a number of ways in which the king can reach that cell. We will fill it out gradually starting with a row of ones at the bottom and a column of ones at the left. To fill out the rest we use the following rule: the number in each cell is equal to the sum of the numbers immediately below, to the left, and diagonally (to the left and below). The result is:
| 1 | 11 | 61 | 231 | 681 | 1683 |
|---|---|---|---|---|---|
| 1 | 9 | 41 | 129 | 321 | 681 |
| 1 | 7 | 25 | 63 | 129 | 231 |
| 1 | 5 | 13 | 25 | 41 | 61 |
| 1 | 3 | 5 | 7 | 9 | 11 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.