Комбинаторика олимпиаднику

• Название: Комбинаторика олимпиаднику
• Дата: 15.07.2022
• Размер: 0.51 Mb.
• Имя файла: kombinatorika (2).pdf
• Тип: Документы; #631437
• страница: 3 из 6

15 27. (Физтех, 2012, 9–10 ) Сколько существует пар натуральных чисел, у которых наименьшее общее кратное равно 5000?
32 28. (Физтех, 2013, 8–11 ) Имеется желоб, по которому в обе стороны могут кататься одинаковые шарики с фиксированной скоростью. Если два шарика соударяются, каждый из них меняет направление своего движения на противоположное. С одного конца желоба двигаются пять шариков на равных расстояниях друг от друга, с другого конца — семь шариков (тоже на равных расстояниях друг от друга. Сколько всего будет соударений 29. (Физтех, 2011, 9–11 ) Найдите количество прямоугольников со сторонами, параллельными осям координат, таких, что точка (14; 22) содержится внутри (ноне на границе) каждого из них, абсциссы вершин являются натуральными числами меньше 29, а ординаты — натуральны и меньше, чем 31.
30576 30. (Физтех, 2014, 9–10 ) На плоскости нарисован круги три семейства прямых водном параллельных между собой прямых, в другом — 23 параллельных между собой прямых, в третьем — 36 параллельных между собой прямых. На какое наибольшее число частей прямые могут разбить круг 19

31. (Покори Воробьёвы горы, 2014, 8–9 ) Числа 1, 2, . . . , 9 расставлены в квадрате 3×3. Будем называть фэншуйными такие расстановки, у которых при выборе любых трёх клеток, расположенных в разных столбцах и разных строках, сумма чисел, стоящих в выбранных клетках,
будет равна 15. Пример фэншуйной расстановки приведён на рисунке 1
7 6
3 9
5 2
8 1 + 6 + 8 = Найдите число всех фэншуйных расстановок 32. (Ломоносов, 2016, 10–11 ) На окружности пытаются разместить 30 чёрных и 20 белых точек так, чтобы среди них можно было насчитать как можно больше всевозможных троек,
являющихся вершинами прямоугольных треугольников сч рными вершинами упрямых углов.
Каково наибольшее количество таких троек 33. (Физтех, 2012, 11 ) Найдите количество пар целых чисел (a, b) таких, что 1 6 a 6 700,
1 6 b 6 700, сумма a + b делится на 7, а произведение ab делится на 5. (При a 6= b пары (a, b) и, a) считаются различными 34. (Физтех, 2012, 11 ) На клетчатой доске размера 31 × 19 (длина стороны клетки равна) требуется отметить тройку клеток так, чтобы центры этих клеток образовывали прямоугольный треугольник с катетами длины 5 и 7 (катеты параллельны краям доски. Сколькими способами это можно сделать 35. (Физтех, 2015, 10–11 ) Найдите количество пар целых чисел (x, y), удовлетворяющих условию 6x
2
− 7xy + y
2
= 10 100 19998 36. (Физтех, 2014, 11 ) Найдите, сколько решений в натуральных числах имеет уравнение x
7
y
2
= 12 55
· 15 30 144 37. (Высшая проба, 2014, 9 ) Клетки шахматной доски раскрашиваются в три цвета — белый,
серый и чёрный — таким образом, чтобы соседние клетки, имеющие общую сторону, отличались цветом, однако резкая смена цвета (то есть соседство белой и чёрной клеток) запрещена. Найдите число таких раскрасок шахматной доски (раскраски, совпадающие при повороте доски на и 180 градусов, считаются разными 33 20

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

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

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

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

Задача. Монету подбрасывают 8 раз. При этом получается некоторая последовательность
«орлов» и «решек» (длины 8). Сколько всего существует таких последовательностей, в которых

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

Задача. Сколькими способами можно из семи человек выбрать комиссию из трёх человек во главе с председателем?
Решение. Председателя можно выбрать семью способами. Остальных двоих мы выбираем из шести человек C
2 6
= 15 способами. Поэтому число способов выбора комиссии равно 7 · 15 = Задача. (Покори Воробьёвы горы, 2014, 10–11 ) Сколькими способами можно собрать бригаду из 3 маляров и 4 штукатуров, если имеется 6 маляров и 8 штукатуров?
Решение. Маляров можно выбрать C
3 способами. Штукатуров можно выбрать C
4 8
способами.
Значит, для формирования бригады имеется C
3 6
C
4 8
= 20 · 70 = 1400 способов.
Задача. (Высшая проба, 2014, 7–8 ) Сколько среди целых чисел от 100 до 10000 таких, в записи которых встречаются ровно три одинаковых цифры?
Решение. Описанные в условии числа будем называть хорошими. Трёхзначных хороших чисел, очевидно, девять 111, 222, . . . , Ищем количество четырёхзначных хороших чисел. Ровно двух нулей в записи хорошего числа быть не может. Остаются следующие варианты три нуля, один нуль, нет нулей.
Хороших четырёхзначных чисел стремя нулями девять 1000, 2000, . . . , Предположим, что среди цифр хорошего четырёхзначного числа ровно один нуль. Остальные три (совпадающие) цифры можно выбрать 9 способами. При этом нуль может стоять на втором, третьем или четвёртом месте. Всего получается 9 · 3 = 27 хороших четырёхзначных чисел с одним нулём.
Предположим, что среди цифр хорошего четырёхзначного числа нуля нет. Тройку совпадающих цифр можно выбрать 9 способами три позиции для этой тройки можно выбрать C
3 4
= способами четвёртую цифру можно выбрать 8 способами. Всего хороших четырёхзначных чисел без нуля получается 9 · 4 · 8 = Искомое количество хороших чисел равно 9 + 9 + 27 + 288 = Задача. (Физтех, 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.
25

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

Задача. Имеются m различных шаров и n различных ящиков. Сколькими способами можно разложить шары по ящикам так, чтобы шаров оказались в первом ящике, шаров — во втором, . . . , m шаров — в м ящике (m
1
+ m
2
+ . . . + m n
= Решение. Искомое число способов обозначим P (m
1
, m
2
, . . . , m 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 В самом деле, выбрать шаров для первого ящика есть тоже самое, что выбрать позиций для букв a
1
; затем, выбрать шаров для второго ящика есть тоже самое, что выбрать позиций для букв a
2
, и т. д.
Все буквы слова (
4
) можно переставить m! способами. Это число надо разделить на m
1
! (перестановок букв a
1
, которые ничего не меняют, на m
2
! (перестановок букв a
2
, которые ничего не меняют, . . . , на m n
! (перестановок букв a n
, которые ничего не меняют. Итого получается (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 различных шаров в n различных ящиков (без каких-либо дополнительных ограничений) есть число размещений с повторениями ¯
A
m n