Урок 7. Комбинаторные оценки и подсчёт двумя способами

Олимпиадная математика

Есть особый жанр красоты в математике: взять одну и ту же величину и посчитать её двумя разными способами. Раз это одно и то же — ответы равны, и часто из этого равенства выпрыгивает неожиданный факт. А ещё мы научимся не считать точно, а оценивать — доказывать «не меньше, чем» и «не больше, чем», что на олимпиадах ценится не меньше точного ответа. Это финальный урок, и в конце — подборка задач на весь курс.

🎯 Что ты узнаешь

Правила суммы и произведения
Что такое сочетания $(k n)$ и как их считать
Приём «подсчёт двумя способами»
Как доказывать оценки «не меньше / не больше»

📖 Разбираемся в теме

Правила суммы и произведения

📌 Запомни: Если один выбор можно сделать $a$ способами, а независимо от него другой — $b$ способами, то оба вместе — $a \cdot b$ способами (правило произведения). Если же выбираем одно из двух непересекающихся множеств вариантов — то $a + b$ способами (правило суммы).

Например, число трёхзначных чисел из цифр $1, 2, 3$ (с повторами): каждая из трёх позиций — 3 варианта, всего $3 \cdot 3 \cdot 3 = 27$ .

Сочетания

Сочетание $(k n)$ («число сочетаний из $n$ по $k$ ») — количество способов выбрать $k$ предметов из $n$ без учёта порядка. Формула:

(k n) = \frac{n !}{k ! ( n - k )!} .

Например, $(2 5) = \frac{5 \cdot 4}{2} = 10$ — столькими способами из 5 человек можно выбрать пару.

💡 Полезное симметричное свойство: $(k n) = (n - k n)$ (выбрать $k$ , кого взять — то же, что выбрать $n - k$ , кого не взять).

Подсчёт двумя способами

Идея: придумать величину и сосчитать её двумя путями. Ответы обязаны совпасть.

Пример. Сколько всего рукопожатий, если $n$ человек пожали руки каждый с каждым? Способ 1: каждый из $n$ человек жмёт $n - 1$ руку, суммарно $n (n - 1)$ — но так каждое рукопожатие сосчитано дважды (с двух сторон), значит рукопожатий $\frac{n ( n - 1 )}{2}$ . Способ 2: рукопожатие — это выбор пары, то есть $(2 n) = \frac{n ( n - 1 )}{2}$ . Совпало — и заодно мы «доказали» формулу для $(2 n)$ .

🤔 А знаешь ли ты? Знаменитая формула $1 + 2 + \dots + (n - 1) = (2 n)$ — тоже подсчёт двумя способами. Треугольная стопка кубиков одновременно и сумма, и число пар.

Оценки: «не меньше» и «не больше»

Часто нельзя (или не нужно) найти точное число, но можно зажать его в границы. Основные приёмы:

среднее: если сумма $n$ чисел равна $S$ , то хотя бы одно из них $\geq S / n$ и хотя бы одно $\leq S / n$ (иначе сумма была бы слишком мала/велика);
крайний элемент: рассмотри самый большой/маленький объект — у него особые свойства;
двойной подсчёт для неравенства.

📌 Запомни: «Средний аргумент»: среди $n$ чисел с суммой $S$ обязательно есть число $\geq S / n$ . Это по сути обобщённый принцип Дирихле в числовой форме.

⚠️ Оценка без примера, показывающего, что она достигается, доказывает только неравенство, но не то, что это точный максимум/минимум. Для «ровно столько» нужны обе части: оценка + конструкция.

✍️ Разбор задачи

Задача (двойной подсчёт). В классе несколько кружков. Каждый ученик ходит ровно в 2 кружка, и любые два кружка имеют ровно одного общего ученика. Кружков 6. Сколько учеников в классе?

Решение. Посчитаем пары кружков двумя способами.

Способ 1. Пар кружков из 6 штук: $(2 6) = 15$ . По условию каждой паре кружков соответствует ровно один общий ученик.

Способ 2. Каждый ученик ходит ровно в 2 кружка — то есть каждый ученик «отвечает» ровно за одну пару кружков (пару своих кружков). Разные ученики дают разные пары (ведь у каждой пары кружков общий ученик единственный).

Значит между учениками и парами кружков — взаимно однозначное соответствие. Учеников столько же, сколько пар кружков: 15. ∎

Вот она, магия двойного подсчёта: мы ни разу не «перечисляли» учеников, а нашли их число из чистой комбинаторики.

Задача (оценка). В турнире каждый сыграл с каждым по разу (без ничьих). Докажи, что найдётся игрок, выигравший хотя бы половину своих партий.

Решение. Пусть игроков $n$ , всего сыграно $(2 n)$ партий, и в каждой ровно одна победа. Значит суммарное число побед всех игроков равно $(2 n) = \frac{n ( n - 1 )}{2}$ . Побед у $n$ игроков в сумме $\frac{n ( n - 1 )}{2}$ , поэтому в среднем у игрока $\frac{n - 1}{2}$ побед. По среднему аргументу хотя бы у одного игрока побед $\geq \frac{n - 1}{2}$ — а это ровно половина из $n - 1$ сыгранных им партий. ∎

📝 Задачи

Сколькими способами можно выбрать из 8 книг три, чтобы взять с собой в поездку? (Порядок не важен.)
Сколько всего диагоналей у выпуклого 12-угольника? (Подсказка: диагональ — пара вершин, но не сторона.)
В компании из 10 человек некоторые дружат. Докажи, что найдутся двое с одинаковым числом друзей внутри компании. (Совмести Дирихле и подсчёт: сколько может быть разных значений «числа друзей»?)
Докажи тождество $(0 n) + (1 n) + \dots + (n n) = 2^{n}$ подсчётом двумя способами. (Подсказка: сколько всего подмножеств у множества из $n$ элементов?)
На плоскости 7 точек, никакие три не на одной прямой. Через каждые две проведён отрезок. Сколько всего отрезков? Сколько среди них можно гарантированно найти... нет — сколько всего отрезков, и сколько треугольников с вершинами в этих точках?
В городе 20 футбольных команд провели турнир, сыграв суммарно 101 матч (каждая пара сыграла не более одного раза). Докажи, что нашлись три команды, каждые две из которых сыграли между собой. (Трудная — это теорема Мантеля. Сравни со случаем ровно 100 матчей: там контрпример есть! Подумай про две группы по 10 команд.)
Итоговая (инвариант). По кругу стоят $n$ выключенных лампочек. За ход можно переключить (сменить состояние на противоположное) любые две соседние лампочки. При каких $n$ можно добиться, чтобы все лампочки горели? (Подсказка из урока 1: что происходит с чётностью числа горящих лампочек?)
⭐ Итоговая на весь курс. Каждую клетку таблицы $3 \times 7$ (3 строки, 7 столбцов) покрасили в чёрный или белый. Докажи, что обязательно найдётся «одноцветный прямоугольник»: четыре клетки, стоящие в углах некоторого прямоугольника (на пересечении двух строк и двух столбцов), все одного цвета. (Подсказка: посмотри на каждый столбец из 3 клеток — какого цвета в нём большинство? Дальше — принцип Дирихле по столбцам и подсчёт пар строк.)