Verified answer

Рассмотрим такую доску 5×5:

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&&&&& \\ (4)&&&&& \\ (3)&&&&& \\ (2)&&&&& \\ (1)&&&&&\end{array}[/tex]

Заполним ее следующим образом: в каждую клетку будем писать число способов попасть в эту клетку из правой верхней клетки.

В саму правую верхнюю клетку запишем число 1, так как попасть из этой клетки в нее саму можно одним способом - стоять на месте.

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&&&&&1 \\ (4)&&&&& \\ (3)&&&&& \\ (2)&&&&& \\ (1)&&&&&\end{array}[/tex]

Всю пятую строку также заполним единицами, так как попасть во все ячейки этой строки можно одним способом - двигаться строго влево из правой верхней клетки (шестой строки нет, поэтому движения в эту строку вниз или по диагонали невозможны):

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&&&&& \\ (3)&&&&& \\ (2)&&&&& \\ (1)&&&&&\end{array}[/tex]

По аналогии, пятый столбец заполняем единицами, так как попасть во все ячейки этого столбца можно одним способом - двигаться строго вниз из правой верхней клетки (шестого столбца нет, поэтому движения в этот столбец влево или по диагонали невозможны):

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&&&&&1 \\ (3)&&&&&1 \\ (2)&&&&&1 \\ (1)&&&&&1\end{array}[/tex]

Остальные строки заполним, используя формулу:

[tex]a(i;\ j)=a(i+1;\ j)+a(i;\ j+1)+a(i+1;\ j+1)[/tex]

То есть, если рассмотреть квадрат 2х2, то значение в левой нижней клетке равно сумме значений во всех остальных клетках.

Из соображений симметрии можно сказать, что:

[tex]a(i;\ j)=a(j;\ i)[/tex]

Заполняем четвертую строку и четвертый столбец:

[tex]a(4;\ 4)=a(5;\ 4)+a(4;\ 5)+a(5;\ 5)=1+1+1=3[/tex]

[tex]a(4;\ 3)=a(5;\ 3)+a(4;\ 4)+a(5;\ 4)=1+3+1=5[/tex]

[tex]a(4;\ 2)=a(5;\ 2)+a(4;\ 3)+a(5;\ 3)=1+5+1=7[/tex]

[tex]a(4;\ 1)=a(5;\ 1)+a(4;\ 2)+a(5;\ 2)=1+7+1=9[/tex]

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&9&7&5&3&1 \\ (3)&&&&5&1 \\ (2)&&&&7&1 \\ (1)&&&&9&1\end{array}[/tex]

Заполняем третью строку и третий столбец:

[tex]a(3;\ 3)=a(4;\ 3)+a(3;\ 4)+a(4;\ 4)=5+5+3=13[/tex]

[tex]a(3;\ 2)=a(4;\ 2)+a(3;\ 3)+a(4;\ 3)=7+13+5=25[/tex]

[tex]a(3;\ 1)=a(4;\ 1)+a(3;\ 2)+a(4;\ 2)=9+25+7=41[/tex]

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&9&7&5&3&1 \\ (3)&41&25&13&5&1 \\ (2)&&&25&7&1 \\ (1)&&&41&9&1\end{array}[/tex]

Заполняем вторую строку и второй столбец:

[tex]a(2;\ 2)=a(3;\ 2)+a(2;\ 3)+a(3;\ 3)=25+25+13=63[/tex]

[tex]a(2;\ 1)=a(3;\ 1)+a(2;\ 2)+a(3;\ 2)=41+63+25=129[/tex]

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&9&7&5&3&1 \\ (3)&41&25&13&5&1 \\ (2)&129&63&25&7&1 \\ (1)&&129&41&9&1\end{array}[/tex]

Заполняем последнюю клетку, значение которой и будет ответом:

[tex]a(1;\ 1)=a(2;\ 1)+a(1;\ 2)+a(2;\ 2)=129+129+63=321[/tex]

[tex]\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&1&1&1&1&1 \\ (4)&9&7&5&3&1 \\ (3)&41&25&13&5&1 \\ (2)&129&63&25&7&1 \\ (1)&\boxed{321}&129&41&9&1\end{array}[/tex]

Таким образом, добраться до левой нижней клетки можно 321 способами.

Ответ: 321 способами