Маршруты на плане города 5×10 — олимпиадная задача по комбинаторике
План города имеет схему, представляющую собой прямоугольник 5×10 клеток. На улицах введено одностороннее движение: разрешается ехать только вправо и вверх. Сколько есть различных маршрутов, ведущих из левого нижнего угла в правый верхний?
Показать ответ
3003 маршрута.
Разобрать решение
Каждому маршруту можно сопоставить строку из 15 букв "П" и "В" (см. подсказку), причём букв "П" должно быть ровно 5, а букв "В" – ровно 10. Наоборот, по каждой такой строке букв можно однозначно восстановить маршрут. Поэтому число маршрутов равно числу таких строк, которое, в свою очередь, равно 
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.