АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЭЮЯ#
§🔍YouTube канал Занимательные задачи

zadach.net YouTube канал Занимательные задачи

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

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

Человек, который живет в левом верхнем углу прямоугольника, состоящего из городских кварталов (см. рисунок), работает в конторе, находящейся в здании, занимающем правый нижний угол прямоугольника. Легко увидеть, что кратчайший путь, которым человек может добираться до работы, равен 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.

О задаче

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

Список похожих занимательных задач:

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

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

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

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

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

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

Имя: Почта:
Сообщение:

Проверочный код: 2+2×2=   

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

Каждый из двух чайников, изображенны на рисунке, вмещает одинаковое количество воды. Сделаны чайники из одного металла. Площадь дна у обоих равная. С внутренней стороны эти чайники потускнели, а с внешней стороны один блестит - он покрыт никелем,- а второй простой. В каком из этих чайников при одинаковых условиях вода закипает быстрее? В котором горячая вода остынет раньше?

a) Для нагревания лучше чайник с тусклой поверхностью;
b) Для нагревания лучше никелированный чайник.
c) Нет разницы.

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

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

Геометрические задачи
Геометрические задачи
Задачи на разрезание
Задачи на разрезание
Задачи на взвешивание
Задачи на взвешивание
Задачи на переливание
Задачи на переливание
Задачи о переправе
Задачи о переправе
Шахматные задачи
Шахматные задачи


Учительский портал

Энциклопедия занимательных задачSirotaSOFT © 2021 -