Математика, вопрос задал reygen , 1 год назад

Хромой ферзь стоит в правом верхнем углу доски
5×5. За один ход он может передвинуться на 1 клетку влево, вниз или по диагонали "влево-вниз". Сколькими способами он может добраться до левого нижнего угла?

ГАЗ52: Откуда задачки?

reygen: Из курсов для подг. к олимпиадам

Ответы на вопрос

Ответил Artem112

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

$\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&&&&& \\ (4)&&&&& \\ (3)&&&&& \\ (2)&&&&& \\ (1)&&&&&\end{array}$

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

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

$\begin{array}{|c|c|c|c|c|c|}&(1)&(2)&(3)&(4)&(5) \\ (5)&&&&&1 \\ (4)&&&&& \\ (3)&&&&& \\ (2)&&&&& \\ (1)&&&&&\end{array}$

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

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

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

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

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

$a(i;\ j)=a(i+1;\ j)+a(i;\ j+1)+a(i+1;\ j+1)$

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

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

$a(i;\ j)=a(j;\ i)$

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

$a(4;\ 4)=a(5;\ 4)+a(4;\ 5)+a(5;\ 5)=1+1+1=3$

$a(4;\ 3)=a(5;\ 3)+a(4;\ 4)+a(5;\ 4)=1+3+1=5$

$a(4;\ 2)=a(5;\ 2)+a(4;\ 3)+a(5;\ 3)=1+5+1=7$

$a(4;\ 1)=a(5;\ 1)+a(4;\ 2)+a(5;\ 2)=1+7+1=9$

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

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

$a(3;\ 3)=a(4;\ 3)+a(3;\ 4)+a(4;\ 4)=5+5+3=13$

$a(3;\ 2)=a(4;\ 2)+a(3;\ 3)+a(4;\ 3)=7+13+5=25$

$a(3;\ 1)=a(4;\ 1)+a(3;\ 2)+a(4;\ 2)=9+25+7=41$

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

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

$a(2;\ 2)=a(3;\ 2)+a(2;\ 3)+a(3;\ 3)=25+25+13=63$

$a(2;\ 1)=a(3;\ 1)+a(2;\ 2)+a(3;\ 2)=41+63+25=129$

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

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

$a(1;\ 1)=a(2;\ 1)+a(1;\ 2)+a(2;\ 2)=129+129+63=321$

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