Вероятность и шахматный король (движение по доске)

[tess]

Пусть шахматная доска представляет собой прямоугольник длиной a и шириной b квадратиков (при a = b = 8 имеем обычную шахматную доску).
Сколько различных маршрутов имеет шахматный король, стоящий в левом нижнем квадратике, чтобы попасть в правый верхний квадратик, всли:
1. Он переходит на соседний квадратик только по вертикали или горизонтали?
2. Он двигается согласно шахматным правилам?
3. Пусть a и b нечётные числа, тогда имеется центральный квадратик.
Какова вероятность, что маршрут короля пройдёт через центр?
Примечание: каждый ход короля должен приближать его к цели.

[jetyb]

Представьте себе прямую нить с бусинками и вспомните про сочетания.

[VAL]

tess в сообщении #462662 писал(а):

Пусть шахматная доска представляет собой прямоугольник длиной a и шириной b квадратиков (при a = b = 8 имеем обычную шахматную доску).
Сколько различных маршрутов имеет шахматный король, стоящий в левом нижнем квадратике, чтобы попасть в правый верхний квадратик, всли:
1. Он переходит на соседний квадратик только по вертикали или горизонтали?

Здесь уже ответили.
Хотя, мне кажется, более понятно другое объяснение:
Сколько всего ходов надо сделать?
Сколько из них по горизонтали?
Верно ли, что маршрут однозначно определен номерами горизонтальных ходов?

Цитата:

2. Он двигается согласно шахматным правилам?

А этот вопрос весьма странный!
Зато ответ очевиден: бесконечно много.

PS: Увидел примечание. Тогда причем здесь шахматные правила?
Полагаю, и в этом случае сформулирована не совсем та задача, которую имел в виду составитель. Например, на обычной доске ход с поля f8 на поле g7 приближает короля к полю h8. Но, мне кажется, имелись в виду лишь ходы: на одну клетку вправо; на одну клетку вверх; на одну клетку вправо и вверх по диагонали.

Если так, рассмотрите отдельно случаи:
без диагональных ходов;
с одним диагональным ходом;
. . . . . . . . . . . . . . .
с $\min(a,b)$ диагональных ходов.

В каждом случае определитесь с номерами диагональных, а затем горизонтальных ходов (из множества оставшихся).

[tess]

"Но, мне кажется, имелись в виду лишь ходы: на одну клетку вправо; на одну клетку вверх; на одну клетку вправо и вверх по диагонали".
В пункте 1. имеются ввиду ходы на одну клетку вправо или на одну клетку вверх.
В пункте 2., кроме указанных в пункте 1. ходов, возможны также ходы на одну клетку вправо и вверх по диагонали.
Что касается замечания "с одним диагональным ходом" и т.д., то все маршруты с
одним диагональным ходом, с двумя диагональными ходами и т.д. входят в число маршрутов по пункту 2. (естественно , они будут различными).
. . . . . . . . . . . . . . .

[VAL]

tess в сообщении #463082 писал(а):

"Но, мне кажется, имелись в виду лишь ходы: на одну клетку вправо; на одну клетку вверх; на одну клетку вправо и вверх по диагонали".
В пункте 1. имеются ввиду ходы на одну клетку вправо или на одну клетку вверх.

Здесь все очевидно, включая ответ, который Вы пока так и не предъявили, несмотря на подсказки.

Цитата:

В пункте 2., кроме указанных в пункте 1. ходов, возможны также ходы на одну клетку вправо и вверх по диагонали.

Я тоже думаю, что это имелось в виду. Но если следовать букве условия, допустимыми являются также ходы вправо и вниз из клеток выше диагонали, и ходы влево и вверх из клеток ниже диагонали.
Различия существенны. Если не рассматривать ходов последних двух типов то на доске $5\times 5$ будет 321 маршрут (общая формула легко выводится).
Если же учитывать ходы влево вверх и вправо вниз, маршрутов будет уже 1130. Разница, однако!

Цитата:

Что касается замечания "с одним диагональным ходом" и т.д., то все маршруты с
одним диагональным ходом, с двумя диагональными ходами и т.д. входят в число маршрутов по пункту 2. (естественно , они будут различными).
. . . . . . . . . . . . . . .

Это я расписал, чтобы было понятнее, как подобраться к общей формуле.

[tess]

Отвечаю на все вопросы
Ходы только вверх и вправо. Для квадрата 5 на 5 требуется 8 ходов, 4 вверх и 4 вправо. Поэтому ответ: имеется C(8,4) = 70 различных маршрутов.
Если король может двигаться ещё и по диагонали, то ответ тоже прост:
C(8,4) + C(7,3)C(4,1) (один косой ход)+ C(6,2)C(4,2) (два косых хода)+
+C(5,1)C(4,3) (три косых хода)+ C(5,0)C(4,4) (все ходы косые) =
= 70+140+90+20+1 = 321.
Ваше замечание о косых ходах справа налево ниже диагонали противоречит условию, что ходы должны приближать короля к цели. Что касается косых ходов выше диагонали, то в примечании имело бы смысл записать, что король должен двигаться наиболее коротким путём. Тогда с поля f8 к цели вели бы только ходы f8 - g8 - h8, и не было бы косого хода f8 - g7.
Рассмотрим, например, прямоугольник 3 на 7, т.е. 2 хода вверх и 6 направо.
Тогда число маршрутов C(8,2)C(8,6) = 28 (косвенное доказательство того, что
C(a,b) = C(a,a – b).
С косыми ходами получим 85 маршрутов.
На примере квадрата 5 на 5 рассмотрим вопрос с центральным полем. Для того, чтобы туда попасть, имеется 13 маршрутов (для ответа достаточно рассмотреть отдельно квадрат 3 на 3). Тогда к цели через центральное поле ведут 13^2 = = 169 маршрутов, а в обход его 321–169 = 152 маршрута. Искомую в 3. вероятность теперь легко вычислить.

[VAL]

tess в сообщении #463512 писал(а):

Отвечаю на все вопросы
Ходы только вверх и вправо. Для квадрата 5 на 5 требуется 8 ходов, 4 вверх и 4 вправо. Поэтому ответ: имеется C(8,4) = 70 различных маршрутов.
Если король может двигаться ещё и по диагонали, то ответ тоже прост:
C(8,4) + C(7,3)C(4,1) (один косой ход)+ C(6,2)C(4,2) (два косых хода)+
+C(5,1)C(4,3) (три косых хода)+ C(5,0)C(4,4) (все ходы косые) =
= 70+140+90+20+1 = 321.

Угу.

Цитата:

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

Не противоречит. По крайней мере, в геометрическом смысле. Найдите соответствующие расстояния между центрами клеток. Если же понимать расстояние в смысле метрики, порождаемой ходами шахматного короля, то и ходы по вертикали (горизонтали) на квадратной доске не приближают короля к цели.

Цитата:

Что касается косых ходов выше диагонали, то в примечании имело бы смысл записать, что король должен двигаться наиболее коротким путём. Тогда с поля f8 к цели вели бы только ходы f8 - g8 - h8, и не было бы косого хода f8 - g7.

Не спасает. Тогда на квадратной доске король должен идти к цели строго по диагонали. И на поле f8 не может оказаться в принципе.
В общем, либо задача хитрая (ходы "влево-вверх" и "вправо-вниз" с определенных полей надо учитывать), либо небрежно сформулирована.
Склоняюсь ко второму варианту.

Цитата:

Рассмотрим, например, прямоугольник 3 на 7, т.е. 2 хода вверх и 6 направо.
Тогда число маршрутов C(8,2)C(8,6) = 28 (косвенное доказательство того, что
C(a,b) = C(a,a – b).
С косыми ходами получим 85 маршрутов.
На примере квадрата 5 на 5 рассмотрим вопрос с центральным полем. Для того, чтобы туда попасть, имеется 13 маршрутов (для ответа достаточно рассмотреть отдельно квадрат 3 на 3). Тогда к цели через центральное поле ведут 13^2 = = 169 маршрутов, а в обход его 321–169 = 152 маршрута. Искомую в 3. вероятность теперь легко вычислить.

Угу.