Сколько маршрутов?

Из письма школьников: «Занимаясь в математическом кружке, мы вычертили план шестнадцати кварталов нашего города.

На прилагаемой схеме плана (рисунок) все кварталы условно изображены одинаковыми квадратами.
Нас заинтересовал такой вопрос:
Сколько разных маршрутов можно наметить от пункта А к пункту С, если двигаться по улицам нашего города только вперед и вправо, вправо и вперед? Отдельными своими частями маршруты могут совпадать (см. пунктирные линии на схеме плана).
У нас сложилось впечатление, что это нелегкая задача. Верно ли мы ее решили, если насчитали 70 разных маршрутов?»
Что надо ответить на это письмо?

1

Решение:

Непосредственно считать все возможные маршруты от A до С сложно — запутаетесь. Надо начать с подсчета маршрутов до перекрестков, более близких к начальному пункту А (рис. 267).
Очевидно, что в каждый перекресток, находящийся на сторонах АВ и AD, ведет только один путь; в перекресток 2b ведут 2 пути. В перекресток 2с можно попасть, во-первых, из пункта 2b, значит, тоже двумя маршрутами, и, во-вторых, из пункта 1с, то-есть еще одним маршрутом. Следовательно, всего к перекрестку 2с ведут 2 +1 = 3 маршрута (найдите их). Аналогично рассуждая, получим, что и к перекрестку Зb ведут 3 маршрута.
В перекресток Зс ведут те же 3 маршрута, которыми можно попасть в перекресток Зb, и те 3 маршрута, которыми можно попасть в перекресток 2с, то-есть всего 6 маршрутов Продолжая эти рассуждения, заметим, что вообще количество маршрутов, ведущих к любому перекрестку, равно сумме маршрутов, ведущих к двум смежным перекресткам, расположенным слева и снизу от рассматриваемого. Если, например, мы определили, что число маршрутов, ведущих в Зс, равно 6, а в 2d равно 4, то число маршрутов, ведущих в 3d, будет равно 10 и т. д.
Так можно определить число маршрутов, ведущих из начального пункта А к любому перекрестку. К конечному пункту С, таким образом, можно прийти 70 различными путями.

1



Это не спам.

 

На нашем сайте собраны задачи занимательной арифметики, математики, геометрии;
задачи на смекалку и логику, головоломки, логические загадки, игры, ребусы и многое другое
2017 © Самый умный - математическая смекалка