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

Кружок 9-11 классов

Комбинаторика-1.1 (1 октября 2011 года)

Если задача не получается, то попробуйте решить её для меньших чисел, это очень часто помогает. К примеру, посмотреть, что получится в задаче 2а для двух или трёх пар.

1.

Имеются три волчка с 6, 8 и 10 гранями соответственно, грани каждого пронумерованы.

а)

Сколькими различными способами они могут упасть?

б)

Эти три волчка закручиваются одновременно. Сколькими способами можно «провалить» бросок: получить хотя бы две «1»?

2.

На университетский бал пришли 40 юношей и 40 девушек.

а)

Сколькими способами они могут разбиться на пары?

б)

Сколькими способами они могут станцевать контрданс в 4 колонны по 10 пар? Порядок пар в колонне важен.

в)

А если все пары в колоннах всё равно перепутаются, и поэтому порядок внутри колонн не важен?

г)

Сколькими способами можно собрать отдельный сет (сет — это маленькая колонна из нескольких пар) из 4 пар? Порядок пар важен.

3.

В деревне Пастушково, вдали от МГУшных балов, 10 юношей и 10 девушек водят хоровод. При этом девушки и юноши чередуются — каждый держится за руки с представителем противоположного пола. Сколько разных хороводов может получиться?

* * *

4.

а)

Имеется клетчатый квадратный лист бумаги размера n×n. В левом нижнем углу сидит кузнечик. Кузнечик может прыгать на одну клетку вверх или вправо. Сколькими способами он может допрыгать до противоположного угла?

б)

Тот же вопрос про кузнечика в клетчатом кубе.

5.

В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить там: а) n различных открыток при n = 2; n = 3; n = 5; n = 9? б) 2 открытки, не обязательно разные? 3 открытки? 10?

6.

а)

В заборе 20 досок, каждую надо покрасить в синий, зелёный или жёлтый цвет, причём соседние доски красятся в разные цвета. Сколькими способами это можно сделать?

б) А если требуется, чтобы хоть одна из досок обязательно была синей?

7.

Сколько среди чисел от 100 до 10000 таких, в записи которых есть ровно 3 одинаковые цифры?

8.

На окружности отмечены десять различных точек. Сколько можно провести незамкнутых несамопересекающихся ломаных с вершинами во всех этих точках?

Hint

Hint. Порисуйте такие ломаные.

9*.

Сколько пар пересекающихся диагоналей есть в n-угольнике? (Пересечение по вершине не считается.)

10*.

«Чёртово колесо» состоит из p одинаковых кабинок (p — простое число). Каждую кабинку можно покрасить в один из n цветов. Сколько есть способов раскраски?