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

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

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

1.

а)

Из города А в город Б есть 5 дорог, из Б в город В — 9 дорог, а из В в А — 5 дорог. Сколькими способами можно проехать по маршруту А-Б-В-А ?

б)

В гардеробе есть 5 шляп, 9 курток и 5 зонтиков. Сколькими способами злоумышленник может выбрать себе полный комплект?

в)

Злоумышленник пытается взломать кодовый замок сейфа. Из надёжных источников ему стало известно, что это чётное трёхзначное число, вторая цифра которого нечётна. Сколько попыток ему потребуется, чтобы взломать сейф?

2.

Сколько разных слов (не только осмысленных) можно получить, переставляя буквы в словах а) РОК; б) КУРОК; в) ПОРОШОК; г) КОЛОБОК; д)

3.

Сколькими способами можно поселить 7 студентов в три комнаты: одноместную, двухместную и четырехместную?

4.

а)

Фабрика игрушек выпускает разноцветные треугольные пирамидки (одного размера). У каждой пирамидки 4 равносторонние грани: жёлтая, красная, синяя и зелёная. Сколько разных видов пирамидок может выпускать эта фабрика?

б)

Тот же вопрос, если фабрика выпускает кубики (одного размера) с жёлтой, красной, синей, зелёной, белой и чёрной гранями.

5.

а)

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

б)

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

6.

Найдите коэффициенты при x¹⁷ и x¹⁸ после раскрытия скобок и приведения подобных членов в выражении (1 + x⁵ + x⁷)²⁰.

7.

Для каждого двузначного числа берем произведение его цифр, а затем все эти произведения, вычисленные для всех двузначных чисел, складываем. Сколько получится? А для трёхзначных? N-значных? (Пояснение: берется произведение всех цифр числа, так что если хотя бы одна из цифр — ноль, то и произведение — ноль.)

* * *

8.

Сколькими способами можно разбить m + n + p предметов на три группы так, чтобы в одной было m, в другой — n, а в третьей — p предметов?

9.

Человек начинает свое движение от фонаря посреди улицы, делая шаги равной длины вправо или влево. Предположим, что всего он сделал N шагов.

а)

Сколькими способами человек может оказаться в m шагах от фонаря справа?

б)

Допустим, этот человек каждый раз определял, в какую сторону ему пойти, броском монеты. С какой вероятностью он окажется в m шагах от фонаря справа?

10.

Тетраэдр (треугольную пирамиду) разрезали на несколько частей. Каждый разрез проходил через одно из рёбер и центр тетраэдра (всего получилось 6 разрезов). На сколько частей разрезался тетраэдр?

11.

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