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

комбинаторная задача, задача с перестановками, задача на графы

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

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

Ответ

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

Мартин Гарднер в своей книге "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.

О задаче

Похожие задачи

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

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

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

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

Занимательные задачи

Ещё больше занимательных задач собрано в следующих разделах: