Доказательства и комбинаторные модели — страница 2
Строить доказательства, контрпримеры и конечные подсчёты, не заменяя обоснование перебором примеров.
Объяснения и разобранные примеры
Почему доказать существование ещё не значит доказать единственность
Почему доказать существование ещё не значит доказать единственность. Утверждение о единственном объекте требует двух доводов: подходящий объект существует, а любые два подходящих объекта совпадают.
Как выбор из двух групп объясняет тождество Вандермонда
выбор из двух групп объясняет тождество Вандермонда. Выбор r объектов из групп размеров m и n можно разделить по числу k объектов первой группы.
Числа Стирлинга второго рода: разбиваем различимые элементы на группы
Доказываем рекурсию по положению последнего элемента, различаем состав групп и размеры частей, затем связываем неподписанные непустые группы с подписанными ящиками.
Числа Стирлинга первого рода: считаем перестановки по числу циклов
Переводим перестановку в непересекающиеся направленные циклы, доказываем рекурсию вставкой нового элемента и отличаем циклический порядок от неупорядоченной группы.
Сопряжённое разбиение: меняем число частей и наибольшую часть
Строим столбцы диаграммы по длинам строк, доказываем обратимость сопряжения и переносим ограничения на число и размер частей, не смешивая их с условием различных слагаемых.
Нечётные и различные части: биекция через двоичные кратности
Строим взаимно обратимые преобразования разбиений с нечётными частями и с различными частями, доказываем отсутствие повторов через нечётное ядро и объясняем роль двоичной записи.
Разрез графа: почему можно разделить хотя бы половину рёбер
Доказываем существование разреза через среднее число пересекающих рёбер и строим его последовательным выбором доли; отличаем гарантию от максимума и от полной двудольности.
Теорема Эрдёша — Секереша: длинная монотонная подпоследовательность
Доказываем конечную гарантию rs+1 через пары длин, заканчивающихся в каждой позиции, строим резкий пример на rs членах и сохраняем исходный порядок индексов.
Теорема Шпернера: сколько подмножеств могут не содержать друг друга
Доказываем взвешенную оценку через полные цепи и перестановки, получаем центральный биномиальный предел и отличаем необходимое неравенство от критерия несравнимости.
Теорема Холла: почему общего числа мест недостаточно
Проверяем объединения допустимых выборов для каждой группы и доказываем критерий разных представителей; отличаем нехватку внутри группы от общего числа мест.
Теорема Кёнига: паросочетание и покрытие всех рёбер
Строим минимальное вершинное покрытие двудольного графа по чередующейся достижимости и доказываем равенство его размера наибольшему паросочетанию.
Теорема Дилворта: сколько цепей нужно частичному порядку
Связываем наибольшую антицепь с наименьшим разбиением на цепи и доказываем равенство через два экземпляра каждого элемента и паросочетание.
Числа Рамсея: как соседи одной вершины дают рекурсию
Доказываем R(r,s)≤R(r−1,s)+R(r,s−1), разделяя соседей по цвету ребра; отличаем найденную верхнюю оценку от точного числа.
Вероятностный метод: раскраска без одноцветной клики
Считаем ожидаемое число запрещённых полных подграфов и из среднего меньше единицы доказываем существование раскраски без них; не путаем нижнюю границу Рамсея с верхней.
Сбалансированная матрица: как разложить назначения на перестановки
Доказываем разложение целочисленной матрицы с одинаковыми суммами строк и столбцов, затем получаем смесь перестановок для дважды стохастической матрицы.
Код Прюфера: восстановление дерева и подсчёт по степеням
Кодируем помеченное дерево удалением наименьшего листа, доказываем обратимость и получаем n^(n−2) и число деревьев с заданными степенями.
Отложенное принятие: почему устойчивое назначение существует
Строим паросочетание по строгим полным предпочтениям, доказываем остановку алгоритма Гейла–Шепли и отсутствие пары, желающей совместно сменить партнёров.
Лучший устойчивый партнёр: что даёт сторона предложений
Доказываем, что отложенное принятие даёт каждому предлагающему лучшего доступного в устойчивых решениях партнёра, а принимающим — худшего среди устойчивых; различаем это с первым выбором вообще.
Частые вопросы
Как работать с темой «Доказательства и комбинаторные модели»?
Выберите объяснение из списка, восстановите ход примера своими словами и ответьте на проверочный вопрос. Если к теме подключён инструмент, им можно проверить свои данные.
Можно ли вернуться к более простой теме?
Да. Откройте учебную карту или ссылки на необходимые основы перед списком материалов. Уровень по классу помогает выбрать сложность и не ограничивает доступ.