E10b Двойной счёт через инциденции

Идея метода: E10b — это специализация метода E10 (двойной счёт) для задач, где основной объект подсчёта — инциденции: пары вида «точка лежит на прямой», «вершина принадлежит гиперграфу», «элемент входит в блок». Метод состоит в том, чтобы считать число таких инцидентных пар двумя способами — по строкам и по столбцам матрицы инциденций.

Отличие от E10: в E10 «двойной счёт» понимается широко (пары, суммы, таблицы). В E10b акцент строго на матрице инциденций $M$ размера $|P| \times |L|$ (точки × линии или объекты × блоки), где $M_{ij} = 1$, если объект $i$ инцидентен блоку $j$. Сумма всех $M_{ij}$ — одно число, которое можно считать двумя способами.

Метод особенно мощен в задачах о геометрических конфигурациях (сколько точек на скольких прямых), в теории блок-схем (комбинаторные дизайны) и в экстремальной комбинаторике (оценки Сильвестра–Галлая, теорема о числе прямых).

Аналогия: таблица посещаемости (строки — студенты, столбцы — занятия, 1 — студент пришёл). Сумма по строкам = суммарная посещаемость каждого студента. Сумма по столбцам = суммарная наполненность каждого занятия. Оба дают «общее число визитов».

• Двойной счёт инциденций (основная лемма): Пусть $M$ — матрица инциденций ($|P| \times |L|$). Тогда $\sum_{p \in P} d(p) = \sum_{l \in L} d(l) = \mathrm{ones}(M)$, где $d(p)$ — число блоков, содержащих $p$; $d(l)$ — число точек в блоке $l$. Когда использовать: задачи о конфигурациях «точки–линии», «элементы–подмножества».

• Теорема о числе пар: Число инцидентных пар $(p, l)$ также равно $\sum_{p \neq p'} \lambda(p,p')$, где $\lambda(p,p')$ — число блоков, содержащих оба $p$ и $p'$. Отсюда: $|P|(|P|-1)\bar{\lambda} = |P|\cdot r(r-1)$ для регулярных конфигураций. Когда использовать: задачи о комбинаторных дизайнах ($(v,b,r,k,\lambda)$-дизайны).

• Теорема Фишера: В $(v,b,r,k,\lambda)$-дизайне $b \geq v$. Следствие: нельзя накрыть $v$ точек блоками по $k$ так, чтобы каждая пара встречалась $\lambda$ раз, используя меньше $v$ блоков. Когда использовать: оценки снизу на число блоков/прямых.

• Неравенство Сильвестра–Галлая: Если $n$ точек на плоскости не все коллинеарны, то существует «обычная прямая» (содержащая ровно 2 точки$). *$Доказательство через двойной счёт инциденций пар (точка, прямая$).* *$Когда использовать:* задачи о конфигурациях точек и прямых.

• Составить матрицу инциденций: строки = точки/объекты, столбцы = блоки/линии. Заполнить 0 и 1. Подсчитать суммы строк и столбцов.

• Считать пары (объект, блок) фиксируя объект: $\sum_{p} d(p)$ — для каждой точки $p$ берём число блоков с $p$.

• Считать те же пары, фиксируя блок: $\sum_{l} |l|$ — для каждого блока берём его размер.

• Двойной счёт пар точек через блоки: $\sum_{l} \binom{|l|}{2}$ = число пар точек, обе из которых в одном блоке = $\sum_{\{p,p'\}} \lambda(p,p')$. Если $\lambda$ одинаково — $\lambda \binom{v}{2}$.

• Применение к геометрии: «прямая» = блок, содержащий точки на ней. Двойной счёт числа пар (точка, прямая) — классическая техника.

• Оценка через регулярность: если все строки матрицы имеют одинаковую сумму $r$ (каждая точка в $r$ блоках) — $|P| \cdot r = |L| \cdot k$ (если все блоки одинакового размера $k$). Это «уравнение регулярности».

Поверхностные признаки (что буквально написано):
- «Каждые две точки лежат ровно на одной прямой» (или $\lambda$ прямых).
- «Каждая прямая содержит ровно $k$ точек».
- «Докажите, что число прямых $\geq$ число точек».

Структурные признаки (форма выражения, объекты):
- Конфигурация точек и линий (или объектов и блоков) с заданными параметрами регулярности.
- Матрица 0–1, где нужно подсчитать число единиц.
- Задача о комбинаторном дизайне или конечной геометрии.

Цель задачи (что от тебя хотят):
- Найти число блоков/прямых через двойной счёт.
- Доказать нижнюю оценку на число блоков (теорема Фишера).
- Доказать существование «особой» прямой или блока.

Задача 1. Число прямых в конфигурации (двойной счёт)

Условие: На плоскости расположены $n$ точек так, что никакие 3 из них не коллинеарны. Через каждые 2 точки проведена прямая. Сколько прямых получилось? Докажите через двойной счёт инциденций.

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу? Точки и прямые — матрица инциденций. Каждая прямая содержит ровно 2 точки (никакие 3 не коллинеарны). Каждые 2 точки дают ровно 1 прямую.$2. *$Двойной счёт пар (точка, прямая$):*$ по прямым: каждая прямая содержит 2 точки, прямых $b$ → сумма $2b$. По точкам: каждая точка лежит на $n-1$ прямых → сумма $n(n-1)$.$3. *$Равенство:* $2b = n(n-1)$, откуда $b = \frac{n(n-1)}{2} = \binom{n}{2}$.

Решение:

Обозначим число прямых $b$. Считаем число инцидентных пар «(точка, прямая)» двумя способами.

• По точкам: каждая из $n$ точек лежит ровно на $n-1$ прямых (через неё проходит $n-1$ прямых, по одной с каждой из остальных точек). Итого $n(n-1)$.
• По прямым: каждая прямая содержит ровно 2 точки (условие: никакие 3 не коллинеарны). Итого $2b$.

Равенство: $2b = n(n-1)$, откуда $b = \dfrac{n(n-1)}{2}$.

Ответ: $b = \dbinom{n}{2}$.

Что главное: матрица инциденций «точки × прямые» дала уравнение сразу.

Задача 2. Комбинаторный дизайн

Условие: Дано множество из $v = 7$ точек и 7 блоков по $k = 3$ точки каждый (проективная плоскость Фано). Каждая точка входит ровно в $r = 3$ блока. Каждые 2 точки входят ровно в $\lambda = 1$ общий блок. Проверьте двойным счётом, что параметры согласованы.

Источник: классическая конструкция (плоскость Фано, уровень ВсОШ заключ.)

Как думать (рассуждение ученика$):
1. *$Что вижу?* Параметры $(v, b, r, k, \lambda) = (7, 7, 3, 3, 1)$. Нужно проверить согласованность через двойной счёт.$2. *$Уравнение $1:*$ считаем пары «(точка, блок)» — $vr = bk$: $7 \cdot 3 = 7 \cdot 3 = 21$. ✓$3. *$Уравнение $2:*$ считаем пары точек через блоки — $b\binom{k}{2} = \lambda\binom{v}{2}$: $7 \cdot 3 = 1 \cdot 21 = 21$. ✓

Решение:

Проверяем два соотношения двойного счёта:

1. Пары (точка, блок): по точкам = $vr = 7 \cdot 3 = 21$; по блокам = $bk = 7 \cdot 3 = 21$. Равны. ✓

2. Пары точек, лежащих в одном блоке: по блокам = $b\binom{k}{2} = 7 \cdot 3 = 21$; по парам точек = $\lambda\binom{v}{2} = 1 \cdot 21 = 21$. Равны. ✓

Оба уравнения выполнены — параметры согласованы. (Реализация — плоскость Фано — существует.)

Ответ: Параметры согласованы: $vr = bk$ и $b\binom{k}{2} = \lambda\binom{v}{2}$.

Что главное: двойной счёт инциденций — это необходимое условие существования дизайна. Проверка двух уравнений обязательна.

• Ошибка: путают E10b с E10. E10 — общий двойной счёт. E10b — строго через матрицу инциденций «точки × блоки» с явными регулярными параметрами $r$, $k$, $\lambda$. Как избежать: если задача о конкретных конфигурациях (точки и прямые, дизайны) — это E10b.

• Ошибка: не проверяют оба уравнения согласованности. Для $(v,b,r,k,\lambda)$-дизайна нужны два уравнения: $vr = bk$ и $\lambda(v-1) = r(k-1)$. Проверка только первого — недостаточна. Как избежать: всегда пишите оба уравнения.

• Ошибка: считают упорядоченные пары вместо неупорядоченных (или наоборот). $\binom{v}{2} = v(v-1)/2$ — неупорядоченные; $v(v-1)$ — упорядоченные. Путаница в 2 раза. Как избежать: выберите одно соглашение и будьте последовательны в обоих подсчётах.

• Ошибка: теорему Фишера ($b \geq v$) применяют без проверки условий. Теорема работает для $(v,b,r,k,\lambda)$-дизайна с $\lambda \geq 1$ и $k < v$. Как избежать: проверьте, что перед вами именно дизайн с постоянным $\lambda$.

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