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

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

Руководители Дмитрий Владимирович Трущин и Михаил Владимирович Шеблаев
2012/2013 учебный год

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

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

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

1.

К задаче 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.

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

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

К задаче 4
Указание. Найдите сначала количество способов добраться от 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.

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

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

К задаче 7
8.

К задаче 8
9.

К задаче 9

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter! Rambler's Top100
liveinternet.ru
Apache
PHP
HTML 4.01
CSS