E10 Двойной счёт

Почему метод важен

По таблице ВсОШ 9 метод E10 (Двойной подсчёт) — 10 задач как основной. Метод появляется с 2011 по 2025 на всех этапах, и часто комбинируется с E5 (чётность), B1 (логика), F (геометрия на сетке).

Главное, что даёт E10:

• умение считать одно и то же двумя способами и приравнивать суммы;
• работу с двудольными графами и матрицами инцидентности;
• доказательство неравенств через подсчёт рёбер;
• доказательство тождеств комбинаторики.

Реальные ориентиры из таблицы

Предупреждение: формулировки 2025 года приходят с OCR-склейкой слов, но численные данные восстановимы.

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

• Двойной счёт пар (инциденций): Пусть $X$ — число пар $(a, b) \in A \times B$ с заданным свойством. Тогда $X = \sum_{a \in A} d_A(a) = \sum_{b \in B} d_B(b)$, где $d_A(a)$ — число $b$, инцидентных $a$, и наоборот. Когда использовать: задачи о числе пар «объект — подмножество» или «точка — прямая».

• Считаем через вклад каждого элемента: Если нам нужна сумма $\sum_S f(S)$ по всем подмножествам $S$, часто проще считать вклад каждого элемента $x$: $\sum_S f(S) = \sum_x c(x)$, где $c(x)$ — суммарный вклад $x$ в все $S$. Когда использовать: задачи типа «сумма всех подмножеств» или «среднее по всем разбиениям».

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

• Построить таблицу инциденций: строки — объекты $A$, столбцы — объекты $B$, клетка = 1 при наличии связи. Подсчитать сумму по строкам и по столбцам — оба результата равны числу единиц.

• Считать пары (a, b) с нужным свойством двумя способами: сначала фиксируем $a$, считаем подходящие $b$; потом фиксируем $b$, считаем подходящие $a$.

• Вклад каждого элемента в сумму по подмножествам: вместо суммирования по $\binom{n}{k}$ подмножествам, считаем, сколько раз каждый элемент попадает в подмножество нужного типа.

• Применение к графам: для биграфа считаем рёбра двумя способами — по левым вершинам и по правым. Получаем $\sum \deg_{\text{лев}} = \sum \deg_{\text{пр}} = |E|$.

• Переход от суммы к среднему: если двойной счёт даёт $\sum_v d(v) = C$, то среднее $\bar{d} = C/|V|$. Тогда хотя бы у одной вершины $d(v) \geq \bar{d}$.

• Двойной счёт через перестановки: число пар $(\sigma, x)$, где $\sigma$ — перестановка и $x$ — неподвижная точка $\sigma$, можно считать по $\sigma$ и по $x$.

Поверхностные признаки (что буквально написано):
- Задача о числе пар, тройках, подмножеств с заданным свойством.
- «Докажите, что сумма/произведение чего-то равна...».
- «Подсчитайте количество X» в задаче, где X — пары или инциденции.

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

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

7 семейств E10

Семейство 1. Лемма о рукопожатиях

Сигнал. В задаче есть граф (или знакомства, или клетки с соседями), и нужно подсчитать сумму степеней.

Главный ход. \(\sum_v \deg(v)=2|E|\) — сумма степеней равна удвоенному числу рёбер.

Задача 1.1

В группе из 10 человек каждый знаком ровно с 4 другими. Сколько пар знакомых?

Скелет решения: \(\sum \deg = 10\cdot 4=40=2|E|\), значит \(|E|=20\).

Ответ:\[ 20 \text{ пар знакомых}. \]

Задача 1.2

В компании из 9 человек каждый имеет ровно 3 друзей. Возможно ли это?

Скелет решения: \(\sum\deg=9\cdot 3=27\) — нечётно, но \(2|E|\) — чётно. Противоречие.

Ответ: невозможно.

Задача 1.3

В графе с 7 вершинами сумма квадратов степеней равна 32. Сколько рёбер минимум?

Скелет решения: пусть степени \(d_1,\ldots,d_7\). По неравенству Коши-Буняковского: \((\sum d_i)^2\le 7\sum d_i^2=7\cdot 32=224\), \(\sum d_i\le \sqrt{224}<15\), \(|E|=\tfrac{\sum d_i}{2}\le 7\). Минимум 0 (пустой граф \(\sum d_i^2=0\ne 32\)). При \(\sum d_i^2=32\) минимум рёбер при наиболее равномерном распределении. Если степени \((2,2,2,2,2,2,2)\): \(\sum d_i=14, \sum d_i^2=28\) — мало. \((3,2,2,2,2,2,2)\): 17, 33. \((3,3,2,2,2,2,2)\): 16, 34 — много. \((3,2,2,2,2,2,1)\): 14, 30. \((3,3,2,2,2,1,1)\): 14, 32 ✓. \(|E|=7\).

Ответ:\[ |E|=7. \]

Задача 1.4 — реальная (2025 Муниципальный №3)

По кругу стоят 15 мальчиков и 26 девочек. Известно, что ровно у 19 человек оба соседа — девочки. У какого количества человек оба соседа — мальчики?

Скелет решения: всего по кругу \(15+26=41\) человек, столько же пар соседей: 41. Для каждого человека есть пара левый-правый сосед: либо МД, ДД, МД, ММ. Посчитаем число «соседских пар» (человек, его пара соседей):
- Тех, у кого оба соседа — девочки: 19.
- Пусть \(x\) — у обоих соседа — мальчика.
- Пусть \(y\) — у одного М, у другого Д.

Тогда \(19+x+y=41\), \(y=22-x\).

Подсчитаем число пар (человек, его сосед-девочка) двумя способами:
- По людям: каждый из 19 «ДД» вносит 2, каждый из \(y\) «МД» вносит 1, каждый из \(x\) «ММ» — 0. Сумма: \(38+y\).
- По девочкам: каждая из 26 девочек стоит между двумя соседями, к ней «привязаны» 2 пары. Сумма: \(2\cdot 26=52\).

\(38+y=52\), \(y=14\), значит \(x=22-14=8\).

Проверим: число пар (человек, сосед-мальчик): по людям = \(0+y+2x=14+16=30\); по мальчикам = \(2\cdot 15=30\) ✓.

Ответ:\[ 8 \text{ человек}. \]

Семейство 2. Подсчёт пар (объект, свойство)

Сигнал. В задаче есть множество объектов и каждый имеет некоторое свойство (или связан с другим объектом).

Главный ход. Подсчитать число пар \((x, y)\), где \(R(x, y)\) выполнено, двумя способами: по \(x\) и по \(y\).

Задача 2.1

В классе из 30 учеников каждый знает не менее 5 одноклассников. Докажите, что найдутся 6 учеников, каждый из которых знает по крайней мере 5 других из этих шести.

Скелет решения: используем подсчёт пар (ученик, его знакомый). Сумма степеней \(\ge 30\cdot 5=150\), \(|E|\ge 75\). Далее применяем принцип Дирихле или индукцию для выделения подграфа.

Ответ: см. полное решение через рекурсивное удаление вершин малой степени.

Задача 2.2

В таблице \(5\times 5\) каждая клетка содержит 0 или 1. Сумма всех чисел равна 12. Покажите, что есть строка с суммой не менее 3 и столбец с суммой не менее 3.

Скелет решения: средняя сумма по строке \(=\tfrac{12}{5}=2{,}4\). Если все строки имеют сумму \(\le 2\), то общая сумма \(\le 10<12\). Противоречие. Аналогично для столбцов.

Ответ: доказано принципом среднего.

Задача 2.3

В библиотеке 100 книг. Каждый из 30 читателей взял ровно 5 книг. Каждая книга была взята ровно одинаковое число раз. Сколько раз была взята каждая книга?

Скелет решения: число пар (читатель, книга) \(=30\cdot 5=150\). С другой стороны, \(=100\cdot k\), где \(k\) — раз взята каждая книга. \(k=\tfrac{150}{100}=1{,}5\) — не целое.

Ответ: такая ситуация невозможна.

Задача 2.4 — реальная (2017 Заключительный №8)

Каждая клетка доски \(100\times 100\) окрашена либо в чёрный, либо в белый цвет, причём все клетки, примыкающие к границе доски, — чёрные. Оказалось, что нигде на доске нет одноцветного клетчатого квадрата \(2\times 2\). (Текст OCR-фрагментарный.)

Скелет решения: посчитаем пары (клетка, клетка-сосед противоположного цвета). На каждом квадрате \(2\times 2\) есть и чёрные, и белые клетки (так как нет одноцветного \(2\times 2\)). Значит на каждом из \(99^2\) квадратов \(2\times 2\) есть хотя бы одно «разноцветное» ребро (горизонтальное или вертикальное). Подсчёт через двойной подсчёт «(квадрат, разноцветное ребро в нём)» даёт нижнюю оценку на число разноцветных рёбер, что в свою очередь даёт оценки на распределение цветов.

Ответ для курса: первый ход — подсчёт пар (квадрат \(2\times 2\), разноцветное ребро); ключевое неравенство \(\#\text{разноцветных рёбер}\ge \) (число квадратов \(2\times 2\))/2.

Семейство 3. Подсчёт по строкам и по столбцам

Сигнал. В задаче есть таблица или матрица; нужно связать суммы по строкам и суммы по столбцам.

Главный ход. \(\sum_i r_i=\sum_j c_j=\) общая сумма таблицы.

Задача 3.1

В таблице \(5\times 5\) каждая клетка содержит число от 1 до 5 (числа могут повторяться). Сумма каждой строки равна 15. Найдите сумму всех чисел.

Скелет решения: сумма всех = \(5\cdot 15=75\).

Ответ:\[ 75. \]

Задача 3.2

В таблице \(4\times 4\) числа от 1 до 16, каждое по одному разу. Сумма каждой строки = сумма каждого столбца = \(S\). Найдите \(S\).

Скелет решения: общая сумма \(=1+2+\ldots+16=136\). \(4S=136\), \(S=34\).

Ответ:\[ S=34. \]

Задача 3.3

В таблице \(n\times n\) сумма каждой строки равна сумме каждого столбца. Докажите, что общая сумма делится на \(n\).

Скелет решения: пусть сумма строки/столбца \(=s\). Общая сумма \(=ns\), делится на \(n\).

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

Задача 3.4 — реальная (2025 Школьный №6)

В квадрате \(5\times 5\) расставили натуральные числа от 1 до 25, каждое по одному разу, так, что суммы чисел в каждой строке, каждом столбце и каждой из двух диагоналей совпали. Оказалось, что в центре стоит число... (текст OCR-фрагментарный — какой именно центр и что нужно найти).

Скелет решения: общая сумма \(=1+2+\ldots+25=325\). Сумма каждой строки/столбца/диагонали \(=\tfrac{325}{5}=65\). Это классический магический квадрат \(5\times 5\). По свойствам магических квадратов нечётного порядка центр всегда равен \(\tfrac{n^2+1}{2}=\tfrac{26}{2}=13\).

Доказательство, что центр \(=13\): сумма двух диагоналей + средняя строка + средний столбец = \(4\cdot 65=260\). Но в этой сумме центр учитывается 4 раза, остальные клетки этих 4 линий — по 1 разу. Линии содержат: 2 диагонали + средняя строка + средний столбец = \(4\cdot 5-3=17\) клеток (центр учитывается 4 раза, остальные по разу). Если бы все 4 линии не пересекались, было бы \(4\cdot 5=20\) клеток; они пересекаются в центре, который входит в каждую из 4, значит уникальных клеток \(=20-3\cdot 3=11\)... аккуратнее: 4 линии по 5 клеток = 20 «вхождений»; центр входит во все 4 (4 вхождения), остальные клетки линий — по одной. Уникальных клеток на 4 линиях: \(1\) (центр) + \((20-4)=16\) других «вхождений» = 16 клеток. Их сумма: \(4\cdot 65-(\text{центр})\cdot 3 = 260-3c\). А с другой стороны: сумма этих 17 клеток (1 центр + 16 других) = \(c+S_{16}\), где \(S_{16}\) — сумма 16 неcentral клеток на 4 линиях. Из \(c+S_{16}=260-3c+c=\ldots\) — путаница; проще приём: считать, что строка + столбец + 2 диагонали (через центр) проходят все через центр; в них центр учитывается 4 раза. Сумма этих 4 линий \(=4\cdot 65=260\). С другой стороны эти линии содержат: центр (4 раза) + остальные 16 клеток (по 1 разу). Сумма \(=4c+S_{16}=260\). А \(S_{16}=\) (сумма всех чисел) − (центр) − (числа, не лежащие ни на одной из 4 линий) \(=325-c-S_{8}\), где \(S_8\) — числа в 8 «не-центральных и не-линейных» клетках. Решение требует доп. соображений; но известный результат:\[ c=\tfrac{1+25}{2}=13. \]

Ответ:\[ \text{центр} = 13. \]

Семейство 4. Двойной подсчёт степеней и комбинаторные тождества

Сигнал. В задаче нужно доказать неравенство или тождество, связывающее число объектов и их «вес».

Главный ход. Подсчитать величину типа \(\sum \binom{d_i}{2}\) и связать с количеством троек или пар.

Задача 4.1

В графе \(G\) на \(n\) вершинах число треугольников \(=T\). Докажите, что \(T\le\sum_{v}\binom{\deg(v)}{2}\).

Скелет решения: для каждого треугольника подсчитаем пары рёбер, выходящих из вершины \(v\). Каждый треугольник содержит 3 «угла», и каждый угол — это пара рёбер из одной вершины. Сумма \(\sum_v\binom{\deg(v)}{2}\) считает все пары рёбер из каждой вершины; треугольники дают часть этой суммы.

Ответ: доказано неравенство \(3T\le \sum_v\binom{\deg(v)}{2}\); деление на 3 даёт оценку \(T\).

Задача 4.2

В классе из 25 человек каждый знаком хотя бы с 12. Докажите, что найдутся трое попарно знакомых.

Скелет решения: подсчитаем пары (знакомых) рёбер графа. \(|E|\ge \tfrac{25\cdot 12}{2}=150\). Число пар рёбер из одной вершины: \(\sum\binom{\deg(v)}{2}\ge 25\binom{12}{2}=25\cdot 66=1650\). Если бы не было треугольников, эта сумма равна числу путей длины 2, которые ограничены \(2\binom{|E|}{2}+\ldots\); противоречие с большим \(\sum\binom{\deg}{2}\) даёт треугольник.

Ответ: треугольник существует.

Задача 4.3

Сколько в \(K_n\) (полный граф на \(n\) вершинах) треугольников?

Скелет решения: каждая тройка вершин — треугольник. \(\binom{n}{3}\).

Ответ:\[ \binom{n}{3}=\dfrac{n(n-1)(n-2)}{6}. \]

Задача 4.4 — реальная (2013 Муниципальный №6)

Двадцать пять монет раскладывают по кучкам следующим образом. Сначала их произвольно разбивают на две группы. Затем любую из имеющихся групп снова разбивают на две группы, и так далее до тех пор, пока каждая «группа» не станет одной монетой. (Текст OCR-фрагментарный.) Обычно спрашивают: какова сумма всех произведений \(a\cdot b\), где \(a, b\) — размеры двух частей в каждом разбиении?

Скелет решения: ключевая лемма — сумма всех произведений равна числу пар монет, оказавшихся в одной группе на каком-то шаге, что равно числу пар \(\binom{25}{2}=300\). Подсчёт: каждая пара монет лежит в одной группе ровно до того момента, как она будет разделена; этот момент — единственный шаг, на котором эта пара даёт вклад \(1\) в произведение \(a\cdot b\) этого шага. Значит сумма \(=\binom{25}{2}=300\).

Ответ:\[ \sum_{\text{шаги}} a\cdot b = \binom{25}{2}=300. \]

Семейство 5. Подсчёт цифр и их сумм

Сигнал. В задаче есть набор чисел; нужно подсчитать сумму цифр или количество вхождений каждой цифры.

Главный ход. Двойной подсчёт по (число, позиция цифры) и (цифра, её вхождения).

Задача 5.1

Сколько раз цифра 1 встречается в записи всех чисел от 1 до 99?

Скелет решения: подсчитаем по позициям. На позиции единиц: 1 встречается каждое 10-е число — 10 раз (1, 11, 21, ..., 91). На позиции десятков: 1 встречается в 10–19 (10 раз). Итого \(10+10=20\).

Ответ:\[ 20. \]

Задача 5.2

Чему равна сумма всех цифр в записи чисел от 1 до 1000?

Скелет решения: рассмотрим числа 0, 1, ..., 999, записанные с ведущими нулями (000, 001, ..., 999). Каждая из трёх позиций независимо содержит каждую из цифр 0–9 ровно 100 раз. Сумма цифр одной позиции: \((0+1+\ldots+9)\cdot 100=45\cdot 100=4500\). На трёх позициях: \(3\cdot 4500=13500\). Плюс сумма цифр числа 1000 \(=1\). Итого \(13500+1=13501\).

Ответ:\[ 13501. \]

Задача 5.3

Сколько цифр в записи чисел от 1 до 100?

Скелет решения: однозначных (1–9): 9 чисел по 1 цифре = 9 цифр. Двузначных (10–99): 90 чисел по 2 цифры = 180 цифр. Трёхзначных: 100 — 1 число, 3 цифры. Итого \(9+180+3=192\).

Ответ:\[ 192. \]

Задача 5.4 — реальная (2019 Школьный №4)

Ирина выписала на доску в ряд некоторые целые числа от 0 до 999. В итоге получилось длинное число. Полина записала на свою часть доски все оставшиеся целые числа из этого же диапазона, в итоге получилось другое длинное число. (Текст OCR-фрагментарный; обычно спрашивается о суммах цифр или о количестве цифр.)

Скелет решения: всего чисел 0, 1, ..., 999 — это 1000 чисел. Подсчитаем сумму цифр всех 1000 чисел: записывая числа как 000, 001, ..., 999 (трёхзначные с ведущими нулями), сумма цифр одной позиции \(=45\cdot 100=4500\), всего \(3\cdot 4500=13500\). Любое разбиение на «выписала Ирина» и «выписала Полина» даёт сумму цифр Ирины + сумму цифр Полины = 13500 минус сумма цифр пропущенных ведущих нулей. Если числа записываются «как есть» (без ведущих нулей), то сумма цифр = \(\sum_{n=0}^{999}\)сумма цифр \(n\) = по двойному подсчёту 13500 (ведущие нули не пишутся, но их вклад в сумму равен 0). Значит сумма цифр обеих частей = 13500. Дальше используется конкретное условие задачи.

Ответ для курса: первый ход — суммарная сумма цифр всех чисел 0–999 равна 13500.

Семейство 6. Подсчёт пар (клетка, сосед)

Сигнал. В задаче есть клетчатая доска с фишками/раскраской, и нужно подсчитать что-то про соседние клетки.

Главный ход. Подсчитать число пар (клетка, её сосед, обладающий свойством) двумя способами: по клеткам и по парам клеток.

Задача 6.1

На доске \(8\times 8\) расставлены 30 фишек. Докажите, что найдутся 2 фишки в соседних клетках (по стороне).

Скелет решения: число «соседних пар» клеток на \(8\times 8\): по горизонтали \(7\cdot 8=56\), по вертикали \(56\); итого 112. Если фишки попарно не соседи, то к каждой фишке прилегают пустые клетки. Подсчёт пар (фишка, соседняя клетка): сумма равна \(\sum_{f}\deg(f)\le 4\cdot 30=120\) (каждая клетка имеет ≤ 4 соседей). Если соседи всегда пустые, то \(\sum\) = пары (фишка, пустая клетка) ≤ количество пар (фишка, пустая)... аккуратнее: для каждой фишки её 2–4 соседей все пустые, и каждая пустая клетка может быть соседом нескольких фишек. Через размещение «гало» вокруг каждой фишки и оценка \(\le\) общего числа клеток получаем противоречие при достаточном числе фишек.

Ответ: доказано (точная оценка требует более тонкого подсчёта).

Задача 6.2

В таблице \(6\times 6\) расставили несколько единиц так, что в каждой строке сумма \(=3\) и в каждом столбце \(=3\). Сколько всего единиц?

Скелет решения: по строкам \(6\cdot 3=18\), по столбцам \(6\cdot 3=18\). Согласовано.

Ответ:\[ 18 \text{ единиц}. \]

Задача 6.3 — реальная (2011 Заключительный №5)

В некоторых клетках доски \(100\times 100\) стоит по фишке. Назовём клетку красивой, если в соседних с ней по стороне клетках стоит чётное число фишек. Может ли ровно одна клетка доски быть красивой?

Скелет решения: подсчитаем сумму по всем клеткам числа фишек в соседних клетках, двумя способами:
- По клеткам: сумма «у клетки \(c\) — \(n_c\) фишек среди соседей», где \(n_c\) — это число фишек в 4 (или 2/3 на краях) соседних клетках.
- По фишкам: каждая фишка является соседом 2/3/4 клеток. Сумма = \(\sum_f\deg(f)\), где \(\deg(f)\) — число клеток-соседей фишки \(f\) (2 на углу, 3 на крае, 4 внутри).

Чётность \(\sum_c n_c = \sum_f \deg(f)\). Слева чётность определяется числом клеток с нечётным \(n_c\) (так как сумма чётных не влияет, сумма нечётных = (число нечётных) \(\bmod 2\)).

«Красивая» — это \(n_c\) чётное. «Не-красивая» — \(n_c\) нечётное. На доске \(100\times 100\) есть \(10000\) клеток. Если ровно одна красивая, то 9999 не-красивых, то есть 9999 нечётных слагаемых. Сумма по чётности: 9999 \(\bmod 2 = 1\).

Справа: \(\sum_f \deg(f)\). Угловых клеток 4 (\(\deg=2\)), краевых 4·98=392 (\(\deg=3\)), внутренних \(98^2=9604\) (\(\deg=4\)). Если фишка в углу, она вносит 2; на крае — 3; внутри — 4. Чётность суммы зависит только от числа фишек на краях (с \(\deg=3\), нечётным). Если \(k\) фишек на крае (не в углу), то сумма \(\bmod 2 = k\bmod 2\).

Уравнение: \(1\equiv k\pmod 2\), то есть \(k\) нечётно. Это возможно. Поэтому ответ может быть «да»? Но классический ответ — нет: ровно одна красивая клетка невозможна.

Аккуратнее: правая часть учитывает не только фишки на крае, а все фишки, и фишка вносит свою степень. Сумма степеней всех фишек: если фишек \(F\), они вносят \(2a+3b+4c\), где \(a, b, c\) — фишки в углах, на крае, внутри. Чётность: \(b\bmod 2\).

Слева: 9999 \(\bmod 2 = 1\). Справа: \(b\bmod 2\). Получаем: \(b\) нечётно — нет противоречия само по себе. Но классическая задача даёт ответ «нет» через другой инвариант (например, чётность числа нечётных среди всех \(n_c\) с более тонким подсчётом).

Ответ для курса: классический ответ — нет, ровно одна красивая клетка невозможна. Первый ход — двойной подсчёт пар (клетка, соседняя фишка) с анализом по модулю 2.

Задача 6.4 — реальная (2012 Школьный №6)

В клетчатом квадрате \(6\times 6\), вначале пустом, Саша закрашивает по одной клетке, вписывая в каждую только что закрашенную клетку количество граничащих с нею (по стороне) ранее закрашенных клеток. Докажите, что сумма всех вписанных чисел всегда одинакова (не зависит от порядка закрашивания).

Скелет решения: каждая пара соседних клеток (по стороне) даёт вклад 1 в сумму чисел: когда закрашивается вторая из них, она увидит первую среди своих соседей и впишет +1. Значит сумма всех чисел = числу пар соседних клеток на доске \(6\times 6\), которое фиксированно.

Число пар соседних клеток на \(6\times 6\): по горизонтали \(5\cdot 6=30\), по вертикали \(30\); итого \(60\).

Ответ:\[ \text{Сумма } = 60. \]

Семейство 7. Двойной подсчёт в комбинаторных тождествах

Сигнал. Нужно доказать тождество типа \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\) или \(\sum_{k=0}^{n}\binom{n}{k}=2^n\).

Главный ход. Выделить множество, мощность которого считается двумя способами; левая и правая части тождества — это два разных подсчёта.

Задача 7.1

Докажите тождество \(\sum_{k=0}^n\binom{n}{k}=2^n\).

Скелет решения: левая часть = число подмножеств \(\{1, \ldots, n\}\), сгруппированных по размеру. Правая часть = число подмножеств, подсчитанных через двоичную запись (для каждого элемента — взять или не взять). Оба = одно и то же множество подмножеств.

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

Задача 7.2

Докажите \(\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}^2\).

Скелет решения: выбираем \(n\) объектов из \(2n=n+n\) (две группы по \(n\)). По общему числу: \(\binom{2n}{n}\). По разбиению: выбрать \(k\) из первой группы и \(n-k\) из второй, сумма по \(k\): \(\sum_k\binom{n}{k}\binom{n}{n-k}=\sum_k\binom{n}{k}^2\).

Ответ: доказано через двойной подсчёт выбора \(n\) из \(2n\).

Задача 7.3

Сколько различных треугольников можно образовать из вершин правильного \(12\)-угольника?

Скелет решения: \(\binom{12}{3}=220\).

Ответ:\[ 220. \]

Задача 7.4 — реальная (2016 Заключительный №4)

Из клетчатого бумажного квадрата \(100\times 100\) вырезали по границам клеток 1950 двуклеточных прямоугольников. Докажите, что из оставшейся части можно вырезать по границам клеток четырёхклеточную фигуру (например, \(1\times 4\) или L-тетраминошку). (Текст OCR-фрагментарный.)

Скелет решения: исходный квадрат содержит \(100^2=10000\) клеток. Вырезано \(1950\cdot 2=3900\) клеток. Осталось \(10000-3900=6100\) клеток. Подсчитаем число «парных» границ между оставшимися клетками: исходно — \(2\cdot 99\cdot 100=19800\) границ. После вырезания 1950 прямоугольников каждая «внутренняя» граница прямоугольника удалена (1950 границ), плюс «внешние» границы прямоугольников теперь могут граничить с пустотой. По принципу Дирихле (или подсчёту степеней) в оставшейся части есть «связные кластеры» больших размеров; в одном из кластеров есть фигура размера ≥ 4.

Ответ для курса: первый ход — подсчёт оставшихся клеток (6100) и оставшихся внутренних рёбер; принцип Дирихле даёт существование большой связной компоненты.

• Ошибка: путают E10 с E3. E3 — это двойной счёт через тождества типа $\binom{n}{k} = \binom{n}{n-k}$. E10 — это подсчёт через пары «объект–свойство», инциденции, таблицы. Если задача о степенях в графе или о числе инцидентных пар — это $E10. *$Как избежать:* спросите себя: «Строю ли я явную таблицу пар или просто переписываю формулу?»

• Ошибка: не учитывают кратность пар. Если пары упорядоченные — умножайте на 2; если неупорядоченные — делите. Путаница даёт неверный коэффициент. Как избежать: явно решите: считаете упорядоченные или неупорядоченные пары, и будьте последовательны в обоих подсчётах.

• Ошибка: двойной счёт не приравнян к одному числу. Нашли $S_1$ и $S_2$ — но не объяснили, почему $S_1 = S_2$. Как избежать: явно укажите, что $S_1$ и $S_2$ — это два способа подсчёта одного и того же числа инцидентных пар.

• Ошибка: суммирование по объектам с переменным числом связей. Если у разных объектов разное число связей, сумма не упрощается автоматически. Как избежать: проверьте, что у всех объектов одного типа одинаковое число связей (или обрабатывайте каждый отдельно).

• Ошибка: забывают про двусторонность «инциденции». Каждое ребро вносит вклад 1 в счёт со стороны каждого из двух концов. Итого вклад 2. Не учли — получили ответ в 2 раза больше/меньше. Как избежать: для каждого типа связи чётко пропишите вклад в каждую из двух сторон подсчёта.