Задачка про дорогу.

Человек, который живет в левом верхнем углу прямоугольника, состоящего из городских кварталов (см. рисунок), работает в конторе, находящейся в здании, занимающем правый нижний угол прямоугольника. Легко увидеть, что кратчайший путь, которым человек может добираться до работы, равен 10 кварталам. Но ему скучно ходить каждый день одной и той же дорогой, поэтому он пытается найти разные варианты кратчайшего маршрута. Сколько он сможет найти маршрутов, равных кратчайшему, соединяющих его дом с работой?

Ответ

210

Решение задачи

Мартин Гарднер в своей книге "Mathematical Magic Show" дает следующую подсказку для данной задачи: число комбинаций, или перестановок, N объектов, A из которых одинаковы, а остальные B также одинаковы между собой, равно ^N!_A!×B!. Чтобы найти число различных кратчайших путей из одного угла сетки городских кварталов в диагонально противоположный, нужно учесть, что если длина прямоугольника составляет A кварталов, а ширина - B кварталов, то кратчайший путь из одного угла в другой, диагонально противоположный, равен A + B. Назовем эту сумму N. Любой маршрут длиной N, соединяющий два угла, может быть представлен как цепь из N символов, "A" из них соответствуют кварталам, пройденным по длине, а оставшиеся "B" - кварталам, пройденным по ширине. Если заменить каждый квартал, пройденный по длине, одноцентовой монетой, а по ширине - десятицентовой, тогда число различных вариантов кратчайшего пути можно представить как число различных способов расположения в ряд этих монеток. Каждый отдельный маршрут соответствует способу перестановки N монеток, и наоборот, каждая перестановка монеток соответствует отдельному маршруту. Подсказка для решения этой задачи - формула для числа способов расположения в ряд N объектов, A и B из которых одинаковы между собой. Прямоугольник имеет в длину 6 кварталов, а в ширину - 4. Таким образом, вычисление числа вариантов маршрутов аналогично вычислению числа способов расположения в ряд шести центовых и четырёх десятицентовых монеток. Ответ: ^10!_6!×4! = 210.

О задаче

Категория: Комбинаторика, Задачи с перестановками, Графы,
Степень сложности: сложная.
Ключевые слова: 10, город, дом, дорога, квартал, прямоугольник, работа, улица, человек,
Источник: 1000 развивающих головоломок,

Скачать задачу

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

◄ На предыдущую страницу

Оставить комментарий

Свои вопросы, комментарии, замечания и занимательные задачи присылайте через предложенную ниже форму.

Решите задачу

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

a) Велосипедист будет дальше.
b) Зависит от скорости автобуса и велосипедиста.
c) Автобус будет дальше.
d) Оба будут на одинаковом расстоянии.