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

Олимпиадная математика · ~40 минут

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

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

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

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

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

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

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

Сочетания

Сочетание $\binom{n}{k}$ («число сочетаний из $n$ по $k$») — количество способов выбрать $k$ предметов из $n$ без учёта порядка. Формула: $$\binom{n}{k} = \frac{n!}{k!,(n-k)!}.$$ Например, $\binom{5}{2} = \frac{5\cdot4}{2} = 10$ — столькими способами из 5 человек можно выбрать пару.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

📝 Задачи

1. Сколькими способами можно выбрать из 8 книг три, чтобы взять с собой в поездку? (Порядок не важен.)

2. Сколько всего диагоналей у выпуклого 12-угольника? (Подсказка: диагональ — пара вершин, но не сторона.)

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

4. Докажи тождество $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$ подсчётом двумя способами. (Подсказка: сколько всего подмножеств у множества из $n$ элементов?)

5. На плоскости 7 точек, никакие три не на одной прямой. Через каждые две проведён отрезок. Сколько всего отрезков? Сколько среди них можно гарантированно найти... нет — сколько всего отрезков, и сколько треугольников с вершинами в этих точках?

6. В городе 20 футбольных команд провели турнир, сыграв суммарно 101 матч (каждая пара сыграла не более одного раза). Докажи, что нашлись три команды, каждые две из которых сыграли между собой. (Трудная — это теорема Мантеля. Сравни со случаем ровно 100 матчей: там контрпример есть! Подумай про две группы по 10 команд.)

7. Итоговая (инвариант). По кругу стоят $n$ выключенных лампочек. За ход можно переключить (сменить состояние на противоположное) любые две соседние лампочки. При каких $n$ можно добиться, чтобы все лампочки горели? (Подсказка из урока 1: что происходит с чётностью числа горящих лампочек?)

8. ⭐ Итоговая на весь курс. Каждую клетку таблицы $3\times 7$ (3 строки, 7 столбцов) покрасили в чёрный или белый. Докажи, что обязательно найдётся «одноцветный прямоугольник»: четыре клетки, стоящие в углах некоторого прямоугольника (на пересечении двух строк и двух столбцов), все одного цвета. (Подсказка: посмотри на каждый столбец из 3 клеток — какого цвета в нём большинство? Дальше — принцип Дирихле по столбцам и подсчёт пар строк.)