Математика — страница 10

Числа, дроби, величины и понятные вычисления.

Синяя и оранжевая половины складываются в целый круг.
Практика · вопросов: 236

Разобраться в теме

Объяснение, примеры и вопрос для себя

Отложенное принятие: почему устойчивое назначение существует

Строим паросочетание по строгим полным предпочтениям, доказываем остановку алгоритма Гейла–Шепли и отсутствие пары, желающей совместно сменить партнёров.

Читать и практиковаться

Разрез графа: почему можно разделить хотя бы половину рёбер

Доказываем существование разреза через среднее число пересекающих рёбер и строим его последовательным выбором доли; отличаем гарантию от максимума и от полной двудольности.

Читать и практиковаться

Теорема Холла: почему общего числа мест недостаточно

Проверяем объединения допустимых выборов для каждой группы и доказываем критерий разных представителей; отличаем нехватку внутри группы от общего числа мест.

Читать и практиковаться

Теорема Кёнига: паросочетание и покрытие всех рёбер

Строим минимальное вершинное покрытие двудольного графа по чередующейся достижимости и доказываем равенство его размера наибольшему паросочетанию.

Читать и практиковаться

Обращение Мёбиуса: как восстановить слагаемые по суммам делителей

Определяем знаки функции Мёбиуса, доказываем взаимное уничтожение по делителям и восстанавливаем f(n) из F(n)=Σf(d); учитываем квадраты простых.

Читать и практиковаться

Нечётные и различные части: биекция через двоичные кратности

Строим взаимно обратимые преобразования разбиений с нечётными частями и с различными частями, доказываем отсутствие повторов через нечётное ядро и объясняем роль двоичной записи.

Читать и практиковаться

Сопряжённое разбиение: меняем число частей и наибольшую часть

Строим столбцы диаграммы по длинам строк, доказываем обратимость сопряжения и переносим ограничения на число и размер частей, не смешивая их с условием различных слагаемых.

Читать и практиковаться

Третий слева и пятый справа: как место помогает узнать длину ряда

Различаем количество и порядковое место, восстанавливаем число предметов по месту одного предмета с двух концов и объясняем вычитание общей единицы.

Читать и практиковаться

Код Прюфера: восстановление дерева и подсчёт по степеням

Кодируем помеченное дерево удалением наименьшего листа, доказываем обратимость и получаем n^(n−2) и число деревьев с заданными степенями.

Читать и практиковаться

Вероятностный метод: раскраска без одноцветной клики

Считаем ожидаемое число запрещённых полных подграфов и из среднего меньше единицы доказываем существование раскраски без них; не путаем нижнюю границу Рамсея с верхней.

Читать и практиковаться

Числа Рамсея: как соседи одной вершины дают рекурсию

Доказываем R(r,s)≤R(r−1,s)+R(r,s−1), разделяя соседей по цвету ребра; отличаем найденную верхнюю оценку от точного числа.

Читать и практиковаться

Римские числа: складываем группы и проверяем разрешённое вычитание

Читаем распространённую школьную римскую запись через значения семи знаков, разбиваем её на разрешённые вычитаемые пары и отличаем её от десятичной позиционной записи.

Читать и практиковаться

Теорема Шпернера: сколько подмножеств могут не содержать друг друга

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

Читать и практиковаться

Лучший устойчивый партнёр: что даёт сторона предложений

Доказываем, что отложенное принятие даёт каждому предлагающему лучшего доступного в устойчивых решениях партнёра, а принимающим — худшего среди устойчивых; различаем это с первым выбором вообще.

Читать и практиковаться

Числа Стирлинга первого рода: считаем перестановки по числу циклов

Переводим перестановку в непересекающиеся направленные циклы, доказываем рекурсию вставкой нового элемента и отличаем циклический порядок от неупорядоченной группы.

Читать и практиковаться

Числа Стирлинга второго рода: разбиваем различимые элементы на группы

Доказываем рекурсию по положению последнего элемента, различаем состав групп и размеры частей, затем связываем неподписанные непустые группы с подписанными ящиками.

Читать и практиковаться

Соседние целые количества: следующий есть всегда, предыдущий у нуля отсутствует

Строим соседей неотрицательного целого прибавлением и вычитанием единицы, учитываем нижнюю границу и отличаем соседство от соседних напечатанных подписей.

Читать и практиковаться

Перекладывание между двумя наборами: почему разность меняется вдвое быстрее

Отслеживаем обе стороны переноса, сохраняем общее количество и вычисляем изменение разности как сумму уменьшения первого набора и увеличения второго.

Читать и практиковаться

Два вида предметов: сначала представим, что все одинаковые

Находим количества двух типов по общему числу предметов и суммарному вкладу, объясняем деление превышения на разность вкладов и проверяем целочисленность.

Читать и практиковаться

Знаки перед векторами: как гарантировать короткую сумму

Доказываем существование выбора плюсов и минусов через средний квадрат длины и получаем последовательное построение; различаем квадрат нормы, сумму длин и точный минимум.

Читать и практиковаться
Выбрать другой предмет