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

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

Занятие 5. Комбинаторика–2

1.

Сколько среди первых 2013 натуральных чисел таких, в записи которых встречаются хотя бы три одинаковые цифры?

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

Ответ. 47.

Решение. Аккуратно перебираем все варианты. Трёхзначных чисел из трёх одинаковых цифр будет 9: 111, 222, ..., 999. Теперь считаем четырёхзначные числа. Чисел с тремя нулями среди первых 2013 чисел две штуки: это 1000 и 2000. Чисел, в которых ровно три единицы, будет 3·9 = 27. В самом деле, есть три способа выбрать, где будет стоять не единица (на первом месте в этих числах обязательно будет стоять единица, иначе получится число больше 2013), и при каждом способе этого выбора есть по 9 способов выбрать четвёртую цифру, не равную единице (0, 2, 3, ..., 9). И ещё есть 9 чисел, в которых на первом месте стоит единица, а остальные три цифры одинаковы: 1111, 1222, ..., 1999 (а число 1000 мы уже учли). Итого получаем 9 + 2 + 27 + 9 = 47 чисел.

2.

а)

Сколькими способами можно сделать из лент шести разных цветов трёхцветный горизонтальный флаг?

б)

А если на флаге обязательно должен быть красный цвет?

в)

А если цветов на флаге может быть меньше трёх, но рядом полосы одинаковых цветов стоять не должны? (Флаги, отличающиеся друг от друга переворотом, считаем разными.)

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

Ответ. а) 120; б) 60; в) 150.

Решение.

а) Цвет верхней полосы можно выбрать шестью способами. При каждом способе такого выбора остаётся по пять способов выбрать цвет средней полосы (чтобы он не совпадал с цветом верхней полосы). Наконец, при каждом способе выбора цветов верхней и средней полос остаётся по четыре способа выбрать цвет для нижней полосы (чтобы он не совпадал с цветами первых двух полос). Итого получаем 6·5·4 = 120 способов.

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

в) Сначала посчитаем количество флагов, в которых используется строго меньше трёх цветов. Одноцветным такой флаг быть не может (иначе три одноцветные полосы шли бы подряд, а это запрещено условием). Значит, он может быть только двухцветным, причём верхняя и нижняя полоса должны быть покрашены в один и тот же цвет, а средняя — в другой. Покрасить верхнюю и нижнюю полосы можно шестью разными способами, после этого среднюю полосу можно покрасить (в другой цвет) пятью способами. Итого получаем 6·5 = 30 флагов, в которых используется строго меньше трёх цветов. А теперь к этому числу надо добавить число трёхцветных флагов, которое мы нашли в пункте а). Итого получим 120 + 30 = 150 флагов.

3.

На полке у Вовочки стоят 7 книжек про Гарри Поттера и 4 различных учебника. Собирая портфель, он выбирает с полки 6 книг, из них не менее двух учебников. Сколько способов у Вовочки собрать портфель?

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

Ответ. 371.

Решение.

Посчитаем отдельно количество способов собрать портфель, взяв 2, 3 и 4 учебника соответственно, а затем сложим эти три числа.

Если Вовочка берёт ровно два учебника, то он берёт 4 книги про Гарри Поттера. Число способов выбрать два учебника из четырёх равно C₄² = 4·3 : 2 = 6 (вспомните предыдущее занятие). А число способов выбрать четыре книги про Гарри Поттера из семи равно C₇⁴ = C₇³ = 7·6·5 : (3·2·1) = 35 (здесь мы воспользовались результатами первых двух задач предыдущего занятия). Значит, число способов положить в портфель два учебника и четыре книги про Гарри Поттера равно 6·35 = 210.

Аналогично считается количество способов положить в портфель три учебника и три книги про Гарри Поттера (оно равно C₄³·C₇³ = C₄¹·C₇³ = 4· 35 = 140) и количество спобов положить в портфель четыре учебника и две книги про Гарри Поттера (оно равно C₄⁴·C₇² = 1· 7·6 : 2 = 21).

Итого у Вовочки есть C₄²· C₇⁴ + C₄³· C₇³ + C₄⁴· C₇² = 210 + 140 + 21 = 371 способ собрать портфель.

4.

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

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

Ответ. 15 способами.

Решение. Сначала поставим между каждыми двумя тиграми по льву (Т Л Т Л Т Л Т), чтобы два тигра точно не шли друг за другом. Осталось куда-то пристроить ещё двух львов. Тигры делят шеренгу зверей на 5 частей, в каждую из которых можно поместить любое число из оставшихся львов. Грубо говоря, этих двух львов надо «разложить» по пяти коробкам, «перегородками» между которыми служат тигры. То есть на 6 мест надо расставить двух львов и 4 «перегородки», а для этого есть C₆² = 6·5 : 2 = 15 способов. (Здесь мы из шести мест выбирали те два, на которых окажутся львы.)

5.

Сколько способов набрать сумму:

а)

в 20 рублей;

б)

в 200 рублей монетами в 1, 2 и 5 рублей?

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

Ответ. а) 29; б) 2081.

Решение.

Сначала будем выбирать количество используемых пятирублёвых монет, затем — количество используемых двухрублёвых монет, а оставшуюся сумму (если она ещё ненулевая) будем добирать рублёвыми монетами.

а) Если использовать четыре пятёрки, то другие монеты уже не нужны, и получаем один способ. Если использовать три пятёрки, то останется добрать ещё 20 − 5·3 = 5 рублей, и можно использовать 0, 1 или 2 двойки (3 двойки — это уже 6 рублей, то есть слишком много) — ещё три способа. Если использовать две пятёрки, то останется добрать ещё 20 − 5·2 = 10 рублей, и можно использовать от 0 до 5 двоек — ещё 6 способов. Если использовать одну пятёрку, то останется добрать ещё 20 − 5·1 = 15 рублей, и можно использовать от 0 до 7 двоек — ещё 8 способов. Наконец, если пятёрки вообще не использовать, то двоек можно использовать от 0 до 10 — ещё 11 вариантов. Итого получим 1+3+6+8+11 = 29 вариантов.

б) Рассуждая аналогично предыдущему пункту, получим сумму 1 + 3 + 6 + 8 + ... + 93 + 96 + 98 + 101 = (1 + 6 + 11 + ... + 96 + 101) + (3 + 8 + 13 + ... + 93 + 98) = 1071 + 1010 = 2081. (О том, как легко посчитать такие суммы, можно прочесть в решениях задач прошлогоднего занятия по теме «Последовательности» для 6 класса: ).

6.

Сколько способов нанизать 15 различных бусинок на спицу? Способы, отличающиеся переворотом спицы, считаем различными.

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

Ответ. 15! = 1·2·3·...·15.

Решение. Будем нанизывать бусинки на спицу по очереди. Первой можно нанизать любую из 15 бусинок, после этого второй — любую из оставшихся 14, после этого третьей — любую из оставшихся 13, ..., пятнадцатой — только одну оставшуюся в самом конце. Итого способов нанизвать 15 бусинок на спицу будет 1·2·3·...·15 = 15!.

7.

Сколько способов составить из 15 различных бусинок браслет, если:

а)

одинаковые браслеты — это те, которые отличаются друг от друга поворотом;

б)

одинаковые браслеты — это те, которые отличаются друг от друга поворотом или переворотом?
Подсказка. Если браслет разрезать в каком-нибудь месте и выпрямить, получится «спица» из предыдущей задачи. Сколько разных «cпиц» с бусинками можно получить из одного браслета с бусинками, разрезая его в разных местах?

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

Ответ. а) 14! = 1·2·3·...·14; б) 14! : 2.

Решение. Из каждого браслета длиной 15 бусинок можно, разрезая его в разных местах и разгибая, получить 15 разных «спиц» из предыдущей задачи. Поэтому в пункте а) браслетов в 15 раз меньше, чем спиц в предыдущей задаче, то есть 15! : 15 = 1·2·3·...·14 = 14!. В пункте б), когда браслеты можно ещё и переворачивать, все браслеты из пункта а) разбиваются на пары, и браслеты в каждой паре переходят друг в друга при переворачивании. Таких пар вдвое меньше, чем браслетов в пункте а), то есть 14! : 2.

8.

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

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

Ответ. 2880 способами.

Решение. В этом задаче нам важно только то, как гости рассажены относително друг друга. Зафиксируем место, на котором сидит один из мужчин, а остальных гостей рассадим относительно него. Тогда по часовой стрелке от него надо посадить: Ж М Ж М Ж М Ж М Ж (чтобы никакие двое мужчин и никакие две женщины не сидели рядом). Теперь надо рассадить четырёх оставшихся мужчин по 4 местам (для этого есть 4! = 24 способа — по аналогии с задачей 6) и 5 женщин — по 5 местам (для этого есть 5! = 120 способов). Сделать и то, и другое одновременно можно 4!·5! = 2880 способами.

9.

На почте имеется по одному виду марок каждого номинала (в 1, 2, 3 рубля и т.д.). Сколькими способами можно наклеить в ряд несколько марок,чтобы их суммарная стоимость равнялась 25 рублям?

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

Ответ. 2²⁴.

Решение. Запишем в ряд 25 единиц. Между некоторыми из них поставим перегородки. Они разделяют разные «марки». Например, запись 1 | 1 1 1 | 1 ... 1 (после второй перегородки ещё 21 единица, и других перегородок нет) означает три марки стоимостью, соответственно, 1, 3 и 21 рубль. Между 25 единицами 24 промежутка, и в каждый можно поставить или не поставить перегородку. Поэтому способов расставить перегородки, а равно и способов наклеить марки, будет 2²⁴.