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

Кружок 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 способах покраски хотя бы одна доска будет синего цвета.