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

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

Занятие 10. Комбинаторика

1.

В корзине сидят котята — четыре чёрных, шесть рыжих и два белых. Сколькими способами можно выбрать трёх котят так, чтобы они все были разной окраски? Котята одного цвета друг от друга отличаются!

Ответ Решение

Ответ. 48

Решение. Надо выбрать одного чёрного котёнка, одного рыжего и одного белого. Чёрного котёнка можно выбрать одним из четырёх способов. Для каждого способа выбрать чёрного котёнка есть по шесть способов выбрать рыжего котёнка. Для каждого способа выбарть чёрного и рыжего котёнка есть по два способа выбрать белого котёнка. Итого получаем 4·6·2 = 48 способов.

2.

В языке аборигенов далекого острова 10 прилагательных, 20 существительных и 15 глаголов. Предложением называется всякое сочетание либо существительного и глагола, либо прилагательного, существительного и глагола (порядок слов в предложении всегда именно такой). Сколько всего предложений в этом языке?

Ответ Решение

Ответ. 3300

Решение.

Сначала сосчитаем количество предложений, состоящих только из существительного и глагола. Существительное можно выбрать одним из 20 способов. Для каждого способа выбрать существительное есть по 15 способов выбрать глагол. Поэтому таких предложений будет 20·15 = 300.

Теперь сосчитаем количество предложений, состоящих прилагательного, существительного и глагола. Прилагательное можно выбрать одним из 10 способов. Для каждого способа выбрать прилагательное есть по 20 способов выбрать существительное. Для каждого способа выбрать прилагательное и существительное есть по 15 способов выбрать глагол. Поэтому таких предложений будет 10·20·15 = 3000. А всего в этом языке будет 300 + 3000 = 3300 предложений.

3.

Корабли, заходя в порт, подают сигналы, поднимая на мачте флаги один над другим. Сколько сигналов можно подать, если есть флаги четырёх цветов, и каждый сигнал подаётся:

а)

двумя флагами;

б)

тремя флагами;

в)

четырьмя флагами?
Порядок флагов важен: они расположены на мачте один над другим.

Ответ Решение

Ответ. а) 16; б) 64; в) 256.

Решение. Цвет первого флага можно выбрать одним из четырёх способов. Для каждого из этих способов есть по четыре способа выбрать цвет второго флага. Поэтому двумя флагами можно подать 4·4 = 16 сигналов. Для каждого способа выбрать первые два флага есть по четыре способа выбрать третий флаг. Поэтому тремя флагами можно подать 4·4·4 = 64 сигнала.

4.

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

Ответ Решение

Ответ. 970200

Решение. Старшая дочь может выбрать себе любого из 100 женихов. В каждом из этих ста случаев средняя дочь сможет выбрать себе только одного из оставшихся 99 женихов. После того, как старшая и средняя дочери сделают свой выбор, младшая дочь сможет выбрать себе одного из оставшихся 98 женихов. Итого они могут сделать свой выбор 100·99·98 = 970200 способами.

5.

На балу собрались 5 дам и 5 кавалеров. Сколькими способами они могут разбиться на пары?

Ответ Решение

Ответ. 32

Решение. Первый кавалер может выбрать себе любую из пяти дам. В каждом из этих пяти случаев второй кавалер сможет выбрать себе любую из оставшихся четырёх дам, затем третий кавалер — любую из оставшихся трёх дам, четвёртый — любую из оставшихся двух дам, и пятый — только одну оставшуюся даму. Таким образом, составить пары можно 5·4·3·2·1 = 120 способами.

6.

Сколькими способами можно выложить в ряд два белых и два черных шарика, если шарики одного цвета считаются одинаковыми?

Ответ Решение

Ответ. 6

Решение. Сначала предположим, что все четыре шарика различаются. Например, напишем на них номера: Ч1, Ч2, Б1 и Б2. Выложить в ряд четыре шарика можно 4·3·2·1 = 24 способами (докажите это самостоятельно по аналогии с предыдущей задачей). Теперь сотрём номера на двух чёрных шариках. Способов выложить шарики в ряд станет в два раза меньше: каждые два способа, отличающиеся только перестановкой чёрных шариков (Ч1 Ч2 и Ч2 Ч1), превратятся в один способ (Ч Ч). Когда мы сотрём номера ещё и на белых шариках, способов выложить шарики в ряд станет ещё вдвое меньше. Таким образом, всего способов станет 24 : 2 : 2 = 6.

7.

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

Ответ Решение

Ответ. 35

Решение. Первую книгу можно выбрать семью способами. В каждом из этих семи случаев вторую книгу можно выбрать шестью способами. При каждом способе выбрать первые две книги есть по пять способов выбрать третью книгу. А теперь заметим, что нам неважно, в каком порядке мы будем покупать книги, а важно только, какие именно книги мы купим. Упорядочить три книги можно шестью способами (докажите это самостоятельно по аналогии с задачей 5). Поэтому способов купить три книги в шесть раз меньше, чем упорядоченных наборов из трёх книг. А таких наборов 7·6·5. Поэтому способов купить три книги будет 7·6·5 : 6 = 35.

8.

У Ивана шесть друзей, и каждый день он приглашает к себе в гости каких-нибудь трёх из них. Может ли он в течение трёх недель каждый день приглашать к себе друзей так, чтобы компании не повторялись?

Ответ Решение

Ответ. Не может.

Решение. Посчитаем количество способов выбрать трёх человек из шести. Таких способов будет 6·5·4 : 6 = 20 (докажите это самостоятельно по аналогии с преыдущей задачей). А три недели — это 21 день. Поэтому хотя бы в какие-то два дня компании будут одинаковыми.

9.

а)

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

б)

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

Ответ Решение

Ответ. б) Нельзя.

Решение.

а) Посчитаем количество возможных наборов оценок по этим предметам. По каждому из трёх предметов можно поставить одну из двух оценок — четвёрку или пятёрку. Для каждого из двух способов поставить оценку по математике есть по два способа поставить оценку по русскому. Для каждого из способов поставить оценки по математике и русскому есть по два способа поставить оценку по английскому. Итого есть 2·2·2 = 8 возможных наборов оценок. Поэтому разные наборы оценок могут получить не более 8 человек.

б) Теперь добавился ещё четвёртый предмет — физкультура. Для каждого из 8 способов поставить оценки по математике, русскому и английскому языку есть по два способа поставить оценку по физкультуре. Итого есть 8·2 = 16 возможных наборов оценок. Так что возможна ситуация, при которой все 16 шестиклассников получат разные наборы оценок по этим предметам.

10.

а)

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

б)

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

Ответ Решение

Ответ. а) 48; б) 46.

Решение.

а) Первую доску можно покрасить в любой из трёх цветов. В каждом из этих трёх случаев вторую доску можно красить в любой из двух оставшихся цветов. Далее, третью доску можно красить в любой из двух цветов (кроме того, в который покрашена вторая доска), и аналогично для четвёртой и пятой доски. Итого 3·2·2·2·2 = 48 способов покрасить забор.

б) Сначала посчитаем число способов покрасить забор, не используя синюю краску. Таких способов всего два: Ж–З–Ж–З–Ж и З–Ж–З–Ж–З. При остальных 48 − 2 = 46 способах покраски хотя бы одна доска будет синего цвета.