Комбинаторные задачи на шахматной доске

§ 5] ДВИЖЕНИЯ КОРОЛЯ 31 До сих пор мы рассматривали тот случай, когда король переме­щается поступательно в направлениях J и —>. Естественно теперь перейти к более общему случаю, а именно пусть король переме­щается поступательно в трех направлениях: | , —> и / * . Мы опять начнем свое исследование изучением движения короля из угловой клетки (1,1) на клетку ( я , у ) . Обозначим через Dx%y искомое число перемещений. Для того чтобы попасть на (х, у ) , король неминуемо должен пройти либо через (х—Ii у—1), либо через ( я — 1 , у ) , либо через (xt у—1). Отсюда будем иметь такое соотношение: D1 гг. у •о. у—г ~Г" A c - I , у "Ί" A » , у-1 : 4 1 7 25 63 3 1 5 13 25 2 1 3 5 7 1 1 / г 1 1 ί Z 3 4 ФИГ. 17. причем Da j i г= 1, Duy= 1. G помощью этой фор­мулы можно определить Dxiy для любой клетки. Проделав все вычисления, мы получим сле­дующую арифметическую шашечницу1 (фиг. 17). Впрочем, оказывается, что и" Dxiy можно не­посредственно выразить через χ и у с помощью тех же методов, которые применялись к Fx, у. Обозначим соответ­ственно через 1, 2 и 3 перемещения \ , —> и / * . В своем движении от клетки ( 1 , 1) до (Xi у ) король должен пройти χ—1 строк и у—1 колонн. При ходе 1 он переходит на новую строку, но колонна остается одна и та же. Наоборот, при ходе 2 король переходит на новую колонну, оставаясь на одной и той же строке. Наконец, при ходе 3 наша фигура перемещается на новую колонну и новую строку. Поэтому ход 3 эквивалентен перемещению 12 или 2 1 . Представляются только следующие возможности: 1) король переходит от ( 1 , 1) к ( х , у ) с помощью χ—1 ходов 1 и у — 1 ходов 2; 2) король переходит от ( 1 , 1) к (л:, у ) с помощью χ у — 2 ходов 2 и одного хода 3; 3) король переходит от ( 1 , 1) к ( х , у ) с помощью х -у—3 ходов 2 и двух ходов 3; - 2 ходов 1, •3 ходов 1, к) король переходит от ( 1 , 1) к (л:, у ) с помощью χ — k ходов 1, у — k ходов 2 и (k—1) хода 3 и т. д. Очевидно, что число перемещений типа 1) равно числу ...