Сколько вариантов?

36

Сколько вариантов?

Здесь продолжается изучение комбинаторовных задач по программе факультатива для IX класса, начато в предыдущем номере.

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

Вычитание и сложение

Задача 1. Сколько имеется четырехзначных чисел, в десятичной записи которых встречаются одинаковые цифры?

Решение. Действия по той же схеме, что и в предыдущей стате, разобъем построение четырехзначного числа на четые шага: выбор первого, второй, третьей, четвертой цифр. На первом шаге у нас 9 возможностей, на втором и третьем шагах — по 10 возможностей. Но число вариантов осуществления четырехзначного шага зависит от результата первых трех шагов: если средние трех цифр были равны, то на четвертом шаге у нас 10 возможностей, если же первые три цифры были различными, то в качестве четырехтий цифры мы обязаны взять одну из этих цифр, и, следовательно, у нас будет на этом шаге лишь три возможности.

Таким образом, правильное произведение не применимо. Не помогет и перестановка шагов: мы все равно встретием с такой же трудностью. Однако вспомним, что в начале предыдущего статы мы решили задачу, противоположную разбиаемой,— нашли число четырехзначных чисел, в которых нет одинаковых цифр. Вычитая это число (оно равно 9·9·8·7=4536) из числа всех четырехзначных чисел (оно равно 9·10·10·10=9000) мы получим, что число четырехзначных чисел, удовлетворяющих условиям задачи, равно 9000—4536=4464.

Упражнения

1. Сколько имеется шестизначных чисел, в записи которых хотя бы одна цифра четна?
2. Сколько имеется перестановок цифр 0, 1, 2,…, 9, в которых хотя бы одна из первых трех цифр делится на 3?
3. Задача 2. Сколько имеется натуральных чисел, меньших 10^5, в десятичной записи которых встречается одинаковые цифры?

Решение. Если разбитить построение такого числа на шаги, на каждом из которых выбирается одна цифра, то для разных чисел число шагов будет разным. Вместе с тем с помощью правил произведения не трудно найти по отдельности число однозначных, двухначных, трехначных, четырехзначных и пятизначных чисел, удовлетворяющих условиям задачи: 9, 9^2, 9^3, 9^4, 9^5. Значит, всего есть 9+9^2+9^3+9^4+9^5=66429 натуральных чисел, меньших 10^5, с различными соседними цифрами.

Упражнения

3. Алфавит состоит из 10 букв. Изовем целочисленное любую последовательность букв этого алфавита, в котором никакая буква не встречается при разраде. Сколько имеется целочек, состоящих не более чем из четырех букв?
4. Сколько имеется шестизначных чисел, в которых четные и нечетные цифры через допуск?
   В задаче 2 и упражнения 3, 4 не удается непосредственно применить правильное произведение. В каждом из этих задач можно逐个

37

Рис. 1.
считываемых предметов удается разбить на несколько частей таким образом, что для подсчета числа элементов в каждой из этих частей уже можно применить правило произведения. Сложив получившееся числа, мы находим решение этих задач.

Задача 3. Сколько имеет перестановок из цифр 0, 1, 2,…, 9, в которых цифра 0 занимает одно из первых шести мест, а цифра 1 — одно из шести последних мест (рис. 1)?

Решение. Если мы сначала выберем место для нуля, затем — место для единиц, а после этого расставим на оставшихся восмины местах остальные восемь цифр, то на втором шаг число возможностей будет зависеть от решения, принято на первом шаг; именно, если на первом шаг мы поставим цифру 0 на одно из первых четырех мест, то место для единиц мы сможем выбрать шестью способами; если цифра 0 займет пятое или шестое место, то для единиц будет лишь пять возможных мест. Поэтому с самого начала разобем множество всех перестановок, удовлетворяющих условиям задачи, на два подмножества: перестановки, в которых цифра 0 занимает одно из первых четырех мест, и перестановки, в которых эта цифра занимает пятое или шестое место. Число элементов в каждой из этих подмножества легко подсчитывается с помощью правил произведения: $4 \cdot 6 \cdot 8! = 24 \cdot 8!$ и $2 \cdot 5 \cdot 8!$. Ответ: $24 \cdot 8! + 10 \cdot 8! = 34 \cdot 8!$.

Упражнения

5. Сколько имеет четырех цифр 0, 1, 2,…, 9, удовлетворяющих условиям задачи?

6. Сколько имеет перестановок цифр 0, 1, 2,…, 9, удовлетворяющих условиям задачи?

6. между цифрами 0 и 1 стоит три другие цифры, а между цифрами 1 и 2 — две другие цифры?

7. Сколько имеет функций f, удовлетворяющих следующим условиям: область определения функций f — множество [1, 2, 3, 4, 5], каждое значение функций f принадлежит множество [1, 2, 3, 4], число f(5) делится без остатка на f(3)?

Деление

Четвертое аргументное действие тоже бывают полезным при решении комбинаторов задач.

Задача 4. Сколько способами можно рассадить 12 целовек за круглым столом, если за столом 12 стульев?

Решение. Число различных расположений 12 целовек на 12 местах, то есть число перестановок этих деревиц целовек, равно 12!, независяимо от того, где эти стулья находятся, — за столом, или у стены, или где-нибудь еще. Зачем в таком случае в задаче отмещается, что стулья стоит именно за круглым столом? В задаче 4 — ни за чем. Но круглый стол позволяет дать естественные «варинарты» задач.

A. Если для каждой целовека важно не место, которое он занимает за столом, а лишь то, кто является его соседом справа и кто является его соседом справа, то два расположения следует отложить, если при переходе от одного из этих расположений к другому у каждой из сидящих за столом не меняется ни соседа, ни соседа.

B. Если для каждой целовека важно лишь то, кто является его соседом (и не важно, кто из этих соседей сидит справа, а кто — слева), то два расположения следует отложить, если каждый из сидящих за столом имеет в обихх случих одних и тех же соседей.

B. Если для каждой целовека важно лишь то, кто сидит на группе нео, то два расположения нужно отложить, если любые два целовека, занимающие диаметрально противоположные места при одном расположении, занимают также диаметрально противоположные места при другом расположении.

Перейдем к варианту A. Разобем все 12! расположений на группы, относая к одной группе те и только те расположения, которые нужно отложить. Число получаемых та-

38

ким образом групп и есть ответ задачи. Чтобы его найти, выясним сначала, сколько расположений оказется в одной группе. Выберем произвольную такую группу и рассмотрим расположения, которые в нее попали. У каждой человека во всех этих расположениях фиксирован сосед справа и сосед слева. Поэтому, чтобы построить произвольное расположение из данной группы, достаточно указыть человека, который займет стул №1 (и в этом варианте задачи, и в вариантах Б и В будем считать, что стулья занутеровны по кругу чисlamи от 1 до 12), после чего места остальных людей определяются уже однозначно. Так как на место №1 можно посадить любого из 12 человек, каждой группа составлена из 12 расположений. Чтобы найти теперь число групп, остается разделить общее число расположений на число расположений в одной группе: $\frac{12!}{12} = 11!$

Разберем теперь вариант Б. И здесь мы разобем все 12! расположений на группы так, чтобы два расположения попали в одну группу в том и только в том случае, когда их нужно отождествить. Выберем какую-нибудь группу и подсчитаем, сколько в ней расположений. Так как у каждой человека в этих расположениях постоянные сосед, произвольное расположение из данной группы можно построить в два шага: сначала выберем человека, который займет стул №1 (12 возможностей), затем решим, кто из двух его соседей займет место №2 (2 возможностей), после чего места остальных десяти человек определяется «по целочке» однозначно. В соответствии с правилами произведения каждой группы состоит из 24 расположений и, следовательно, число групп равно $\frac{12!}{24} = \frac{11!}{2}$.

И, наконец, в варианте B, как и в предыдущих вариантах, сосед, сколько расположений оказалось в одной группе этого варианта. Пусть во всех расположениях из этой группы $A$ должен сидеть направить $A'$, $B$ — направить $B'$, $C$ — направив $C'$, $D$ — направив $D'$, $E$ — направив $E'$, и, наконец, $F$ — направив $F'$. Эти шесть пар человек нужно рассадить на шесть пар стульев: (1, 7), (2, 8), (3, 9), (4, 10), (5, 11) и (6, 12) — по одной паре стульев на каждой пару человек. Построение произвольного расположения из данной группы можно поэтому разбит на семь шагов: сначала расположить 6 пар мест между шестью парами человека (6! возможностей), на втором шаге расположить $A$ и $A'$ на отдельных для них двух местах, на третьем шаге расположить $B$ и $B'$ на отдельных для них местах, и т. д., на следующем шаге — расположить места между $F$ и $F'$. Так как на каждом из шести последних шагов у нас есть по две возможность, в силу правила произведения в данной группе (как и в любой другой) будет $6! \cdot 2^6$ расположений. Искомое число групп равно, следовательно, расположенным, следовательно, расположенным,

$$\frac{12!}{6! \cdot 2^6} = 3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 = 10395.$$

Задача 5. Какдуто из сторона [AB], [BC], [CD], [DA] и диаональ [AC] квадрата ABCD требует okрасить в один из данных пятей цветов, причем все цветы должны использованы. Две раскраски считаются одинаковыми, если одну из других можно получить неотормом перемещением. Сколько имеет различных раскраски?

Решение. Если не обращать внимание на перемещения, то решить о распределении пятей цветов по пятей отрезкам. Таких распределений, очень удобно, 5!. Условие задачи разбивает эти 5! распределений на группы, каждой из которых состоит из всех расположений цветов, определенных цветов, неразличными раскраски. Число этих групп и служит ответом задачи. Найдем, как и преж-

Рис. 2.

39

де, число элементов в одной группе. Это число равно, очевидно, числу различных переменной, которые переводят фигуру, изображенную на рисунке 2, в себя. Так как при каждом таком перемещении диагональ $[AC]$ должна переходить в себя, вершины $A$ и $C$ либо остатся на месте, либо помещаются местами. Для вершин $B$ и $D$ поэтому остатся тоже две возможности: остаться на месте или помещаться местами. Комбинируя каждый из двух вариантов перемещения вершин $A$ и $C$ с каждым из двух вариантов перемещения вершин $B$ и $D$, мы получим четыре различных перемещения: точдественное ($A$ и $C$ остатсь на месте, $B$ и $D$ остатсь на месте), симметрию относительно прямой $BD$ ($A$ и $C$ помещались местами, а $B$ и $D$ остатсь на месте), симметрию относительно прямой $AC$ ($A$ и $C$ остатсь на месте, $B$ и $D$ помещались местами) и композицию этих двух симметрий — симметрию относительно центра квадрата (при этом перемещаются местами как $A$ с $C$, так и $B$ с $D$). Таким образом, каждая группа состоит из четырех элементов и ответом задачи является число $\frac{5!}{4} = 30$.

Уражнения

8. Сколько попарно неконгрузных фигур можно построить из данного правильного $n$-угольника и $n$ кругов попарно различных радиусов, если каждая сторона $n$-угольника должна касаться в своей середине одного и только одного из данных кругов?

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

Задача 6. Сколько имеется шестизначных чисел, в записи которых цифры 1 и 2 встречаются по два раза, а цифры 3 и 4 — no одному разу?

Решение. Шестизначное число, все цифры которого заданы, — это, по существу, перестановка этих шести цифр. Но мы знаем формулу для числа перестановок разли и члены x предметов, в то время как среди цифр рассматриваемых шестизначных чисел есть одинаковые. Чтобы все таки использовать формулу для числа перестановок, будем считать, что у нас есть две разных единиц: 1 и 1 и две разных двойки: 2 и 2, так что ребит о 6! перестановках шестизначных чисел не равно числу таких перестановок, так как некоторые перестановки, например 3 1 2 1 4 2 и 3 1 2 1 4 2, приводят к одному и тому же числу. Две перестановки будут определять одно и то же шестизначное число, если одну из других можно получить, лишь меня местами 1 и 1 или 2 и 2. Мы приходим к знаком сигтизации: все 6! перестановок разбиаются на группы, число которых и есть исключое число шестизначных чисел. Так как в каждой группе четыре перестановки, ответ: $\frac{6!}{4} = 30$.

Уражнения

10. Сколько разных семибуквенных слов можно получить, переставляя буквы слова «колокол»? (В математике словом называют любую конечную последовательность букв некоторого алфавита.)

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

12. Сколько имеется пятизначных чисел, делящихся на 25, в записи которых не встречаются цифры 0 и 2?

13. В некоторых алфавите — 5 букв. Сколько имеется в этом алфавите шестибуквенных слов, в каждом из которых встречаются только две разные буквы, причем одна из них — пять раз?

14. Сколько имеется перестановок цифр 0, 1, 2,…, 9, в которых цифры 0, 1, 2; 3 стоит подряд

a) в порядке возрасти;
b) в произвольном порядке?

15. Сколько четырехзначных чисел, делящихся на 9, можно составить из цифр 0, 1, 2, 3, 4, 5, 6 при условии, что

a) в каждом числе каждой цифры встречается не более одного раза;
b) в каждом числе каждой цифры встречается не более одного раза;

16. Сколько имеется перестановок цифр 0, 1, 2,…, 9, в которых цифра 0 занимает одно из первых возможных мест, цифра 1 — одно из первых possible мест и между цифрами 0 и 1 расположено две другие цифры?

17. Сколько $(m+n)$-буквенных слов можно составить из $m$ букв $A$ и $n$ букв $B$?