E3 Двойной счёт (классика)

Идея метода: если у нас есть некоторая сумма, которую можно записать двумя разными способами, то оба способа дадут одинаковый результат. Двойной счёт классический (E3) — это именно подсчёт одной и той же числовой суммы двумя разными методами с целью получить тождество или равенство.

Важно отличать E3 от E10: E3 — «классический двойной счёт сумм», где мы вычисляем конкретную сумму (например, сумму степеней вершин графа, сумму попарных расстояний, число пар «элемент–множество») двумя способами и приравниваем результаты. E10 — более продвинутый метод, применяющий двойной счёт к вероятностным или алгебраическим тождествам иного рода. В E3 оба способа подсчёта — элементарные, не требуют дополнительных теорий.

Жизненная аналогия: если посчитать рукопожатия на вечеринке «со стороны каждого гостя» (каждый называет, сколько он пожал рук) и «со стороны каждой пары» (за каждое рукопожатие считаем 1), то результаты должны совпасть — это и есть двойной счёт.

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

• Лемма о рукопожатиях: в любом графе сумма степеней вершин равна удвоенному числу рёбер: $\sum_{v} \deg(v) = 2|E|$. Условие: конечный граф. Когда использовать: задачи на графы, где нужно связать число рёбер и степени.

• Двойной счёт пар: если $S = \sum_{i} a_i$ — одна запись суммы (по строкам таблицы), а $S = \sum_{j} b_j$ — другая (по столбцам), то $\sum_i a_i = \sum_j b_j$. Когда использовать: всегда, когда сумму можно записать по двум «осям» (объектам и их свойствам).

• Тождество Вандермонда (одно из применений): $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$. Доказывается двойным счётом: левая часть = разными способами выбрать $r$ из $m+n$. Когда использовать: при суммировании биномиальных коэффициентов.

• Считать пары «объект–свойство»: зафиксировать множество пар $(x, S)$ где $x \in S$, и посчитать его двумя способами: суммируя по $x$ (сколько множеств содержат $x$) и суммируя по $S$ (сколько элементов в $S$).
• Суммировать по строкам и столбцам: создать матрицу $M$ с $M_{ij} \in \{0, 1\}$, выразить сумму всех элементов двумя способами.
• Считать рёбра в двудольном графе: если каждая левая вершина связана с $a_i$ правыми, а каждая правая — с $b_j$ левыми, то $\sum a_i = \sum b_j$.
• Применить к биномиальным суммам: доказывать тождества типа $\sum_k \binom{n}{k} = 2^n$ через подсчёт всех подмножеств двумя способами.

Поверхностные признаки (что буквально написано):
- «Докажите тождество $\sum \ldots = \sum \ldots$».
- «Докажите, что количество ... равно количеству ...».
- «Найдите сумму степеней всех вершин», «найдите сумму всех попарных произведений».

Структурные признаки (форма выражения, объекты):
- Есть двусторонняя таблица или матрица инциденций (объекты vs. свойства).
- Сумма, которую можно интерпретировать как «число пар (объект, свойство)» с обеих сторон.
- Граф, где нужно связать степени вершин с числом рёбер.

Цель задачи (что от тебя хотят):
- Доказать тождество между двумя суммами без прямого вычисления каждой.
- Найти среднее значение или суммарный вклад через подсчёт с двух сторон.

Задача 1. В конкурсе участвуют $n$ жюри и $m$ участников. Каждый из $n$ жюри проверил ровно $k$ работ. Докажите, что каждый участник был проверен в среднем $\frac{nk}{m}$ раз.

Источник: тренировочная (классический двойной счёт)

Как думать (рассуждение ученика$):
1. $Что я вижу? Жюри проверяют работы — пары «жюри–участник». Нужно найти среднее.$2. *$Метод: двойной счёт. Посчитаю общее число проверок двумя способами.$3. *$Первый ход: пусть $T$ — общее число пар «жюри проверил участника». По условию каждый из $n$ жюри проверил $k$ работ, значит $T = nk$.$4. *$Второй способ*: $T = $ сумма числа проверок по всем участникам. Среднее число проверок на участника $= T/m = nk/m$.

Решение:
Обозначим $T$ — полное число пар «(жюри, проверенный участник)». С одной стороны, $T = n \cdot k$ (каждый из $n$ жюри проверил $k$ работ). С другой стороны, $T = \sum_{i=1}^{m} c_i$, где $c_i$ — число проверок $i$-го участника. Среднее значение $c_i$ равно $\frac{1}{m} \sum_{i=1}^m c_i = \frac{T}{m} = \frac{nk}{m}$.

Ответ: среднее число проверок на участника = $\frac{nk}{m}$.

Что в этой задаче было главным: одно и то же число $T$ считается «по жюри» (результат $nk$) и «по участникам» (результат $\sum c_i$), и именно равенство этих двух записей даёт ответ.

Задача 2. Докажите тождество $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$.

Источник: классическое тождество, тип задач ВсОШ-9

Как думать (рассуждение ученика$):
1. $Что я вижу? Сумма с биномиальными коэффициентами. Правая часть похожа на «выбрать подмножество и в нём один элемент».$2. *$Метод: двойной счёт числа пар «(подмножество $S \subseteq \{1,\ldots,n\}$, выделенный элемент $x \in S$)».$3. *$Первый способ: для каждого $k$-элементного $S$ выбираем один из $k$ элементов как выделенный → $\sum_{k=0}^n k\binom{n}{k}$ пар.$4. *$Второй способ*: сначала выбираем выделенный элемент $x$ ($n$ способов), затем любое подмножество, содержащее $x$ ($2^{n-1}$ вариантов, так как остальные $n-1$ элементов включаем или нет) → $n \cdot 2^{n-1}$ пар.

Решение:
Подсчитаем число пар $(S, x)$, где $S \subseteq \{1,\ldots,n\}$ и $x \in S$.
- По подмножествам: $k$-элементных подмножеств $\binom{n}{k}$, в каждом $k$ вариантов для $x$. Итого: $\sum_{k=0}^n k\binom{n}{k}$.
- По выделенному элементу: $n$ вариантов для $x$; для каждого $x$ подходят все $2^{n-1}$ подмножеств, содержащих $x$. Итого: $n \cdot 2^{n-1}$.
Приравнивая: $\sum_{k=0}^n k\binom{n}{k} = n \cdot 2^{n-1}$. $\square$

Ответ: тождество доказано.

Что в этой задаче было главным: интерпретация суммы как числа пар «подмножество + выделенный элемент» позволила мгновенно увидеть оба способа счёта.

• Ошибка: посчитать «с одной стороны» неправильно, включив лишние или пропустив пары. → Почему неверно: итоговое равенство окажется ложным. → Как избежать: явно описать, что именно является «парой», до начала счёта.

• Ошибка: смешать E3 и E10 — применить двойной счёт к тому, что считается совершенно иначе. → Как избежать: E3 = классический подсчёт числа пар объект–свойство; если задача про вероятности или алгебраические тождества с суммированием по индексам — скорее E10.

• Ошибка: при суммировании биномиальных коэффициентов написать неверные пределы суммирования. → Как избежать: перед записью суммы проверить: при $k=0$ первый член нулевой или нет?

• Ошибка: не объяснить, почему обе записи считают одно и то же. → Как избежать: явно назвать «объект», который считается с двух сторон.