МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Версия для печати

Всюду идут дороги, или еще немного комбинаторики (9 февраля 2013 года)

В каждой задаче нужно найти число способов добраться от города A до города Z.

1.

Решение

Решение. Для каждого из 4 способов добраться от A до B есть 3 способа добраться дальше от B к Z. Значит, чтобы найти общее число способов добраться от A до Z, нужно сложить 4 способа добраться от A до Z, используя первую дорогу на промежутке от B до Z, 4 способа добраться от A до Z, используя вторую дорогу на промежутке от B до Z, и также 4 способа для третьей дороги на промежутке от B до Z: 4 + 4 + 4 = 3 · 4 = 12.
Таким образом, чтобы найти количество способов добраться до Z, нужно умножить количество способов добраться до предыдущего города на количество дорог от него до Z.

2.

Решение

Решение. Добраться до C можно 12 способами (по предыдущей задаче), для каждого из которых будет по 2 способа добраться дальше до Z, то есть всего 12 · 2 = 24 способа.

3.

Ответ Указание

Ответ. 34

Указание. Добираться до Z можно либо через C, либо через E. Посчитайте количество тех и других способов отдельно (то есть задача распадается на две задачи, похожие на предыдущие).

4.

Ответ Указание Указание 2

Ответ. 64

Указание. Найдите сначала количество способов добраться от A до городов, связанных только с ним непосредственно; затем посчитайте количество способов добраться от A до городов, связанных с этими городами, и так далее, находите число способов добраться от A до каждого из городов, пока не дойдете до Z. При этом, если в город ведут дороги из нескольких разных городов, то нужно посчитать количество способов добраться до него через каждый из этих городов по отдельности, как в предыдущей задаче.

Указание 2.

Например, сначала легко посчитать число способов добраться от A до B и до D (4 и 1 способ соответственно).

После этого уже можно посчитать число способов добраться от A до F. Попасть в F можно либо по дороге из A сразу (1 способ), либо по дороге из B, либо по дороге из D. Число способов добраться до F, попав в него по дороге из B, равно произведению числа способов добраться до B (4 способа) на число дорог от B до F (1 штука). Аналогично, число способов добраться до F, попав в него по дороге из D, равно произведению числа способов добраться до D (1 способ) на число дорог от D до F (1 штука). Итак, в F можно добраться 1 + 4 · 1 + 1 · 1 = 6 способами.

Теперь можно найти число способов добраться до C. Любой путь приходит в C либо по дороге из B (таких путей, очевидно, 4 · 3 = 12), либо по дороге из F (число таких путей равно произведению числа способов добраться сначала до F (а их 6) на число дорог (то есть 1) и равно 6). Обратите внимание, что здесь мы разделяли способы на группы по последнему городу (городу, из которого мы непосредственно по дороге попали в нужный нам C). То есть все 4 способа вида ABFC не являются способами попасть в C из B непосредственно, поэтому они были учтены ровно по одному разу — среди 6 способов попасть в C дорогой из F (вместе с 2 способами AFC и ADFC).

5.

Ценное указание Ответ

Ценное указание. Заметим, что мы движемся всегда либо вниз, либо вправо. Значит, движение можно записать в виде последовательности действий "Н" и "П", причем, поскольку в итоге, чтобы прийти в Z, нужно опуститься ровно 4 раза и ровно 5 раз пойти вправо, то в этих последовательностях всегда будет по 4 "Н" и по 5 "П". Разные способы отличаются только порядком следования этих букв в последовательности. Значит, достаточно найти число таких последовательностей, то есть число способов расставить 4 одинаковые буквы "Н" на 4 + 5 = 9 мест (Если у вас это не получается, посмотрите Доп. задачи по комбинаторике).

Ответ. 126

6.

Ответ Указание

Ответ. 63

Указание. Здесь аналогия с последовательностями неудобна, так как длина пути может быть разной. Однако можно находить количества способов добраться от A до каждого города, начиная с соединенных непосредственно с A и постепенно доходя до Z, как в задаче ?4, при этом пользуясь симметрией.

7.

Ответ

Ответ. 60

8.

Ответ

Ответ. 119

9.

Ответ

Ответ. 28527