Комбинаторика и логика

Относится к заданиям: 12, 90

Содержание

Особенности комбинаторики и логики на ДВИ
Основные формулы и методы
Алгоритм подхода к логическим задачам
Метод инвариантов и чётности
Принцип Дирихле через остатки
Математическая индукция
Примеры разбора задач
Оформление под рубрику ДВИ
Частые ошибки
Что запомнить
Стратегия на ДВИ

Особенности комбинаторики и логики на ДВИ

Задачи на логику, комбинаторику и теорию множеств — это, как правило, последние номера варианта (задача №7 или №8). Их главная особенность в том, что здесь нет стандартных школьных алгоритмов вроде «взять производную» или «решить квадратное уравнение».

От тебя требуется построить математическую модель (граф, систему уравнений, разбить на множества) и строго доказать результат. Проверяющие оценивают полноту логических переходов: если ты угадал ответ, но не доказал, что других вариантов нет, задача будет оценена в 0 баллов.

Лист формул на ДВИ не выдают, поэтому формулы комбинаторики нужно не зубрить, а уметь восстанавливать из смысла подсчёта. Ниже формулы даны вместе с короткими выводами — именно так их и надо держать в голове.

Основные формулы и методы

Для решения комбинаторных задач на ДВИ достаточно уверенного владения базовыми формулами и принципами подсчёта.

СОВЕТ

Как восстановить формулы без листа (вывод

C_n^k = A_n^k / k!

)

Размещение — это упорядоченный выбор $k$ из $n$ : первый элемент можно взять $n$ способами, второй $(n-1)$ , ..., $k$ -й — $(n-k+1)$ способами. Отсюда сразу

A_n^k = n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}.

Сочетание отличается от размещения тем, что порядок не важен. Каждый неупорядоченный набор из $k$ элементов можно упорядочить $k!$ способами (это перестановки внутри набора). Значит размещений ровно в $k!$ раз больше, чем сочетаний:

A_n^k = C_n^k \cdot k! \;\Longrightarrow\; C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{k!(n-k)!}.

Так формулу можно вывести на экзамене за 20 секунд, а не вспоминать наизусть.

Помимо прямых формул, на ДВИ часто встречается сведение задачи к распределению предметов.

Иллюстрация метода шаров и перегородок для конкретного случа

СОВЕТ

Откуда берётся

C_{n+k-1}^{k-1}

(вывод через перегородки)

Изобразим число $n$ как $n$ одинаковых шаров в ряд. Чтобы разбить их на $k$ групп (значения $x_1, \dots, x_k$ ), нужно поставить $k-1$ перегородку. Всего в ряду стоит $n$ шаров и $k-1$ перегородок — это $n + k - 1$ позиций. Выбрать, на каких $k-1$ из них стоят перегородки, можно $C_{n+k-1}^{k-1}$ способами. Нули разрешены — две перегородки могут стоять рядом (пустая группа). Если же все слагаемые строго положительны, перегородки ставят в $n-1$ промежуток между соседними шарами: $C_{n-1}^{k-1}$ .

ВАЖНОЕ

Принцип Дирихле — сильная и обобщённая форма

Сильная форма (без всяких условий на $n, m$ ): при любом распределении $n$ предметов по $m$ ящикам найдётся ящик, содержащий не менее

\left\lceil \frac{n}{m} \right\rceil

предметов (округление вверх).

Слабая форма (удобна для существования): если $n > m$ (предметов больше, чем ящиков), то хотя бы в одном ящике лежит $\geqslant 2$ предмета.

Обобщённая форма: если предметов больше, чем $k\cdot m$ , то в каком-то ящике окажется $\geqslant k+1$ предмет.

Внимание: оценка $\left\lceil \frac{n}{m}\right\rceil$ верна всегда, без условия $n>m$ . Условие $n>m$ нужно только слабой форме (она даёт лишь $\geqslant 2$ ). Не привязывай сильную оценку к $n>m$ — это методическая ошибка.

ВАЖНОЕ

Принцип включений-исключений

Для двух множеств:

|A \cup B| = |A| + |B| - |A\cap B|.

Для трёх множеств:

|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|.

Смысл: сложили все, вычли двойные пересечения (их посчитали дважды), вернули тройное (его вычли трижды и трижды добавили). Подробнее и диаграмма Венна — см. справочник.

Диаграмма Венна для двух множеств — формула включений-исключений

ВАЖНОЕ

Метод двойного подсчёта

Если одну и ту же величину (число пар, число «инцидентностей», сумму) посчитать двумя разными способами, результаты обязаны совпасть. Приравняв их, получаем уравнение. Это главный рабочий приём комбинаторных задач ДВИ: «считаем по элементам = считаем по объектам».

Типичные применения:

сумма степеней вершин графа $= 2\cdot(\text{число рёбер})$ ;
число пар «человек–человек», «точка–окружность» считаем и со стороны людей/окружностей, и со стороны точек/ответов.

ВАЖНОЕ

Метод «Оценка + Пример» (для задач на максимум/минимум)

Когда требуется найти наибольшее/наименьшее возможное значение $N$ , полный балл даёт только связка из двух независимых частей:

Оценка. Доказать, что больше (меньше) нельзя: $N \leqslant a$ (или $N \geqslant a$ ) — строгое рассуждение для любой конфигурации.
Пример (конструкция). Предъявить конкретную конфигурацию, на которой значение $a$ достигается.

Если есть только оценка — это « $\pm$ » (примерно половина баллов). Только пример без оценки — тоже неполно. Ответ $N=a$ обоснован, лишь когда есть обе части.

Алгоритм подхода к логическим задачам

В задачах про «правдивцев и лжецов» или перебор конфигураций действуй по чёткому плану:

АЛГОРИТМ

Стратегия поиска решения

Формализуй условие. Введи переменные: пусть $T$ — количество правдивцев, $L$ — количество лжецов.
Найди инвариант или закономерность для пар. Рассмотри, что происходит, когда общаются люди одного типа и разных типов. Составь матрицу или систему уравнений.
Организуй перебор по крайним случаям. Если нужно найти оценку, предполагай экстремальные значения (пусть все лжецы или пусть граф полный).
Докажи отсутствие других решений. Составленное уравнение обычно имеет ограничение в целых числах (например, $T \geqslant 0$ , $L \geqslant 0$ ).

Метод инвариантов и чётности

Часть «логических» задач ДВИ формулируется как «можно ли из состояния X получить состояние Y набором операций». Лобовой перебор тут бесполезен — состояний бесконечно много. Работает поиск инварианта.

Принцип Дирихле через остатки

Геометрический Дирихле (см. Пример 3) — лишь один сюжет. Не менее частый — числовой: в роли «ящиков» берут остатки по модулю.

Математическая индукция

Совет «проверь закономерность на $N=3,4,5$ » — это лишь способ угадать ответ. Для полного балла угаданное надо доказать, и универсальный строгий инструмент здесь — математическая индукция.

Примеры разбора задач

Пример 1. Правдивцы и лжецы (двойной подсчёт пар)

В закрытом клубе каждый участник является либо правдивцем (всегда говорит правду), либо лжецом (всегда лжёт). Каждого из участников спросили про каждого из остальных, кем он является — правдивцем или лжецом. В результате было получено 24 ответа «он лжец» и 18 ответов «он правдивец». На сколько отличается количество правдивцев от количества лжецов в этом клубе?

Разбираем типы ответов

Пусть в клубе $T$ правдивцев и $L$ лжецов. Всего было задано $(T+L)(T+L-1)$ вопросов, так как каждый оценивает каждого, кроме себя.

Выясним, какие ответы дают участники в зависимости от их типа:

Правдивец оценивает правдивца: он скажет правду, ответ — «правдивец».
Лжец оценивает лжеца: на самом деле тот лжец, но оценивающий соврёт, поэтому ответ — «правдивец».
Правдивец оценивает лжеца: скажет правду, ответ — «лжец».
Лжец оценивает правдивца: на самом деле тот правдивец, но оценивающий соврёт, ответ — «лжец».

Следовательно:

Любая пара людей одного типа (оба правдивцы или оба лжецы) даёт друг на друга ровно два ответа «правдивец».
Любая пара людей разных типов (один правдивец, другой лжец) даёт друг на друга ровно два ответа «лжец».

Составляем уравнения (двойной подсчёт)

Количество пар людей разных типов равно произведению $T \cdot L$ . Каждая такая пара генерирует два ответа «лжец». По условию таких ответов 24:

2 \cdot T \cdot L = 24 \implies T \cdot L = 12.

Количество пар людей одного типа равно $C_T^2$ (пары правдивцев) плюс $C_L^2$ (пары лжецов). Каждая такая пара даёт два ответа «правдивец». По условию:

2 \cdot C_T^2 + 2 \cdot C_L^2 = 18 \implies T(T-1) + L(L-1) = 18.

Решаем квадратное уравнение

Раскроем скобки во втором уравнении:

T^2 - T + L^2 - L = 18 \implies (T+L)^2 - 2TL - (T+L) = 18.

Подставим $TL = 12$ :

(T+L)^2 - 2(12) - (T+L) - 18 = 0 \implies (T+L)^2 - (T+L) - 42 = 0.

Сделаем замену $S = T+L$ . Получаем квадратное уравнение $S^2 - S - 42 = 0$ . Его корни $S = 7$ и $S = -6$ . Так как число людей не может быть отрицательным, $T+L = 7$ .

Находим ответ по теореме Виета

Имеем систему:

\begin{cases} T + L = 7 \\ T \cdot L = 12 \end{cases}

По теореме, обратной теореме Виета, числа $T$ и $L$ являются корнями уравнения $x^2 - 7x + 12 = 0$ . Корни этого уравнения: 3 и 4. Значит, в клубе либо 4 правдивца и 3 лжеца, либо 3 правдивца и 4 лжеца. Разница между их количеством: $|4 - 3| = 1$ .

Ответ: На $1$ .

Пример 2. Комбинаторная геометрия (двойной подсчёт инцидентностей)

На плоскости нарисовано несколько окружностей. Известно, что любые две из них пересекаются ровно в двух точках. Всего на плоскости образовалось 12 различных точек пересечения. В 8 из них пересекаются ровно две окружности, а в остальных 4 точках — ровно три окружности (точек, где пересекается больше трёх окружностей, нет). Сколько окружностей нарисовано на плоскости?

Считаем пересечения по парам окружностей

Пусть на плоскости нарисовано $n$ окружностей. Количество всевозможных пар окружностей равно $C_n^2$ . По условию любые две окружности пересекаются ровно в двух точках. Следовательно, если мы сложим точки пересечения для каждой пары в отдельности, мы должны получить ровно $2 \cdot C_n^2$ точек (при этом реальные точки на плоскости будут посчитаны несколько раз).

Считаем те же пересечения по точкам

Посчитаем этот же объём пересечений, опираясь на сами точки на плоскости:

Точка, в которой пересекаются ровно 2 окружности, принадлежит ровно одной паре окружностей. Таких точек 8, они дают $8 \cdot 1 = 8$ «парных пересечений».
Точка, в которой пересекаются ровно 3 окружности, принадлежит сразу $C_3^2 = 3$ различным парам окружностей. Таких точек 4, они дают $4 \cdot 3 = 12$ «парных пересечений».

Приравниваем и решаем уравнение

Суммируем все пересечения по парам: $8 + 12 = 20$ . Приравниваем к формуле через общее количество окружностей:

2 \cdot C_n^2 = 20 \implies C_n^2 = 10.

Распишем сочетания:

\frac{n(n-1)}{2} = 10 \implies n^2 - n - 20 = 0.

Корни уравнения: $n = 5$ и $n = -4$ . Так как количество окружностей натуральное число, ответ 5.

Ответ: $5$ .

Пример 3. Принцип Дирихле и геометрическая оценка

В квадрате со стороной 1 бросили 51 точку. Докажи, что среди них найдутся три точки, которые можно накрыть кругом радиуса $\dfrac{1}{7}$ .

Разбиваем квадрат и применяем Дирихле

Разобьём исходный квадрат $1 \times 1$ на 25 маленьких равных квадратиков со стороной $\dfrac{1}{5}$ (проведя по 4 прямые, параллельные сторонам).

У нас есть 25 клеток (маленьких квадратиков) и 51 точка («кролики»). По принципу Дирихле (обобщённая форма), так как $51 = 25 \cdot 2 + 1 > 2\cdot 25$ , хотя бы в один из маленьких квадратиков попадёт не менее трёх точек.

Оцениваем радиус накрывающего круга

Рассмотрим этот маленький квадратик со стороной $\dfrac{1}{5}$ и его центр $O$ . Диагональ квадратика равна $\dfrac{1}{5} \cdot \sqrt{2} = \dfrac{\sqrt{2}}{5}$ , поэтому любая точка квадратика удалена от центра $O$ не более чем на половину диагонали:

R = \dfrac{\sqrt{2}}{10}.

Значит круг с центром в $O$ и радиусом $R = \dfrac{\sqrt2}{10}$ накрывает весь квадратик, а вместе с ним и все три попавшие в него точки.

Проверяем, что круг помещается в радиус 1/7

Осталось проверить, что этот круг помещается в круг радиуса $\dfrac17$ , то есть что $R = \dfrac{\sqrt2}{10} < \dfrac17$ . Сравним радиусы:

\dfrac{\sqrt{2}}{10} \vee \dfrac{1}{7}.

Умножим крест-накрест (обе части положительны):

7\sqrt{2} \vee 10.

Возведём в квадрат:

49 \cdot 2 \vee 100 \implies 98 < 100.

Следовательно, $R = \dfrac{\sqrt{2}}{10} < \dfrac{1}{7}$ . Тогда круг радиуса $\dfrac17$ с тем же центром $O$ тем более накрывает все три точки (он содержит круг радиуса $R$ ). Утверждение доказано.

Ответ: Утверждение доказано.

Пример 4. Включения-исключения

В классе 30 учеников. Английский язык изучают 18 человек, немецкий — 15, а 8 учеников изучают сразу оба языка. Сколько учеников класса не изучают ни одного из этих двух языков?

Пример 5. Включения-исключения для трёх множеств (делимость)

Сколько среди чисел от 1 до 100 таких, которые не делятся ни на 2, ни на 3, ни на 5?

Считаем одиночные множества

Обозначим: $A$ — числа от 1 до 100, делящиеся на 2; $B$ — делящиеся на 3; $C$ — делящиеся на 5. Количество кратных $d$ среди $1,\dots,100$ равно $\left\lfloor \dfrac{100}{d}\right\rfloor$ .

Одиночные множества:

|A| = \left\lfloor\tfrac{100}{2}\right\rfloor = 50, \quad |B| = \left\lfloor\tfrac{100}{3}\right\rfloor = 33, \quad |C| = \left\lfloor\tfrac{100}{5}\right\rfloor = 20.

Считаем пересечения

Попарные пересечения (число делится сразу на оба — значит на их произведение, так как $2, 3, 5$ попарно взаимно просты):

|A\cap B| = \left\lfloor\tfrac{100}{6}\right\rfloor = 16, \quad |A\cap C| = \left\lfloor\tfrac{100}{10}\right\rfloor = 10, \quad |B\cap C| = \left\lfloor\tfrac{100}{15}\right\rfloor = 6.

Тройное пересечение (делится на $2\cdot3\cdot5 = 30$ ):

|A\cap B\cap C| = \left\lfloor\tfrac{100}{30}\right\rfloor = 3.

Применяем формулу включений-исключений

По формуле включений-исключений количество чисел, делящихся хотя бы на одно из $2, 3, 5$ :

|A\cup B\cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

Тогда не делятся ни на одно из них:

100 - 74 = 26.

Ответ: $26$ чисел.

Пример 6. Инвариант (чётность суммы)

На доске выписаны все натуральные числа от 1 до 2025. За один ход разрешается стереть любые два числа $a$ и $b$ и вместо них записать их модуль разности $|a-b|$ . После 2024 таких ходов на доске останется одно число. Может ли это число быть чётным?

Пример 7. Дирихле по остаткам

Докажи, что среди любых 12 целых чисел найдутся два, разность которых делится на 11.

Пример 8. Индукция (доказательство делимости)

Докажи, что при любом натуральном $n$ число $n^3 + 2n$ делится на 3.

Пример 9. Бином Ньютона (член без

x

)

Найди член разложения $\left(x + \dfrac{1}{x^2}\right)^9$ , не содержащий $x$ .

Пример 10. Оценка + Пример (максимум с конструкцией)

Из чисел $1, 2, \dots, 30$ выбрали несколько так, что никакие два выбранных числа не дают в сумме 31. Какое наибольшее количество чисел можно выбрать?

Пример 11. Чистая логика (рыцари и лжецы)

На острове живут рыцари (всегда говорят правду) и лжецы (всегда лгут). Встретились два жителя, $A$ и $B$ . Житель $A$ сказал: «Хотя бы один из нас двоих — лжец». Кто из них рыцарь, а кто лжец?

Перебор гипотез о жителе A

Переберём два возможных типа жителя $A$ (третьего не дано) и для каждого проверим непротиворечивость.

Гипотеза о $A$	Должна ли фраза быть истинной	Истинна ли фраза на самом деле	Вывод
$A$ — лжец	фраза ложна	«хотя бы один лжец» — но $A$ уже лжец, значит фраза истинна	противоречие
$A$ — рыцарь	фраза истинна	значит реально есть лжец; раз это не $A$ , то лжец — $B$	согласовано

Разбираем случаи подробно

Пусть $A$ — лжец. Тогда его фраза должна быть ложной. Но фраза «хотя бы один из нас — лжец» при лжеце $A$ истинна (лжец-то как раз есть — это сам $A$ ). Лжец не может произнести истинное утверждение — противоречие. Значит этот случай невозможен.
Следовательно $A$ — рыцарь. Тогда его фраза истинна: среди двоих действительно есть лжец. Сам $A$ рыцарь, поэтому лжец — это $B$ .

Ответ: $A$ — рыцарь, $B$ — лжец.

Оформление под рубрику ДВИ

ДВИ проверяют по outcomes-рубрике: за каждую задачу ставят полный балл, « $\pm$ » (частично) или 0. « $\pm$ » обычно означает, что идея верна, но доказательство неполно. Чтобы получить полный балл, оформляй решение по эталону ниже.

АЛГОРИТМ

Эталон полного решения

Введи обозначения и модель. Явно: «Пусть $T$ — число правдивцев…», «Обозначим $A$ — множество…». Без введённых переменных рассуждение нечитаемо.
Сформулируй ключевой шаг словами. «Посчитаем число пар двумя способами», «Рассмотрим инвариант — чётность суммы». Проверяющий должен видеть метод, а не угадывать его.
Для задач на max/min — отдельно «Оценка» и отдельно «Пример». Подпиши эти части. Оценка без примера — это « $\pm$ ».
Доведи до числа и проверь ограничения. Отбрось посторонние корни ( $S=-6$ , $n=-4$ — отрицательное число людей/окружностей невозможно), укажи, почему оставшийся ответ единственный.
Запиши явный ответ. Отдельной строкой «Ответ: …». Для задач «докажите» — «Утверждение доказано».

ЧАСТАЯ ОШИБКА

За что снимают баллы до «±»

Оценка без примера (или пример без оценки) в задаче на максимум/минимум — половина баллов.
«Угадал ответ, но не доказал единственность» — не отброшены другие конфигурации/корни.
Пропущенный случай в переборе (например, забыл проверить $\cos x = 0$ , крайнюю конфигурацию, граничный остаток).
Слова «очевидно», «нетрудно видеть» вместо записанного шага — проверяющий вправе счесть шаг недоказанным.
Не введены обозначения — рассуждение формально нечитаемо, даже если по сути верно.

Частые ошибки

ЧАСТАЯ ОШИБКА

Шары-перегородки: «неотрицательные» против «натуральных»

Ошибка: Применить $C_{n+k-1}^{k-1}$ , когда по условию все слагаемые должны быть строго положительными (например, «раздать конфеты так, чтобы каждому досталось хотя бы по одной»), или наоборот. Правильно: Сначала чётко определи, разрешены ли нулевые слагаемые. Нули разрешены — формула $C_{n+k-1}^{k-1}$ . Каждому нужно $\geqslant 1$ — формула $C_{n-1}^{k-1}$ (или сначала «выдай по одной всем», уменьшив $n$ на $k$ , и сведи к неотрицательному случаю).

Что запомнить

Двойной подсчёт: если в задаче элементы взаимодействуют (дружат, оценивают, пересекаются) — считай количество взаимодействий двумя разными способами и приравнивай.
Включения-исключения: «хотя бы один из…», «не делится ни на…», «знают хотя бы один язык» — сложи множества и аккуратно вычти пересечения.
Дирихле: если просят доказать существование сгущения (точек, чисел одного остатка) — ищи, что взять за «клетки» (часто остатки по модулю), а что за «кроликов».
Инвариант: для «можно ли получить…» ищи сохраняющуюся величину (чётность, остаток, раскраску); разные значения у начала и конца = переход невозможен.
Индукция: угадал на малых $n$ — докажи база→шаг, иначе это лишь гипотеза.
Оценка + Пример: задача на max/min не закрыта, пока нет обеих частей.

Стратегия на ДВИ

СОВЕТ

Экзаменационная тактика

Логика и комбинаторика на ДВИ — не отдельный номер варианта, а сюжет, который встречается в нестандартной задаче; читай её первой, но решай последней: подсознание будет обрабатывать её, пока ты решаешь уравнения и неравенства. Заложи на финальный номер 30-40 минут с запасом на оформление «оценки + примера».
Если задача кажется сложной — реши её для $N=3, 4, 5$ . Нарисуй руками. На ДВИ закономерность на малых числах почти всегда масштабируется — но помни: малые числа дают гипотезу, а полный балл требует строгого доказательства (индукция, инвариант, двойной подсчёт).
Избегай слов «очевидно», «нетрудно понять». Проверяющим на мехмате ничего не очевидно, пока не записана формула или не перебраны все возможные случаи. Пиши словами каждый свой логический шаг.

Проверь себя

Выбираем капитана и заместителя из 10 человек (роли разные). Какая формула считает число способов?
Сколько способов представить $n = 10$ в виде суммы $k = 4$ целых неотрицательных слагаемых (порядок важен)?
Среди любых 12 целых чисел найдутся два, разность которых делится на 11. Почему?
В задаче «найдите наибольшее $N$ » ты доказал, что $N \leqslant 15$ . Что ещё нужно для полного балла?

Комбинаторика и логика

Особенности комбинаторики и логики на ДВИ

Основные формулы и методы

Алгоритм подхода к логическим задачам

Метод инвариантов и чётности

Принцип Дирихле через остатки

Математическая индукция

Примеры разбора задач

Разбираем типы ответов

Составляем уравнения (двойной подсчёт)

Решаем квадратное уравнение

Находим ответ по теореме Виета

Считаем пересечения по парам окружностей

Считаем те же пересечения по точкам

Приравниваем и решаем уравнение

Разбиваем квадрат и применяем Дирихле

Оцениваем радиус накрывающего круга

Проверяем, что круг помещается в радиус 1/7

Считаем изучающих хотя бы один язык

Находим остальных

Считаем одиночные множества

Считаем пересечения

Применяем формулу включений-исключений

Находим инвариант

Считаем начальную чётность

Задаём ящики-остатки и применяем Дирихле

Проверяем делимость разности

База и предположение

Индукционный шаг

Записываем общий член разложения

Находим номер члена без x

Оценка сверху

Пример на достижение

Перебор гипотез о жителе A

Разбираем случаи подробно

Оформление под рубрику ДВИ

Частые ошибки

Что запомнить

Стратегия на ДВИ