Математика — страница 10
Числа, дроби, величины и понятные вычисления.

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