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

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

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

Всюду идут дороги, или ещё немного комбинаторики (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


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

ГЛАВНАЯ СТРАНИЦА НАША КОМАНДА О КРУЖКАХ РАСПИСАНИЕ ВОПРОС-ОТВЕТ ЛЕКЦИИ МАТЕРИАЛЫ ЗАНЯТИЙ 5 класс 6 класс 7 класс 8 класс Перечневые олимпиады 2-3 уровень АРХИВ МАЛЫЙ МЕХМАТ — ШКОЛЕ ЛИТЕРАТУРА ССЫЛКИ	Кружок 5 класса Руководители Дмитрий Владимирович Трущин и Михаил Владимирович Шеблаев 2012/2013 учебный год Всюду идут дороги, или ещё немного комбинаторики (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	ЗАДАЧИ 5 класс Плюс-минус один Обратный ход Посчитай-ка Скобки и знаки Рыцари и лжецы Движение Движение (доп. задачи) Факториал Комбинаторика (доп. задачи) Математическая абака Комбинаторика Козы Переливания Предновогодний Оливье Математическая карусель Всюду идут дороги Разные задачи Разрезалки Круги Эйлера Принцесса или тигр Магические фигуры Двумя способами Конструкции ЗАДАЧИ ауд. П3 (рук. Л. А. Попов)