Тема 05 · Математика, углублённый уровень · подтема 3 из 5

Принцип Дирихле и худший случай

Логические и комбинаторные задачи. 100 заданий.

Решено

Правильно

Точность

Простыми словами

У Маши 3 кофты и 4 юбки. Сколько разных нарядов? К каждой кофте подходит любая из 4 юбок — получаем $3 \cdot 4 = 12$ . Так устроено большинство задач на подсчёт: выбор делят на шаги и перемножают число вариантов на каждом шаге. Остальные задачи темы — про «худший случай», пересекающиеся группы и закономерности.

Правило произведения

вариантов = n_{1} \cdot n_{2} \cdot \dots \cdot n_{k}

n_{1}

— число способов сделать первый шаг,

n_{2}

— второй (при любом первом) и т. д.

Первая цифра числа не может быть $0$ .
Без повторений каждый следующий выбор на 1 меньше: $n$ предметов в ряд — $n \cdot (n - 1) \cdot \dots \cdot 2 \cdot 1$ способов.
«Двое рядом» — склеиваем их в один блок и умножаем на 2 (внутри блока два порядка).
Если путь идёт одним из нескольких разных способов (или так, или так), варианты складывают.

Сколько чётных трёхзначных чисел из цифр 0, 3, 8 (повторять можно)?

Сотни: 3 или 8 — 2 способа (не 0).
Десятки: любая — 3 способа.
Единицы: чётная, 0 или 8 — 2 способа.
$2 \cdot 3 \cdot 2 = 12$ .

A–B: 3 дороги, B–C: 3, A–C напрямую: 3. Съездить A → C → A, не проезжая дважды по одной дороге.

Туда напрямую (3 способа). Обратно: напрямую по другой — 2, или через B — $3 \cdot 3 = 9$ . Итого $3 \cdot 11 = 33$ .
Туда через B ( $3 \cdot 3 = 9$ ). Обратно: напрямую — 3, или через B по другим дорогам — $2 \cdot 2 = 4$ . Итого $9 \cdot 7 = 63$ .
Всего $33 + 63 = 96$ .

Подсчёт чисел с условием

От 1 до $N$ на $k$ делятся $[N : k]$ чисел — неполное частное.
Делятся на $a$ или на $b$ : $[N : a] + [N : b] - [N : НОК (a, b)]$ — общие посчитаны дважды.
Делятся на $a$ , но не на $b$ : $[N : a] - [N : НОК (a, b)]$ .
«Хотя бы одна цифра $d$ » = все числа − числа без цифры $d$ .

Сколько чисел от 1 до 284 делятся на 5, но не на 7?

На 5: $[284 : 5] = 56$ .
На 5 и на 7, то есть на 35: $[284 : 35] = 8$ .
$56 - 8 = 48$ .

Трёхзначные числа с возрастающими цифрами, делящиеся на 5: последняя цифра 5 (ноль не может быть больше предыдущих), впереди две разные цифры из $1, 2, 3, 4$ по возрастанию — 6 пар: 12, 13, 14, 23, 24, 34.

Запреты и подсчёт цифр

Есть запрет — считаем все варианты и вычитаем запрещённые.

2 рубашки (одна зелёная), 5 пар брюк (одни серые), 2 пары обуви. Зелёную рубашку с серыми брюками не надевают. Сколько комплектов?

Всего: $2 \cdot 5 \cdot 2 = 20$ .
Запрещённые: зелёная рубашка + серые брюки + любая обувь — $1 \cdot 1 \cdot 2 = 2$ .
$20 - 2 = 18$ .

Сколько раз пишут цифру. Числа от $1$ до $999$ удобно считать как $000$ – $999$ : в каждом из трёх разрядов каждая цифра встречается $100$ раз. Цифра $4$ — $3 \cdot 100 = 300$ раз.

Мало вариантов — выписываем все по порядку. Двузначные с суммой цифр $9$ : $18, 27, 36, 45, 54, 63, 72, 81, 90$ — их $9$ .

Принцип Дирихле и худший случай

Если $n$ кроликов сидят в $k$ клетках и $n > k$ , то в какой-то клетке не меньше двух кроликов. Общее: хотя бы в одной клетке не меньше $n : k$ кроликов (округляем вверх).

«Наверняка» = представим самый неудачный случай и добавим 1. Чтобы 5 человек наверняка родились в одном месяце: в худшем случае по 4 в каждом из 12 месяцев — $48$ человек, и 49-й даёт пятого. Ответ: $4 \cdot 12 + 1 = 49$ .

86 учеников в 4 классах. Сколько наверняка окажется в одном классе? $86 : 4 = 21, 5$ — поровну не получится, значит, где-то не меньше $22$ . Ответ: $22$ .

Худший случай: примеры

В мешке шары 4 цветов. Сколько вынуть, чтобы наверняка было 2 одного цвета?

Худший случай — по одному каждого цвета: $4$ шара.
Пятый обязательно повторит цвет. Ответ: $5$ .

9 пар перчаток каждого из 2 цветов. Сколько взять, чтобы наверняка была пара (левая и правая) одного цвета?

Худший случай — все левые: $9 + 9 = 18$ перчаток, пары нет.
19-я — правая какого-то цвета, к ней есть левая. Ответ: $19$ .

В коробке 5 красных и синих карандашей. Среди любых 4 есть красный, среди любых 3 — синий. Сколько красных?

«Среди любых 4 есть красный» — синих не больше 3.
«Среди любых 3 есть синий» — красных не больше 2.
$2 + 3 = 5$ , значит, красных ровно $2$ .

Круги Эйлера

Только чай

18 - 4 = 14

, только какао

5 - 4 = 1

, оба

4

; вне кругов

21 - 19 = 2

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

∣ A ∣

— сколько в группе

A

∣ A \cap B ∣

— сколько сразу в обеих,

∣ A \cup B ∣

— хотя бы в одной

∣ A \cup B \cup C ∣ = A + B + C - A B - BC - A C + A BC

31 ученик; хор 20, театр 14, шахматы 16; попарно 10, 10, 9; во всех трёх 8. Хотя бы в одном: $20 + 14 + 16 - 10 - 10 - 9 + 8 = 29$ . Ни в одном: $31 - 29 = 2$ .

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

Закономерности и последовательности

«Каждое число, начиная с третьего, равно сумме двух предыдущих» — просто выписываем по порядку: $7, 8, 15, 23, 38, 61, 99, 160, 259, 419$ — десятое число $419$ .
Если ряд повторяется с периодом $k$ , $n$ -й элемент равен элементу с номером, равным остатку от деления $n$ на $k$ (остаток 0 — последний в периоде).
«Каждый с каждым» (рукопожатия, матчи): $n \cdot (n - 1) : 2$ .
Ряд из $n$ квадратов из спичек — $3 n + 1$ спичка.

Считайте номера внимательно: первое число — номер 1. Полезно подписывать номер над каждым членом.

Циклы, разности, цифры подряд

Дни недели повторяются через 7. Через $198$ дней после вторника: $198 = 7 \cdot 28 + 2$ — сдвиг на 2 дня, четверг.

Разности растут на одно и то же число. $10, 13, 18, 25, 34$ : разности $3, 5, 7, 9$ — значит, $a_{n} = n^{2} + 9$ ( $1 + 9 = 10$ , $4 + 9 = 13$ , …). 16-й член: $1 6^{2} + 9 = 265$ .

«Каждый с каждым» наоборот. Матчей $136$ : $n (n - 1) : 2 = 136$ , $n (n - 1) = 272 = 17 \cdot 16$ — команд $17$ .

Спичечная сетка $m \times n$ клеток: горизонтальных отрезков $(m + 1) \cdot n$ , вертикальных $(n + 1) \cdot m$ . Для $8 \times 12$ : $9 \cdot 12 + 13 \cdot 8 = 108 + 104 = 212$ .

Выписали $123456789101112 \dots$ Какая цифра на 654-м месте?

Однозначные занимают места 1–9, двузначные — ещё $90 \cdot 2 = 180$ : всего $189$ .
Осталось $654 - 189 = 465 = 3 \cdot 155$ — ровно 155 трёхзначных чисел, последнее из них $100 + 154 = 254$ .
654-е место — последняя цифра числа $254$ : ответ $4$ .

Повторяющаяся запись $953595359535 \dots$ : период 4, $1320 = 4 \cdot 330$ — остаток 0, последняя цифра периода: $5$ .

Посмотреть и посчитать

Модели

События и множества: круги Эйлера Перестановки, размещения, сочетания

Серия: 0

Принцип Дирихле и худший случай

Простыми словами

Правило произведения

Подсчёт чисел с условием

Запреты и подсчёт цифр

Принцип Дирихле и худший случай

Худший случай: примеры

Круги Эйлера

Закономерности и последовательности

Циклы, разности, цифры подряд

Примеры заданий