Страница 116 номер 226, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Муха ползёт из точки \(A\) в точку \(B\) по рёбрам решётки размером:
а) \(4 \times 4\) (рис. 109); б) \(5 \times 4\); в) \(7 \times 6\).
Сколько кратчайших маршрутов у мухи?
Вершина \(A\) стоит в левом верхнем углу решётки, вершина \(B\) — в правом нижнем. Путь кратчайший тогда и только тогда, когда каждый шаг ведёт вправо или вниз: шаг влево или вверх пришлось бы возмещать обратным шагом.
Пометим шаг вправо цифрой 1, шаг вниз — цифрой 0. Тогда каждый маршрут получает свою бинарную последовательность, и обратно — каждой такой последовательности отвечает ровно один маршрут.
а) В решётке \(4 \times 4\) надо пройти 4 клетки вправо и 4 клетки вниз, маршрут состоит из \(4 + 4 = 8\) рёбер, а его код — последовательность из 4 единиц и 4 нулей: \[C_8^4 = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4!} = \frac{1680}{24} = 70.\]
Проверка: сосчитаем маршруты по узлам. В каждый узел верхнего ряда и левого столбца ведёт ровно один кратчайший маршрут — по прямой; в любой другой узел маршрут приходит либо сверху, либо слева, поэтому маршрутов в него столько, сколько их в соседнем узле сверху и в соседнем узле слева вместе.
В узле \(B\) стоит число 70 — столько же, сколько дала формула.
б) В решётке \(5 \times 4\) надо пройти 5 клеток вправо и 4 клетки вниз, маршрут состоит из \(5 + 4 = 9\) рёбер, а его код — последовательность длины 9 из 5 единиц и 4 нулей; задать её — то же самое, что выбрать 4 места для нулей: \[C_9^4 = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4!} = \frac{3024}{24} = 126.\]
в) В решётке \(7 \times 6\) надо пройти 7 клеток вправо и 6 клеток вниз, маршрут состоит из \(7 + 6 = 13\) рёбер, а его код — последовательность длины 13 из 7 единиц и 6 нулей, то есть выбор 6 мест для нулей: \[\begin{aligned} &C_{13}^6 = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{6!} = {} \\ &= \frac{1\,235\,520}{720} = 1716. \end{aligned}\]
Ответ: а) 70 кратчайших маршрутов; б) 126 кратчайших маршрутов; в) 1716 кратчайших маршрутов.
Муха ползёт из точки \(A\) в точку \(B\) по рёбрам решётки размером:
а) \(4 \times 4\) (рис. 109); б) \(5 \times 4\); в) \(7 \times 6\).
Сколько кратчайших маршрутов у мухи?
Решётка размером \(4 \times 4\) — это 4 клетки в ширину и 4 клетки в высоту; вершина \(A\) стоит в левом верхнем углу, вершина \(B\) — в правом нижнем. Муха ползёт по рёбрам, и её путь будет кратчайшим тогда и только тогда, когда каждый шаг приближает её к \(B\), то есть ведёт вправо или вниз: шаг влево или вверх пришлось бы потом возмещать обратным шагом.
Чтобы попасть из левого верхнего угла в правый нижний, надо пройти 4 клетки вправо и 4 клетки вниз. Значит, любой кратчайший маршрут состоит из \(4 + 4 = 8\) рёбер: 4 ребра вправо и 4 ребра вниз, а различаются маршруты только порядком этих шагов.
Дадим маршруту цифровой код: шаг вправо пометим цифрой 1, шаг вниз — цифрой 0. Тогда каждый кратчайший маршрут получает последовательность из 4 единиц и 4 нулей, и обратно — каждой такой последовательности отвечает ровно один маршрут. Количество бинарных последовательностей длины 8, состоящих из 4 единиц и 4 нулей, равно \(C_8^4\).
а) Решётка \(4 \times 4\), маршрут из 8 рёбер: \[C_8^4 = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4!} = \frac{1680}{24} = 70.\]
Проверка: сосчитаем маршруты ещё раз, по узлам. В каждый узел верхнего ряда и в каждый узел левого столбца ведёт ровно один кратчайший маршрут — по прямой. В любой другой узел кратчайший маршрут приходит либо сверху, либо слева, поэтому маршрутов в него столько, сколько их в соседнем узле сверху и в соседнем узле слева вместе. Отметим эти числа в узлах решётки.
В узле \(B\) стоит число 70 — столько же, сколько дала формула.
б) Решётка \(5 \times 4\): надо пройти 5 клеток вправо и 4 клетки вниз, поэтому маршрут состоит из \(5 + 4 = 9\) рёбер, а его код — последовательность длины 9 из 5 единиц и 4 нулей. Задать такую последовательность — то же самое, что выбрать 4 места для нулей: \[C_9^4 = \frac{9 \cdot 8 \cdot 7 \cdot 6}{4!} = \frac{3024}{24} = 126.\]
в) Решётка \(7 \times 6\): надо пройти 7 клеток вправо и 6 клеток вниз, поэтому маршрут состоит из \(7 + 6 = 13\) рёбер, а его код — последовательность длины 13 из 7 единиц и 6 нулей. Задать её — то же самое, что выбрать 6 мест для нулей: \[\begin{aligned} &C_{13}^6 = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{6!} = {} \\ &= \frac{1\,235\,520}{720} = 1716. \end{aligned}\]
Ответ: а) 70 кратчайших маршрутов; б) 126 кратчайших маршрутов; в) 1716 кратчайших маршрутов.
