Комбинаторика и логика — ДВИ

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

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

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

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

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

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

ВАЖНОЕ

Базовые комбинаторные формулы

Число перестановок из $n$ элементов (порядок важен, участвуют все):

P_{n} = n!

Число размещений из $n$ по $k$ (порядок важен, выбираем часть):

A_{n}^{k} = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)

Число сочетаний из $n$ по $k$ (порядок НЕ важен):

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

Полный список свойств сочетаний и бинома — см. справочник, раздел «Комбинаторика, множества, логика».

✓СОВЕТ

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

C_{n}^{k} = A_{n}^{k} / k!

)

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

A_{n}^{k} = n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!} .

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

A_{n}^{k} = C_{n}^{k} \cdot k! ⟹ C_{n}^{k} = \frac{A _{n}^{k}}{k !} = \frac{n !}{k ! ( n - k )!} .

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

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

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

ВАЖНОЕ

Метод шаров и перегородок

Количество способов представить натуральное число $n$ в виде суммы $k$ целых неотрицательных слагаемых (порядок слагаемых важен):

x_{1} + x_{2} + \dots + x_{k} = n ⟹ C_{n + k - 1}^{k - 1} способов .

Если слагаемые строго натуральные (больше нуля), формула меняется на $C_{n - 1}^{k - 1} .$

✓СОВЕТ

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

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$ ящикам найдётся ящик, содержащий не менее

⌈ \frac{n}{m} ⌉

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

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

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

Внимание: оценка $⌈ \frac{n}{m} ⌉$ верна всегда, без условия $n > m .$ Условие $n > m$ нужно только слабой форме (она даёт лишь $⩾ 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 (число рёбер);$
число пар «человек–человек», «точка–окружность» считаем и со стороны людей/окружностей, и со стороны точек/ответов.

ВАЖНОЕ

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

Когда требуется найти наибольшее/наименьшее возможное значение $N,$ полный балл даёт только связка из двух независимых частей:
1. Оценка. Доказать, что больше (меньше) нельзя: $N ⩽ a$ (или $N ⩾ a$ ) — строгое рассуждение для любой конфигурации.
2. Пример (конструкция). Предъявить конкретную конфигурацию, на которой значение $a$ достигается.

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

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

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

АЛГОРИТМ

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

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

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

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

ВАЖНОЕ

Инвариант

Инвариант — величина, которая не меняется (или меняется предсказуемо: например, сохраняет чётность) при каждой разрешённой операции. Если у начального и конечного состояний значения инварианта разные — переход невозможен. Самые частые инварианты: чётность суммы/произведения, остаток по модулю, раскраска (шахматная доска).

✓СОВЕТ

Раскраска шахматной доской

Многие задачи про замощение доминошками, ходы фигур, перекрашивание клеток решаются раскраской доски в два цвета. Доминошка $1 \times 2$ всегда накрывает одну белую и одну чёрную клетку — это инвариант. Если в фигуре белых и чёрных клеток разное количество, замостить доминошками её нельзя.

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

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

ВАЖНОЕ

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

Среди любых $m + 1$ целых чисел найдутся два, дающих одинаковый остаток при делении на $m$ (ящиков-остатков всего $m :$ $0, 1, \dots, m - 1$ ). Разность таких двух чисел делится на $m .$

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

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

АЛГОРИТМ

Схема индукции

1. База. Проверь утверждение при наименьшем $n$ (обычно $n = 1$ ).
2. Предположение. Допусти, что утверждение верно при $n = k .$
3. Шаг. Докажи, что тогда оно верно и при $n = k + 1$ (опираясь на предположение).
4. Вывод. «По принципу математической индукции утверждение верно для всех $n$ ».

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

ПРИМЕР 1

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

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

ПРИМЕР 2

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

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

ПРИМЕР 3

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

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

ПРИМЕР 4

Включения-исключения

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

ПРИМЕР 5

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

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

ПРИМЕР 6

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

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

ПРИМЕР 7

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

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

ПРИМЕР 8

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

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

ПРИМЕР 9

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

x

)

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

ПРИМЕР 10

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

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

ПРИМЕР 11

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

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

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

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

АЛГОРИТМ

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

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

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

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

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

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

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

Оценка без примера

Ошибка: В задаче вида «найдите наибольшее/наименьшее значение...» доказать неравенство (оценку) и сразу записать ответ.
Правильно: Обязательно привести конкретный пример конфигурации (чисел, графа, множества), при котором достигается найденное значение. Метод называется «Оценка + Пример». Без примера решение считается неполным и теряет половину баллов.

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

Путаница между

C_{n}^{k}

A_{n}^{k}

Ошибка: Использовать сочетания $C_{n}^{k},$ когда порядок элементов имеет значение (например, выбор капитана и заместителя из команды).
Правильно: Задавай себе проверочный вопрос: «Изменится ли результат, если я поменяю выбранные элементы местами?». Если да — это размещения ( $A_{n}^{k}$ ), если нет — сочетания ( $C_{n}^{k}$ ).

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

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

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

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

Двойной учёт при подсчёте пар

Ошибка: Смешать упорядоченные и неупорядоченные пары. В П1 каждая пара даёт два ответа (каждый оценивает каждого) — легко по ошибке посчитать один и потерять множитель 2.
Правильно: Заранее реши, считаешь ли ты упорядоченные пары (тогда их $n (n - 1)$ ) или неупорядоченные ( $C_{n}^{2}$ ), и держись этого выбора во всём решении.

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

Off-by-one в принципе Дирихле

Ошибка: Перепутать сильную и слабую формы: из $n > m$ заключить, что «в каком-то ящике $⩾ ⌈ n / m ⌉$ », хотя $n > m$ даёт лишь $⩾ 2;$ либо неверно округлить $⌈ n / m ⌉ .$
Правильно: Для гарантии « $⩾ k$ » проверяй обобщённую форму: нужно, чтобы предметов было больше $(k - 1) \cdot m .$ В П3: чтобы попало $⩾ 3,$ нужно $> 2 \cdot 25 = 50$ точек; у нас 51 — годится.

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

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

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

✓СОВЕТ

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

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

Проверь себя0 из 4

1.Выбираем капитана и заместителя из 10 человек (роли разные). Какая формула считает число способов?

2.Сколько способов представить

n = 10

в виде суммы

k = 4

целых неотрицательных слагаемых (порядок важен)?

3.Среди любых 12 целых чисел найдутся два, разность которых делится на 11. Почему?

4.В задаче «найдите наибольшее

N

» ты доказал, что

N ⩽ 15 .

Что ещё нужно для полного балла?