8. The King's Path (from 7th grade, 2 points). A chess king is on the a1 square of a chessboard and wants to move to the h8 square, moving right, up, or diagonally up-right. In how many ways can he do this?
Solution. Instead of letter designations for the columns, we use numerical ones. Then, instead of al, we can write $(1,1)$. Let $S_{m, n}$ be the number of ways to get from the cell $(1,1)$ to the cell $(m, n)$. We are interested in $S_{8,8}$.

Obviously, $S_{1, n}=1$ and $S_{m, 1}=1$ for all $m$ and $n$. In particular, we can consider that $S_{1,1}=1$, since the king can get to the cell $(1,1)$ in only one way: by standing in place and doing nothing.

If $m>1$ and $n>1$, then the cell $(m, n)$ can be reached only from one of the three cells $(m-1, n),(m, n-1)$, and $(m-1, n-1)$. This gives the recurrence relation $S_{m, n}=S_{m-1, n}+S_{m, n-1}+S_{m-1, n-1}$.

The calculations can be easily performed in Excel (Fig. 2).

| INDEX |  |  | $-x \vee f=C 5+C 6+D 6$ |  |  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 4 | A | B | C | D | E | F | G | H | I |
|  | 8 | 1 | 15 | 113 | 575 | 2241 | 7183 | 19825 | 48639 |
|  | 7 | 1 | 13 | 85 | 377 | 1289 | 3653 | 8989 | 19825 |
|  | 6 | 1 | 11 | 61 | 231 | 681 | 1683 | 3653 | 7183 |
|  | 5 | 1 | 9 | 41 | 129 | 321 | 681 | 1289 | 2241 |
|  | 4 | 1 | 7 | $=\mathrm{C} 5+$ | +D6 | 129 | 231 | 377 | 575 |
|  | 3 | 1 | 5 | 13 | 25 | 41 | 61 | 85 | 113 |
|  | 2 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 |
|  | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|  |  | a | b | c | d | e | f | g | h |

Fig. 2. Solution to problem 8 in Excel

Answer: 48639.