Олимпиадные задачи по комбинаторике. Задача о беспорядках

• Название: Задача о беспорядках
• Анкор: Олимпиадные задачи по комбинаторике
• Дата: 12.04.2022
• Размер: 0.5 Mb.
• Имя файла: kombinatorika.pdf
• Тип: Задача; #468020
• страница: 3 из 6

974 12. («Физтех», 2014, 7–8 ) Сколько различных натуральных делителей у числа 15552?
42 13. («Высшая проба», 2013, 8, 10 ) Сколько различных делителей у числа 999 999
?
2998000 14. («Физтех», 2014, 9–11 ) Натуральное число имеет ровно два простых делителя. Его квад- рат имеет 51 различныx натуральных делителей. Какое наибольшее количество различных натуральных делителей может иметь куб этого числа?
100 15. («Ломоносов», 2013, 7 ) а) Сколько натуральных делителей имеет число N = 1 00 . . . 0
|
{z
}
99
?
б) Найдите количество натуральных делителей числа N , не являющихся точными квадра- тами (т. е. квадратами натуральных чисел).
а)10000;
б)7500 16. («Физтех», 2012, 9–11 ) Какое количество натуральных чисел a обладает следующим свой- ством: «Наименьшее общее кратное чисел 16, 50 и a равняется 1200»?
15 16

17. («Физтех», 2012, 9–10 ) Сколько существует пар натуральных чисел, у которых наименьшее общее кратное равно 5000?
32 18. («Физтех», 2013, 8–11 ) Имеется желоб, по которому в обе стороны могут кататься оди- наковые шарики с фиксированной скоростью. Если два шарика соударяются, каждый из них меняет направление своего движения на противоположное. С одного конца желоба двигаются пять шариков на равных расстояниях друг от друга, с другого конца — семь шариков (тоже на равных расстояниях друг от друга). Сколько всего будет соударений?
35 19. («Физтех», 2011, 9–11 ) Найдите количество прямоугольников со сторонами, параллельны- ми осям координат, таких, что точка (14; 22) содержится внутри (но не на границе) каждого из них, абсциссы вершин являются натуральными числами меньше 29, а ординаты — натуральны и меньше, чем 31.
30576 20. («Покори Воробьёвы горы!», 2014, 8–9 ) Числа 1, 2, . . . , 9 расставлены в квадрате 3×3. Будем называть фэншуйными такие расстановки, у которых при выборе любых трёх клеток, распо- ложенных в разных столбцах и разных строках, сумма чисел, стоящих в выбранных клетках,
будет равна 15. Пример фэншуйной расстановки приведён на рисунке.
4 1
7 6
3 9
5 2
8 1 + 6 + 8 = 15
Найдите число всех фэншуйных расстановок.
72 21. («Физтех», 2012, 11 ) Найдите количество пар целых чисел (a, b) таких, что 1 6 a 6 700,
1 6 b 6 700, сумма a + b делится на 7, а произведение ab делится на 5. (При a 6= b пары (a, b) и
(b, a) считаются различными.)
25200 22. («Физтех», 2012, 11 ) На клетчатой доске размера 31 × 19 (длина стороны клетки рав- на 1) требуется отметить тройку клеток так, чтобы центры этих клеток образовывали прямо- угольный треугольник с катетами длины 5 и 7 (катеты параллельны краям доски). Сколькими способами это можно сделать?
2592 23. («Физтех», 2014, 11 ) Найдите, сколько решений в натуральных числах имеет уравнение x
7
y
2
= 12 55
· 15 30 144 17

24. («Высшая проба», 2014, 9 ) Клетки шахматной доски раскрашиваются в три цвета — белый,
серый и чёрный — таким образом, чтобы соседние клетки, имеющие общую сторону, отличались цветом, однако резкая смена цвета (то есть соседство белой и чёрной клеток) запрещена. Най- дите число таких раскрасок шахматной доски (раскраски, совпадающие при повороте доски на
90 и 180 градусов, считаются разными).
2 33 18

4
Размещения, перестановки и сочетания
Некоторые комбинации объектов встречаются наиболее часто и имеют определённые названия:
размещения, перестановки и сочетания. В этом разделе мы научимся подсчитывать количества таких комбинаций.
4.1
Размещения
Выше нам уже встретились размещения с повторениями
. Однако повторения возможны не всегда. В некоторых ситуациях бывает, что выбор, сделанный на данном этапе, ограничивает число вариантов выбора на следующем этапе.
Задача. В футбольной команде 11 человек. Сколькими способами можно выбрать: а) капитана и его ассистента; б) капитана, первого ассистента и второго ассистента?
Решение. а) Капитаном можно выбрать любого из 11 футболистов. Ассистентом — любого из
10 оставшихся. Поэтому капитана и ассистента можно выбрать 11 · 10 = 110 способами.
б) Капитана и первого ассистента мы уже выбрали 11 · 10 способами. Для выбора второго ассистента остаётся 9 способов. Поэтому капитана, первого ассистента и второго ассистента можно выбрать 11 · 10 · 9 = 990 способами.
В этой задаче мы фактически нашли число упорядоченных пар и упорядоченных троек,
которые можно выбрать из 11-элементного множества. Теперь рассмотрим данный вопрос в общем виде.
Определение. Пусть имеется множество, содержащее n элементов. Произвольный упорядо- ченный набор, составленный из k различных элементов данного множества, называется разме- щением из n элементов по k элементов (или просто размещением из n по k).
Число размещений из n элементов по k элементов обозначается A
k n
(читается «а из эн по ка»).
Это число упорядоченных наборов из k элементов (или число цепочек длины k), выбранных из n-элементного множества. Найдём, чему равно это число.
Рассуждаем так же, как и в задаче про футболистов. Для выбора первого элемента цепочки имеется n способов, для выбора второго элемента имеется n − 1 способов, для выбора третьего элемента имеется n − 2 способов и т. д. Для выбора последнего, k-го элемента цепочки имеется n − k + 1 способов. Следовательно,
A
k n
= n(n − 1)(n − 2) . . . (n − k + 1).
(1)
Данную формулу можно записать в более компактном виде, если правую часть умножить и разделить на (n − k)!:
A
k n
=
n(n − 1)(n − 2) . . . (n − k + 1)(n − k)!
(n − k)!
,
то есть
A
k n
=
n!
(n − k)!
(2)
(напомним, что n! = 1 · 2 · . . . · n, и по определению 0! = 1).
4.2
Перестановки
Перестановка есть простой частный случай размещения, однако настолько важный, что заслу- живает отдельного рассмотрения.
19

Задача. Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что цифры не должны повторяться?
Решение. Для выбора первой цифры имеется пять способов, для выбора второй — четыре,
для выбора третьей — три, для выбора второй — два, и для выбора последней цифры остаётся один способ. Всего чисел получается 5 · 4 · 3 · 2 · 1 = 5! = 120.

Задача. Имеется n разноцветных шаров. Сколькими способами их можно выложить в ряд?
Решение. Первый шар можно выбрать n способами, второй шар можно выбрать n − 1 спосо- бами и т. д. Для выбора последнего, n-го шара остаётся один способ. Всего получается n · (n − 1) · . . . · 2 · 1 = n!
способов выложить наши n шаров в ряд.
Определение. Пусть имеется множество, содержащее n элементов. Произвольная цепочка длины n, составленная из всех элементов данного множества, называется перестановкой этого множества (или перестановкой n элементов).
Иными словами, перестановка n элементов — это размещение из n по n. Число перестано- вок n-элементного множества обозначается P
n
; мы нашли это число в последней задаче (про разноцветные шары):
P
n
= n!
Данная формула легко получается также из формул (
1
) и (
2
) при k = n.
4.3
Сочетания
Переходим к рассмотрению сочетаний. Вернёмся к нашей футбольной команде, в которой мы выбирали капитана и ассистента.

Задача. В футбольной команде 11 человек. Сколькими способами можно выбрать из них двух игроков для прохождения допинг-контроля?
Решение. На первый взгляд кажется, что ситуация аналогична выбору капитана и ассистента:
первого человека выбираем 11 способами, второго — 10 способами, так что всего имеется 11 · 10
способов. Однако в данном случае это не так.
В самом деле, пара «капитан и ассистент» является упорядоченной: выбрать Петю капита- ном, а Васю ассистентом — это не то же самое, что выбрать Васю капитаном, а Петю ассистен- том. С другой стороны, пара человек, отправленных на допинг-тест, является неупорядоченной:
отправить Петю и Васю на тест — это ровно то же самое, что отправить Васю и Петю на тест.
Соответственно, в данной задаче нас интересует именно число неупорядоченных пар футболи- стов, выбираемых из 11 человек.
Давайте представим себе, что неупорядоченная пара {Петя, Вася} как бы склеивается из двух упорядоченных пар (Петя, Вася) и (Вася, Петя). Иными словами, любые две упорядо- ченные пары, отличающиеся лишь порядком следования объектов, дают одну и ту же неупо- рядоченную пару. Следовательно, число неупорядоченных пар будет в два раза меньше числа упорядоченных пар и окажется равным
11 · 10 2
= 55.
Таким образом, двух футболистов можно выбрать для допинг-контроля 55 способами.
20

Задача. Сколькими способами можно выбрать троих футболистов из 11 для прохождения допинг-контроля?
Решение. Произведение 11 · 10 · 9 (число способов выбора капитана, первого ассистента и второго ассистента) есть число упорядоченных троек футболистов. В данном же случае, как и в предыдущей задаче, порядок не важен, поэтому нам нужно найти число неупорядоченных троек фуболистов, выбираемых из 11 человек.
В одну неупорядоченную тройку склеиваются те и только те упорядоченные тройки, которые отличаются лишь порядком следования элементов. Число таких троек равно числу перестано- вок трёх элементов, то есть 3! = 6. Например, в одну неупорядоченную тройку
{Петя, Вася, Коля}
склеиваются ровно шесть упорядоченных троек
(Вася, Коля, Петя),
(Вася, Петя, Коля),
(Коля, Вася, Петя),
(Коля, Петя, Вася),
(Петя, Вася, Коля),
(Петя, Коля, Вася).
Следовательно, число неупорядоченных троек в 3! раз меньше числа упорядоченных троек.
Соответственно, имеется
11 · 10 · 9 3!
= 165
способов выбрать троих человек для допинг-контроля.
В последних двух задачах о футболистах, выбираемых на допинг-контроль, мы нашли число неупорядоченных пар и неупорядоченных троек, которые можно выбрать из 11-элементного множества. Теперь мы можем рассмотреть данный вопрос в общем виде.
Определение. Пусть имеется множество, содержащее n элементов. Произвольный неупоря- доченный набор, состоящий из k различных элементов данного множества, называется сочета- нием из n элементов по k элементов (или просто сочетанием из n по k).
Иными словами, сочетание из n элементов по k элементов — это просто k-элементное под- множество n-элементного множества.
Число сочетаний из n элементов по k элементов обозначается C
k n
(читается «це из эн по ка»).
Это число неупорядоченных наборов из k элементов, выбранных из n-элементного множества
(то есть число k-элементных подмножеств n-элементного множества). Найдём, чему равно это число.
Число упорядоченных наборов из k элементов (то есть число цепочек длины k) есть чис- ло размещений A
k n
. Те и только те цепочки, которые отличаются лишь порядком следования элементов, склеиваются в один неупорядоченный набор. Число таких цепочек равно числу пе- рестановок k элементов, то есть k!. Следовательно, искомое число неупорядоченных наборов из k элементов будет в k! раз меньше числа цепочек длины k:
C
k n
=
A
k n
k!
Согласно формулам (
1
) или (
2
) имеем:
C
k n
=
n(n − 1)(n − 2) . . . (n − k + 1)
k!
=
n!
k!(n − k)!
(3)
Теперь, зная, что такое число сочетаний, мы можем сразу сказать, что двух футболистов из одиннадцати для допинг-теста можно выбрать C
2 11
= (11 · 10)/2! способами; аналогично, трёх футболистов из одиннадцати можно выбрать C
3 11
= (11 · 10 · 9)/3! способами.
21

Задача. Монету подбрасывают восемь раз. При этом получается некоторая последователь- ность «орлов» и «решек» длины 8. Сколько всего существует таких последовательностей?
Решение. Пусть О означает «выпал орёл», а Р — «выпала решка». Тогда в результате вось- ми подбрасываний мы получим восьмибуквенное слово, состоящее из букв О и Р. Например,
слово РОРРООРР означает, что орёл выпал при втором, пятом и шестом подбрасываниях, а в остальных случаях выпала решка.
Теперь ясно, что вопрос ставится так: сколько восьмибуквенных слов можно составить из трёх букв О и пяти букв Р? Заметим, что слово однозначно определяется выбором позиций для трёх букв О (остальные позиции автоматически заполняются буквами Р). Поэтому число наших слов есть число способов выбрать три позиции из восьми, то есть C
3 8
= (8 · 7 · 6)/3! = 56.
Это и есть ответ.
Заметим также, что позиции можно было бы выбирать не для букв О, а для букв Р. А имен- но, слово однозначно определяется выбором позиций для пяти букв Р, что можно сделать
C
5 8
= 56 способами. Как видите, C
3 8
= C
5 8
, и это частный случай общего свойства числа со- четаний (см. следующую задачу).
Задача. Докажите, что C
k n
= C
n−k n
Решение. Каждому k-элементному подмножеству A n-элементного множества M однозначно соответствует его дополнение, то есть (n − k)-элементное множество, состоящее из все тех эле- ментов, которые не входят в A. Поэтому число k-элементных подмножеств множества M равно числу его (n − k)-элементных подмножеств; но первое число есть C
k n
, а второе равно C
n−k n
(Попросту говоря, выбрать k элементов — это всё равно, что выбрать n − k дополнительных элементов; поэтому число способов выбора первых равно числу способов выбора вторых.)
Данное равенство можно доказать и алгебраически с помощью формулы (
3
):
C
n−k n
=
n!
(n − k)!(n − (n − k))!
=
n!
(n − k)!k!
= C
k n
Задача. Докажите, что C
k n+1
= C
k n
+ C
k−1
n
Решение. Алгебраическое доказательство с помощью формулы (
3
) оставляется читателю в качестве самостоятельного упражнения. Приведём комбинаторное доказательство данного ра- венства.
Рассмотрим множество A, состоящее из n + 1 элементов. Тогда C
k n+1
— это число k-элемент- ных подмножеств множества A.
Выделим в множестве A некоторый элемент и назовём его x. Всякое подмножество множе- ства A либо содержит элемент x, либо не содержит его.
Сколько k-элементных подмножеств множества A не содержит x? Чтобы сформировать такое подмножество, нам нужно из оставшихся n элементов множества A выбрать k элементов.
Это можно сделать C
k n
способами. Значит, имеется C
k n
подмножеств множества A, состоящих из k элементов и не содержащих x.
Теперь найдём число k-элементных подмножеств множества A, содержащих элемент x. Что- бы сформировать такое подмножество, надо из оставшихся n элементов множества A выбрать k − 1 элементов (ведь x уже включён в подмножество). Это можно сделать C
k−1
n способами.
Значит, число подмножеств множества A, состоящих из k элементов и содержащих элемент x,
равно C
k−1
n
Для завершения доказательства остаётся воспользоваться правилом суммы.
Доказанное равенство объясняет, почему числа C
k n
можно расположить по строкам тре- угольника Паскаля. Этот треугольник изображён ниже на рисунке. По боковым сторонам тре- угольника стоят единицы, числа внутри треугольника расположены в шахматном порядке, и каждое внутреннее число равно сумме двух чисел, стоящих непосредственно над ним.
22

1 1
1 1
2 1
1 3
3 1
1 4
6 4
1 1
5 10 10 5
1
Строки треугольника нумеруются сверху начиная с нуля. Числа в строках нумеруются слева также с нуля. Число C
k n
стоит в n-й строке k-м по счёту (например, 6 = C
2 4
).
В следующих задачах нужно не просто находить числа сочетаний, но и одновременно ис- пользовать правила произведения и суммы.

Задача. Сколькими способами можно из семи человек выбрать комиссию из трёх человек во главе с председателем?
Решение. Председателя можно выбрать семью способами. Остальных двоих мы выбираем из шести человек C
2 6
= 15 способами. Поэтому число способов выбора комиссии равно 7 · 15 = 105.
Задача. («Покори Воробьёвы горы!», 2014, 10–11 ) Сколькими способами можно собрать бри- гаду из 3 маляров и 4 штукатуров, если имеется 6 маляров и 8 штукатуров?
Решение. Маляров можно выбрать C
3 6
способами. Штукатуров можно выбрать C
4 8
способами.
Значит, для формирования бригады имеется C
3 6
C
4 8
= 20 · 70 = 1400 способов.
Задача. («Высшая проба», 2014, 7–8 ) Сколько среди целых чисел от 100 до 10000 таких, в записи которых встречаются ровно три одинаковых цифры?
Решение. Описанные в условии числа будем называть хорошими. Трёхзначных хороших чи- сел, очевидно, девять: 111, 222, . . . , 999.
Ищем количество четырёхзначных хороших чисел. Ровно двух нулей в записи хорошего числа быть не может. Остаются следующие варианты: три нуля, один нуль, нет нулей.
Хороших четырёхзначных чисел с тремя нулями девять: 1000, 2000, . . . , 9000.
Предположим, что среди цифр хорошего четырёхзначного числа ровно один нуль. Осталь- ные три (совпадающие) цифры можно выбрать 9 способами. При этом нуль может стоять на втором, третьем или четвёртом месте. Всего получается 9 · 3 = 27 хороших четырёхзначных чисел с одним нулём.
Предположим, что среди цифр хорошего четырёхзначного числа нуля нет. Тройку совпада- ющих цифр можно выбрать 9 способами; три позиции для этой тройки можно выбрать C
3 4
= 4
способами; четвёртую цифру можно выбрать 8 способами. Всего хороших четырёхзначных чи- сел без нуля получается 9 · 4 · 8 = 288.
Искомое количество хороших чисел равно 9 + 9 + 27 + 288 = 333.
Задача. («Физтех», 2011, 9–11 ) На некоторой прямой произвольно отмечено 10 точек, а на параллельной ей прямой — 12 точек. Сколько существует треугольников и сколько четырёх- угольников с вершинами в этих точках?
Решение. Будем для краткости называть 10 точек на первой прямой красными, а 12 точек на второй прямой — синими.
У треугольника может быть: 1) одна красная вершина и две синих; 2) одна синяя вершина и две красных. В первом случае мы выбираем красную вершину 10 способами, а синюю —
C
2 12
= 12 · 11/2 = 66 способами. Во втором случае мы выбираем синюю вершину 12 способами,
а красную — C
2 10
= 45 способами. Всего треугольников получается 10 · 66 + 12 · 45 = 1200.
У четырёхугольника лишь одна возможность: две красные вершины и две синие. Число четырёхугольников получается равным C
2 10
· C
2 12
= 45 · 66 = 2970.
23

4.4
Перестановки с повторениями
Идея склеивания упорядоченных наборов (отличающихся лишь порядком следования элемен- тов) в один неупорядоченный набор является весьма плодотворной и даёт не только формулу для числа сочетаний, но и гораздо больше.
Задача. Анаграмма — это слово (не обязательно осмысленное), полученное из данного слова перестановкой букв. Например, бьорд является анаграммой слова дробь. Сколько всего ана- грамм у слова дробь? У слова класс? У слова колобок ?
Решение. У слова дробь имеется 5! анаграмм — именно столько существует перестановок множества из пяти объектов.
В слове класс две буквы одинаковы. Давайте временно считать их различными, приписав им индексы: клас
1
с
2
. У этого нового слова 5! анаграмм. А теперь во всех анаграммах нового слова сотрём индексы. Каждые две анаграммы слова клас
1
с
2
, которые отличались лишь пере- становкой букв с
1
и c
2
, склеятся в одну анаграмму слова класс. Поэтому анаграмм получится
5!/2 = 60.
Аналогично рассмотрим слово к
1
о
1
ло
2
бо
3
к
2
. У него 7! анаграмм. После стирания индексов у букв о
1
, о
2
, о
3
склеятся в одно слово каждые 3! анаграмм, отличающиеся лишь перестановкой этих трёх букв. Затем после стирания индексов у букв к
1
и к
2
склеятся в одно слово каждые 2!
анаграмм, отличающиеся лишь перестановкой этих двух букв. Таким образом, после стирания всех индексов склеятся в одно слово 3! · 2! анаграмм, и число анаграмм у слова колобок будет равно
7!
3! · 2!
= 420.
У слов класс и колобок анаграмм получилось меньше, чем 5! и 7! соответственно, по той причине, что в этих словах присутствуют повторяющиеся буквы. Учитывая повторы и деля на соответствующий коэффициент, мы находим количество так называемых перестановок с повторениями.
Идея нахождения числа перестановок с повторениями иногда называется методом кратного подсчёта. Суть метода проста: чтобы посчитать нужное количество комбинаций, мы сначала находим количество других комбинаций, превосходящее количество исходных комбинаций в некоторое число раз, а потом делим на это число.
Формула для числа сочетаний немедленно получается с помощью метода кратного подсчё- та. В самом деле, число способов выбора k объектов из n объектов равно числу анаграмм n-буквенного слова aa . . . a
|
{z
}
k bb . . . b
|
{z
}
n−k
,
состоящего из k букв a и n − k букв b (ведь каждая анаграмма — это определённый выбор k позиций из n для букв a). Из сказанного выше ясно, что у данного слова имеется n!
k!(n − k)!
анаграмм; столько же получается и сочетаний из n по k.
Теперь сформулируем общую задачу о перестановках с повторениями.
Задача. Имеются m различных шаров и n различных ящиков. Сколькими способами можно разложить шары по ящикам так, чтобы m
1
шаров оказались в первом ящике, m
2
шаров — во втором, . . . , m n
шаров — в n-м ящике (m
1
+ m
2
+ . . . + m n
= m)?
24

Решение. Искомое число способов обозначим P (m
1
, m
2
, . . . , m n
). Оно равно количеству ана- грамм n-буквенного слова a
1
a
1
. . . a
1
|
{z
}
m
1
a
2
a
2
. . . a
2
|
{z
}
m
2
. . . a n
a n
. . . a n
|
{z
}
m n
(4)
В самом деле, выбрать m
1
шаров для первого ящика есть то же самое, что выбрать m
1
позиций для букв a
1
; затем, выбрать m
2
шаров для второго ящика есть то же самое, что выбрать m
2
позиций для букв a
2
, и т. д.
Все буквы слова (
4
) можно переставить m! способами. Это число надо разделить на m
1
! (пе- рестановок букв a
1
, которые ничего не меняют), на m
2
! (перестановок букв a
2
, которые ничего не меняют), . . . , на m n
! (перестановок букв a n
, которые ничего не меняют). Итого получается
P (m
1
, m
2
, . . . , m n
) =
m!
m
1
!m
2
! . . . m n
!
=
(m
1
+ m
2
+ . . . + m n
)!
m
1
!m
2
! . . . m n
!
способов.
Нетрудно видеть, что данная формула обобщает формулу для числа сочетаний. В самом деле, мы просто имеем C
m n
= P (m, n − m).
4.5
Сочетания с повторениями
Как мы знаем, число способов разложить m различных шаров в n различных ящиков (без каких-либо дополнительных ограничений) есть число размещений с повторениями: ¯
A
m n
= n m