Дидактические цели
Университетская лаборатория по оптимизации и дискретной математике об одной задаче, которая встречается в пяти обличьях: разбить на пары учеников, которые ладят друг с другом, расставить камеры на улицах района, выбрать для каждого кружка своего делегата, распределить документы между переводчиками и направить студентов на практику в компании. Блоки A, B и F доступны старшеклассникам.
Сквозная мысль: наибольшее паросочетание доказывается. «Это наибольшее» подтверждается покрытием того же размера (Кёниг), «совершенного нет» — множеством Холла, оптимальное назначение — приведённой матрицей с независимыми нулями. Лаборатория никогда не говорит «это оптимально», не показав сертификата.
Порядок — порядок опыта, а не оглавления учебника. В первом зале нет ни одного термина: ученик составляет пары руками и застревает. Слова «максимальное» и «наибольшее» появляются только тогда, когда разница уже прожита с несмываемым маркером. В каждом зале, где вычисляется число (ν, τ, оптимальная стоимость, сколько нужно обменов), ученик сначала записывает свой прогноз.
Чему учит лаборатория
- Отличать максимальное паросочетание (к нему нельзя добавить ребро) от наибольшего (в нём больше всего рёбер) и видеть, почему жадный метод останавливается на первом.
- Улучшать паросочетание, обращая увеличивающий путь, и узнавать, когда таких путей больше нет (теорема Бержа).
- Проходить алгоритм увеличивающих путей шаг за шагом, с поиском в глубину и неудачными ветвями, и видеть препятствие нечётных циклов, которое преодолел Эдмондс.
- Понимать вершинное покрытие и неравенство ν ≤ τ, и видеть, что в двудольных графах выполняется равенство (теорема Кёнига).
- Изучать паросочетание и покрытие вместе через согласованную пару и её дефект и доводить дефект до нуля двумя операциями: менять только M или только C.
- Решать, можно ли насытить одну долю двудольного графа, всегда предъявляя сертификат: паросочетание или множество S с |N(S)| < |S| (теорема Холла), и применять это к регулярным доскам и карточному фокусу.
- Решать задачи о назначениях со стоимостями венгерским методом, понимая, почему вычитание константы из строки или столбца не меняет решения и почему минимальное число линий — это снова Кёниг.
- Находить блокирующие пары, проходить алгоритм Гейла–Шепли по раундам и убеждаться, что выигрывает тот, кто делает предложения.
- Увидеть, как выглядит совершенное паросочетание, выбранное наугад (блок G): замощения ацтекского бриллианта доминошками и шестиугольника ромбами, в которых возникает арктический круг.
Ключевые математические идеи
- Каждый результат — с сертификатом. Паросочетание и покрытие следят друг за другом: каждой паре нужна своя камера, поэтому всегда |M| ≤ |C|, а при равенстве ни то, ни другое улучшить нельзя.
- Увеличивающий путь даёт ровно одно ребро. Рёбер вне M в нём на одно больше, чем внутри. Поэтому, начиная с нуля, дойти до совершенного паросочетания в графе 7 + 7 всегда стоит 7 обменов.
- Дефект считает свободные вершины C. В согласованной паре f = |C| − |M| — это ровно число вершин покрытия, оставшихся без пары. Обе операции его уменьшают; в двудольном графе он всегда доходит до нуля, и тогда оба сертификата налицо одновременно.
- Нечётные циклы — препятствие. В треугольнике или пятиугольнике ν < τ, и дефект не опускается ниже 1.
- Условие Холла необходимо и достаточно. Если ни у какой группы кружков кандидатов не меньше, чем кружков, делегаты найдутся для всех. На доске, где в каждой строке и каждом столбце r закрашенных клеток, всегда помещаются n ладей, а из колоды, разложенной на 13 стопок по 4, всегда можно вытащить все 13 значений.
- Вычитание из линии уменьшает все суммы одинаково. Порядок назначений не меняется, а назначение из одних нулей в матрице без отрицательных чисел оптимально.
- Кто предлагает, тот и выигрывает. Обе версии Гейла–Шепли дают устойчивые назначения, каждое — лучшее из возможных для предлагающей стороны.
Благодарности
Залы «Согласованные пары», «Операция 1», «Операция 2», «Нулевой дефект» и «Ладьи на закрашенных клетках» основаны на листке Паросочетания и покрытия Вани Яковлева (Кроссворд Тьюринга, https://d1-d57.github.io/matchings/), откуда взяты понятия согласованной пары и дефекта.
Заметки для урока
- «Несмываемый маркер» объясняет разницу между максимальным и наибольшим за тридцать секунд.
- «Операция 2»: цепная реакция очень хорошо смотрится на проекторе. Стоит спросить класс, замкнётся ли цепочка, прежде чем её запускать.
- «Нулевой дефект»: момент, когда M и C подтверждают друг друга, — лучшее введение в теорему Кёнига.
- «Карточный фокус»: перетасовать три-четыре раза перед классом и попросить добровольца найти выбор.
- Маршрут для старшеклассников: блоки A → B → F. Блоки C, D и E требуют университетского уровня, а E опирается на зал «Нулевой дефект».
Содержание по залам
Зал 1 · Пары для практикума
Двенадцать друзей хотят работать парами; каждая линия — дружба. Без единого термина ученик составляет пары, нажимая на линии или на обоих друзей. В графе (решётка 3 × 4 с несколькими диагоналями) разбить всех двенадцать на пары можно единственным способом; при случайном выборе тупик наступает в 94 % случаев, и в большинстве тупиков разрушить одну пару недостаточно. Зал распознаёт каждый тупик и предлагает что-нибудь отменить; после двух тупиков называет тех, кто остался один, после четырёх показывает решение.
Задания для ученика
- Составить шесть пар, чтобы никто не остался один.
Зал 2 · Несмываемый маркер
Пары рисуются маркером и не стираются, а на каждой доске кто-то уже наспех отметил одну. Когда больше ничего не помещается, ученик отвечает, можно ли, начав заново, составить больше пар. Три доски подобраны так, чтобы интуиция подводила: на первой всегда можно улучшить, на второй остаются две свободные вершины, и всё же больше ни одной пары не поместить (без центра остаются три треугольника), а на третьей ответ зависит от того, что отмечено. Затем — определения максимального и наибольшего паросочетаний и два отдельных вопроса о них, а в конце задача: если маркер застрял на 5 парах, в наибольшем не больше 10.
Задания для ученика
- На трёх досках решить, можно ли составить больше пар.
- Ответить, всякое ли наибольшее максимально и всякое ли максимальное наибольшее.
- Оценить наибольшее паросочетание по максимальному из 5 рёбер.
Зал 3 · Сколько пар можно составить?
Четыре графа, в которых «половина вершин» — не ответ или ответ не очевиден: дерево из 9 вершин (ν = 3), два центра с четырьмя треугольниками (14 вершин, ν = 6), доска 4 × 4 без двух противоположных углов (ν = 6) и граф Петерсена (ν = 5). Ученик предсказывает ν, глядя на граф, а затем должен вручную построить паросочетание такого размера; объяснение появляется, только если прогноз неверен. В конце — рассуждение в духе Татта (20 вершин; если убрать одну, остаётся 5 нечётных кусков: не больше 8 пар). Задача с доской связана с домино из лаборатории «Полимино».
Задания для ученика
- Предсказать ν для четырёх графов и построить паросочетание такого размера.
- Оценить ν с помощью нечётных кусков.
Зал 4 · Обмен
Начинается с анимации на маленьком графе: что такое увеличивающий путь и что им не является (путь, заканчивающийся синим ребром, и путь с двумя неиспользованными рёбрами подряд), правильный путь, нарисованный ребро за ребром, и анимированный обмен, добавляющий одну пару. Анимацию можно пересмотреть из любого задания. У вершин нет имён. Задания: лестница из 8 вершин (2 × 4) с двумя уже отмеченными парами, которые не входят вместе ни в одно совершенное паросочетание: отдельными рёбрами всегда застреваешь на 3 парах, а чтобы дойти до 4, нужен путь хотя бы из 3 рёбер (заканчивается кнопкой «Уже наибольшее», которая проверяется); единственный увеличивающий путь из 5 рёбер с тупиковыми ветками; граф из 12 вершин, где без предупреждения нужны два обмена; двудольный граф 6 + 6 с единственным путём из 7 рёбер; и числовой вопрос о M △ M′ (|M| = 5, |M′| = 8: не меньше 3 увеличивающих путей).
Задания для ученика
- Посмотреть анимацию увеличивающего пути и обмена.
- Нарастить пустое паросочетание до наибольшего.
- Найти и обменять увеличивающие пути из 5 и 7 рёбер и дойти до наибольшего за два обмена.
- Оценить, сколько увеличивающих путей в M △ M′.
Зал 5 · Найди путь
Три графа с максимальным, но не наибольшим паросочетанием; в каждом ученик должен найти увеличивающий путь (годится любой) и применить его. В первом, двудольном 6 + 6 с четырьмя свободными вершинами, всего два пути по 5 рёбер, и оба выходят из свободной вершины b3: b2 не конец ни одного из них, так что начинать с неё — терять время. Во втором (12 вершин, не двудольный, с треугольниками) две свободные вершины и единственный путь из 7 рёбер; развилки настоящие, а ребро из 8 в 9 ведёт в тупик. Третий — цветок: путь обходит цикл из 5 вершин по длинной стороне, а короткий путь между двумя свободными вершинами не чередуется. После решения появляется Эдмондс (1965) и проблема нечётных циклов. После трёх ошибок подряд путь показывается.
Задания для ученика
- Найти увеличивающий путь в двудольном графе, правильно выбрав свободную вершину для старта.
- Найти единственный путь в графе с треугольниками и тупиками.
- Решить цветок и понять, почему короткий путь не годится.
Зал 6 · Дипломные проекты
Алгоритм увеличивающих путей, выполненный вручную. Шесть студентов (a1…a6) выбирают проект среди шести (b1…b6), каждый только среди тех, что ему интересны, и обрабатываются по очереди: в каждый ход нужно отметить увеличивающий путь, начинающийся ровно в том, чья очередь (другое начало отвергается). Если бы каждый студент брал первый свободный проект из своего списка, ходы a5 и a6 решались бы только перестановкой других: цепочки из 3 и 5 рёбер. После обмена сразу начинается следующий ход, на том же поле. Затем на случайном двудольном графе 7 + 7 без совершенного назначения (ν равно 5 или 6) нужно предсказать, скольким студентам самое большее можно дать проект; при ошибке показывается группа студентов, у которой проектов меньше, чем студентов, а если ответ был занижен — ещё и назначение. Последнее задание — на другом графе 7 + 7 из набора трудных (ν = 6, 18–20 рёбер и всего 4 наибольших паросочетания): построить наибольшее паросочетание с нуля и самому решить, когда нажать «Уже наибольшее», — кнопка срабатывает, только когда это так.
Задания для ученика
- Отметить увеличивающий путь каждого студента, от a1 до a6.
- Предсказать, скольким студентам можно дать проект в случайном графе 7 + 7.
- Построить наибольшее паросочетание с нуля и понять, когда увеличить его уже нельзя.
Зал 7 · Уже наибольшее?
Теорема Бержа как решение «да/нет»: четыре доски с отмеченным паросочетанием и вопрос «оно наибольшее или его можно увеличить?». Первые две доски двудольные 6 + 6: на первой остаются четыре свободные вершины и есть два пути по 5 рёбер; на второй свободных всего две, и путей нет (у a3, a4, a5 и a6 рёбра ведут только к b4, b5 и b6). Остальные две не двудольные, по 12 вершин: на третьей есть чередующиеся цепочки до 10 рёбер, заканчивающиеся в занятой вершине, и всё же паросочетание наибольшее; на четвёртой единственный путь из 7 рёбер. Кто отвечает «можно увеличить», должен отметить путь; кто отвечает «наибольшее» и ошибся, переходит к поиску пути. Неверный выбор ветви считается ошибкой, а после трёх ошибок показывается путь или, для наибольших, самая длинная цепочка, которая заходит в тупик, и причина оценки. Верный ответ «наибольшее» доказывать не требует: пока ему верят на слово. В конце формулировка теоремы Бержа.
Задания для ученика
- На четырёх досках решить, наибольшее ли паросочетание или его можно увеличить.
- Отметить увеличивающий путь, когда он есть, в том числе в недвудольных графах.
- Отличить длинную чередующуюся цепочку, не доходящую до свободной вершины, от настоящего увеличивающего пути.
Зал 8 · Пары против камер
Камеры на перекрёстках квартала из 14 перекрёстков и 17 улиц (сетка 3 × 6 с пропусками): каждая просматриваемая улица подсвечивается. Три задания. Сначала предсказывают наименьшее число камер, а потом расставляют их: при раскраске в шахматном порядке 7 перекрёстков одного цвета уже просматривают всё, но минимум равен 6, он единственный и содержит оба цвета. Затем в том же квартале строят одновременно паросочетание M и покрытие C с |M| = |C| = 6. Наконец, граф Петерсена (3-регулярный, 15 улиц): чему равно τ? Первая подсказка напоминает, что каждая камера просматривает 3 из 15 улиц; вторая — что 5 камер просматривали бы 5 · 3 = 15 улиц, ровно все, и ни у одной улицы не было бы камер на обоих концах; она предлагает посмотреть на внешний пятиугольник. По окончании задания (правильно ответил ученик или ошибся трижды) на поле всегда показывают покрытие из 6 камер и доказательство того, что 5 не хватает: при 5 камерах у каждой улицы камера стояла бы ровно на одном конце, поэтому вдоль любого цикла перекрёстки чередовались бы «с камерой» и «без камеры», а во внешнем пятиугольнике (5 вершин, нечётное число) это невозможно; значит, τ ≥ 6, а на поле видно, что 6 хватает. Каждая непросматриваемая улица и каждая лишняя камера отмечаются при проверке.
Задания для ученика
- Предсказать и расставить наименьшее число камер (6), просматривающих все улицы.
- Построить одновременно паросочетание и покрытие одного размера.
- Найти τ в графе Петерсена и разобрать доказательство того, что 5 камер не хватает.
Зал 9 · Каким может быть ν?
При заданном τ какие значения может принимать ν? Сначала идёт исследование без оценки: два ползунка (τ от 3 до 7 и число треугольников t) рисуют t непересекающихся треугольников и ещё τ − 2t отдельных рёбер и подписывают τ и ν = τ − t, пока ничего не объясняя. Затем ученик строит граф из палитры фигур, которые добавляются как непересекающиеся компоненты и могут быть убраны (ребро, путь из 3, треугольник, цикл из 4, цикл из 5 и K₄); τ и ν всего графа не показываются сразу, только после нажатия «Проверить». Задания: τ = 6 при как можно меньшем ν (3, три треугольника), τ = 6 при как можно большем ν (6, фигуры с τ = ν, например рёбра) и τ = 7 при ν = 4 не более чем из 3 фигур, что вынуждает взять два треугольника и цикл из 5 или K₄. Если у графа τ = 6, но ν не крайнее, зал сообщает, что можно получить меньшее или большее. Затем при τ = 9: какие значения может принимать ν? Любое от 5 до 9; каждый неверный вариант опровергается контрпримером. В конце на экране остаётся теорема ν ≤ τ ≤ 2ν с доказательством обоих неравенств.
Задания для ученика
- Исследовать двумя ползунками, как меняются τ и ν.
- Построить из фигур граф с τ = 6 и наименьшим ν, ещё один с наибольшим ν и ещё один с τ = 7 и ν = 4 не более чем из 3 фигур.
- Решить, какие значения может принимать ν при τ = 9.
Зал 10 · Согласованные пары
Паросочетание и покрытие изучаются одновременно. После двух определений (пара (M, C) согласована, если C покрывает и у каждого ребра из M ровно один конец в C; дефект равен f = |C| − |M|) ученик решает на двух двудольных графах 6 + 6, согласована ли показанная пара; из четырёх вариантов ошибка каждого объясняется отдельно. В первом у ребра a3–b3 из M оба конца в C; во втором пара согласована (f = 2), хотя у нескольких рёбер вне M оба конца в C — в этом и соблазн. Затем вопрос, что гарантирует f = 0: что M наибольшее, а C наименьшее, потому что |M| ≤ ν ≤ τ ≤ |C|. Последнее задание: построить согласованную пару с f = 0 в двудольном графе 7 + 7 с 19 рёбрами, где ν = τ = 6 и единственное наименьшее покрытие берёт вершины обеих долей; зал подсказывает, что не так: C не покрывает, ребро из M касается C дважды или дефект не равен нулю.
Задания для ученика
- Решить, согласована ли пара (M, C), и понять, почему не подходят другие варианты.
- Вывести, что гарантирует нулевой дефект.
- Построить согласованную пару с f = 0.
Зал 11 · Операция 1
Краткое определение операции 1 (увеличивающий путь, вершины которого чередуются: в C, вне C, …; M растёт на одно ребро, C не меняется, f уменьшается на 1) и медленная анимация на примере 3 + 3: ищем вершину из C без пары, проходим путь с зелёным коридором за рёбрами, переворачиваем его по этапам, и f падает с 1 до 0. Затем три простых задания, в каждом есть «Посмотреть объяснение», а после верного ответа операция показывается по этапам с кнопкой «Посмотреть ещё раз»: граф 3 + 4 с f = 1 и единственным подходящим путём из 3 рёбер; граф 4 + 4 с f = 2, где две вершины из C без пары соединены ребром (соблазнительный путь a4–b2 увеличивает M, но не чередуется с C и отвергается), а подходящий путь состоит из 3 рёбер; и граф 4 + 5 с f = 2 и подходящим путём из 5 рёбер, а также более коротким соблазнительным путём, который заканчивается внутри C. Каждая ошибка объясняется, у каждого задания свои две подсказки.
Задания для ученика
- Отметить путь операции 1 в графе из 7 вершин.
- Отличить произвольный увеличивающий путь от того, который годится для операции 1.
- Найти путь из 5 рёбер, чередующийся с C.
Зал 12 · Операция 2
Сначала простейший случай — выключить лишнюю камеру (S из одной вершины), со своей анимацией и заданием, затем общий случай. Определение операции 2 в виде алгоритма (начать в вершине из C без пары, пройти по её рёбрам за пределы C, включить в S пары достигнутых вершин, повторять; затем S выходит из C, а её пары входят) и медленная анимация на небольшом примере. Три задания растущего размера, в каждом есть «Посмотреть объяснение», а после верного ответа операция показывается по этапам: граф 4 + 4 с S из 2 вершин, граф 5 + 4 с S из 3 вершин цепочкой и граф 7 + 6 с S из 4 вершин, распространяющимся на два уровня; во всех трёх M наибольшее (увеличивающего пути нет), f = 1 и подходящее S единственное. Ошибки объясняются (S не независимо, ребро осталось бы непокрытым, дефект не уменьшается). В конце — итог по двум операциям на одной паре (4 + 5, f = 2): операция 1 с путём из 3 рёбер (f падает до 1) и операция 2 с S из 2 вершин (f падает до 0) в пошаговой анимации, и текст: операция 1 меняет только M (оно растёт на одно ребро), операция 2 меняет только C (оно теряет столько вершин, сколько в S было вершин без пары), а обе сохраняют согласованность пары и уменьшают f.
Задания для ученика
- Построить S, идя по рёбрам за пределы C и затем по парам, на трёх всё более крупных графах.
- Увидеть, что меняет каждая операция (M или C) на одной и той же паре.
Зал 13 · Нулевой дефект
Теорема Кёнига, пережитая до формулировки, и единственный зал, где операции объединяются. Две большие кнопки выбирают операцию («Сделаю операцию 1 (отметить путь)» или «Сделаю операцию 2 (отметить S)»), активная подсвечена, одна строка говорит, что отмечать, а единственная кнопка применяет выбранную операцию; сообщения об ошибке одной операции не упоминают другую. Первое задание: случайный двудольный граф 5 + 5, где M пусто, C равно одной доле, а ν = 4 < 5, поэтому для f = 0 мало увеличить M: нужно сократить C операцией 2. Второе: граф 7 + 7 с 17 рёбрами, наполовину построенный (|M| = 5, |C| = 8, f = 3), который всегда решается ровно двумя операциями 1 и одной операцией 2, причём хотя бы один путь содержит 5 рёбер. Когда дефект доходит до 0, M и C одновременно мигают (можно повторить). Третье: недвудольный граф из 11 вершин (пятиугольник с двумя ветвями), где вначале доступны только операции 2; дефект опускается до f = 1, и ни одна операция больше не применима, а ученик должен это объявить («Ниже опустить нельзя»): сделать это раньше времени — ошибка. Завершающий вопрос: что этому мешает? Нечётный цикл (здесь ν = 5, а τ = 6); варианты с чётным циклом, вершиной степени 1 и вершиной с тремя соседями зал опровергает на самом графе. В конце — Кёниг: в двудольных графах ν = τ. Бесплатная подсказка (после двух ошибок или через 60 с без продвижения) сначала показывает вершину для старта, а при повторном нажатии рисует подходящую операцию и включает её кнопку; после пятой ошибки операцию применяет сам зал.
Задания для ученика
- Довести до нулевого дефекта случайный двудольный граф 5 + 5, где нужна операция 2.
- Сделать то же в графе 7 + 7, где нужны два увеличивающих пути и изменение C.
- Понять, когда дальше снижать нельзя, в графе с нечётным циклом и объяснить почему.
Зал 14 · Делегаты кружков
Свой делегат у каждого клуба: 7 клубов и 8 человек, ученик нажимает на линию, соединяющую клуб с одним из его участников. У первого задания есть решение (17 рёбер, 4 назначения), но если идти по клубам и брать «первого свободного участника», на седьмом клубе наступает тупик, а при случайном выборе получается лишь примерно в 18 % случаев; подсказка напоминает, что Cris и Eva состоят только в «Театре». Второе задание сформулировано так же и с теми же двумя кнопками, но решения не имеет (ν = 6): здесь правильный ответ «Это невозможно», а потом нужно доказать его, отметив единственную группу клубов, которая этому мешает, — пять клубов (Хор, Танцы, Дзюдо, Живопись и Скалолазание), у которых вместе всего четыре человека. В первом задании нажатие «Это невозможно» считается ошибкой; если отмеченная группа не подходит, зал говорит, скольким людям она располагает. В конце условие Холла как необходимое условие.
Задания для ученика
- Назначить своего делегата каждому из семи клубов.
- Решить, что во втором варианте это невозможно.
- Отметить группу из пяти клубов, у которых всего четыре человека.
Зал 15 · Детектив Холла
Четыре двудольных графа 7 + 7 с 20 рёбрами и без вершин степени 1 и вопрос: есть ли паросочетание, насыщающее A? Ответы по порядку: да, нет, нет, да. Ученик выбирает ветвь и доказывает её: либо самим паросочетанием (в обоих графах «да» по 4 совершенных паросочетания, а жадный выбор заходит в тупик), либо группой S из A с |N(S)| < |S|. В двух графах «нет» нарушающая группа единственна, и по степеням её не увидеть: во втором это 4 вершины всего с 3 соседями, а a7 степени 2 в S не входит; в третьем — 5 вершин с 4 соседями. Неверный выбор ветви считается ошибкой и объясняется, а у каждого графа своя вторая подсказка. В конце теорема Холла: условие не только необходимо, но и достаточно.
Задания для ученика
- В каждом из четырёх графов решить, есть ли паросочетание, насыщающее A.
- Дать свидетельство: паросочетание или группу S, которая этому мешает.
Зал 16 · Ладьи на закрашенных клетках
В задании 8 × 8 до ответа можно пробовать ставить ладей и смотреть на доску как на граф «строки — столбцы», синхронизированный с ладьями. Если в каждой строке и каждом столбце по r закрашенных клеток, то всегда помещаются n ладей, не бьющих друг друга. Три задания. Первое: доска 7 × 7 с 20 закрашенными клетками, нерегулярная, с 4 полными расстановками; если идти по строкам и брать самый левый свободный столбец, на седьмой строке наступает тупик. Второе: доска 8 × 8 с 24 закрашенными клетками, на которой 8 ладей не помещаются: при заблокированной доске нужно предсказать, сколько ладей помещается (6), а потом расставить их; в строках 1, 2, 4, 5, 7 и 8 клетки есть только в столбцах b, c, g и h (шесть строк на четыре столбца), и после трёх ошибок зал их отмечает. Третье: вопрос с вариантами ответа о том, почему при r клетках в каждой строке и каждом столбце всегда помещаются n ладей: в k строках rk клеток, и они затрагивают не меньше k столбцов (Холл). Среди неверных ответов — то, что общее число клеток кратно n (опровергается предыдущей доской 8 × 8), и правило «первый свободный столбец» (оно подводит на доске 4 × 4 с 2 клетками в строке).
Задания для ученика
- Расставить 7 ладей на доске, где жадный выбор заходит в тупик.
- Предсказать и расставить наибольшее число ладей (6) на доске 8 × 8, где помещаются не все.
- Объяснить с помощью условия Холла, почему они помещаются всегда, когда в каждой строке и каждом столбце по r клеток.
Зал 17 · Карточный фокус
Колода из 52 карт случайно раскладывается на 13 стопок по 4 карты: нужно выбрать по одной карте из каждой стопки так, чтобы вышли все 13 значений. Пока ученик выбирает, зал показывает лишь, сколько стопок уже сделано; какие значения вышли и какие повторились, отмечается после нажатия «Проверить». Колоду можно перетасовать снова сколько угодно раз, и решение есть всегда. После двух неудачных попыток появляется кнопка подсказки, фиксирующая одну карту, а после трёх зал показывает решение (оно не засчитывается как верный ответ). В конце вопрос с вариантами ответа о том, почему это возможно всегда: в k стопках 4k карт, и так как каждого значения по 4 карты, среди них не меньше k разных значений; это условие Холла для стопок и значений, потому что мультиграф «стопки–значения» 4-регулярен. Каждый неверный ответ опровергается (подсчёта карт мало, масти ни при чём, в стопке значение может повториться).
Задания для ученика
- Выбрать по одной карте из каждой стопки так, чтобы вышли все 13 значений.
- Объяснить с помощью условия Холла, почему это возможно всегда, как бы ни перетасовали колоду.
Зал 18 · Задача о назначениях на глаз
Четыре переводчика и четыре документа, таблица 4 × 4 с часами, которые каждый тратит на каждый документ. Сначала нужно подсчитать, сколько даёт жадная стратегия, при которой каждый переводчик по очереди берёт самый быстрый из ещё свободных документов: 17 ч. Затем ученик вручную выбирает по одной клетке в каждой строке и каждом столбце, чтобы сумма была наименьшей. Всего 24 назначения, а оптимум единственный — 12 ч (T1–D4, T2–D3, T3–D2, T4–D1), всего на 2 ч лучше второго по качеству; он не использует ни минимум строки T1, ни минимум строки T4, так что решать строка за строкой недостаточно. При ошибке зал сообщает только полученную сумму (и предупреждает, что ответ близок, если до оптимума не больше 2 ч); при верном ответе показывает, что это единственное назначение на 12 ч из 24.
Задания для ученика
- Подсчитать сумму, которую даёт жадная стратегия (17 ч).
- Найти назначение с наименьшей суммой, 12 ч, среди 24 возможных.
Зал 19 · Вычитание ничего не меняет
Работаем с той же таблицей 4 × 4. Сначала нужно подсчитать, как изменится сумма одного конкретного назначения, если из строки T2 вычесть 2, а к столбцу D4 прибавить 5 (+3, со знаком). Затем вопрос, меняет ли это изменение оптимальное назначение; из четырёх вариантов каждая ошибка опровергается: каждое назначение использует ровно одну клетку каждой строки и каждого столбца, поэтому все они меняются на одну и ту же величину. Последнее задание — шесть ползунков (от 0 до 9) на таблице 3 × 3: нужно вычесть из каждой строки и каждого столбца целое число, пока не исчезнут отрицательные числа и не появятся три независимых нуля. Таблица отмечает нули и отрицательные числа, а проверка идёт при отпускании ползунка. Решение единственное (строки 3, 0, 4 и столбцы 0, 3, 1), а тонкость в том, что вычесть из каждой линии её минимум недостаточно: останется не больше 2 независимых нулей. Подсказка появляется после 12 движений, решение — после 30.
Задания для ученика
- Подсчитать, как изменится сумма назначения, если вычесть из строки и прибавить к столбцу.
- Объяснить, почему оптимальное назначение не меняется.
- Получить ползунками три независимых нуля без отрицательных чисел.
Зал 20 · Венгерский метод по шагам
Матрица приводится по шагам: ученик пишет минимум каждой строки, и матрица меняется на экране; затем минимум каждого столбца; затем считает нули, закрывает их наименьшим числом линий, корректирует и составляет назначение, всегда видя текущую матрицу. Таблица часов 4 × 4, преобразуемая шаг за шагом венгерским методом, с двумя коррекциями; единственный оптимум — 20 ч. Сначала вычитаются минимумы строк (5, 2, 2, 3) и столбцов (0, 0, 2, 0) и подсчитываются оставшиеся нули: 6. Затем ученик находит наибольшее число независимых нулей (2) и закрывает все нули наименьшим числом линий, нажимая на заголовки (2: строка T3 и столбец D4; здесь появляется Кёниг, применённый к матрице нулей). Потом подсчитывает значение клетки после первой коррекции (клетка T3 и D4, на пересечении двух линий, наименьшее незакрытое значение равно 1), сколько линий нужно теперь (3) и значение другой клетки после второй коррекции (наименьшее незакрытое значение равно 4). Наконец отмечает четыре нуля, образующих полное назначение, и подсчитывает его стоимость в исходной таблице: 20 ч, с T1–D2, T2–D4, T3–D1 и T4–D3. У каждого вопроса две подсказки и решение.
Задания для ученика
- Привести строки и столбцы и сосчитать оставшиеся нули.
- Найти независимые нули и закрыть их наименьшим числом линий.
- Выполнить две коррекции и подсчитать значение клетки после каждой.
- Отметить назначение по нулям и подсчитать его стоимость в исходной таблице.
Зал 21 · Техники
С приведённой таблицей перед глазами и живой суммой отмеченных клеток. Пять техников и пять поломок, таблица 5 × 5 без подсказок: нужно выбрать назначение с наименьшей суммой — 22 ч (оптимум единственный; жадный выбор по строкам даёт 33 ч). Двух приведений самих по себе недостаточно: чтобы закрыть нули, всё ещё нужны 4 линии, так что без коррекции не обойтись; предупреждение о близком ответе появляется только в пределах 1 ч от оптимума. Затем задача на максимизацию прибыли: четыре торговых представителя и четыре зоны. Сначала нужно выбрать, как превратить её в задачу минимизации (вычесть каждую прибыль из наибольшей в таблице, 19; обратная величина 1/b или замена местами дают назначение лишь на 52 тыс. € вместо 54, а деление меняет только масштаб), а потом выбрать назначение с наибольшей прибылью — 54 тыс. € с C1–Z3, C2–Z4, C3–Z1 и C4–Z2. Брать максимум каждой строки не годится: C2 и C3 хотят Z4, а C1 и C4 хотят Z3.
Задания для ученика
- Найти назначение с наименьшей суммой в таблице 5 × 5 без подсказок.
- Выбрать, как превратить задачу максимизации в задачу минимизации.
- Найти назначение с наибольшей прибылью.
Зал 22 · Блокирующие пары
Пять студентов и пять компаний для практики с полными списками предпочтений, а также определения назначения, блокирующей пары и устойчивого назначения. Начинается с пошаговой анимации (с людьми и с графом) на примере 3 × 3: что является и что не является блокирующей парой. Затем четыре задания по возрастающей сложности (3 × 3, 4 × 4 и два 5 × 5): ученик указывает блокирующую пару (выбирая студента и компанию) или нажимает «Назначение устойчиво»; при нажатии на студента отмечаются компании, которые он предпочитает своей, а каждая неудачная попытка объясняет, кто что предпочитает. Анимацию можно пересмотреть в каждом задании.
Задания для ученика
- Решить, устойчиво ли каждое назначение, и, если нет, указать блокирующую пару.
- Отличать блокирующую пару от пары, где предпочитает только один из двух.
Зал 23 · Гейл и Шепли
Алгоритм отложенного согласия, который ученик выполняет проход за проходом, с теми же предпочтениями, что и в предыдущем зале. Сначала предлагают студенты (4 прохода, с двумя цепочками отказов: Ana вытесняет Carla в S, а Elena вытесняет David в P): в каждом проходе ученик говорит, кого оставляет каждая компания, получившая нескольких кандидатов, а зал вычисляет предложения следующего прохода; каждый неверный выбор считается ошибкой и объясняется. Затем предлагают компании (ещё 4 прохода, с 4 выборами из двух кандидатов). Получаются два из трёх устойчивых назначений, различающиеся у 4 компаний из 5. Затем исследовательское задание: исходя из этих двух, ученик ищет недостающее, составляя пары в графе (нажатием на студента и компанию) и проверяя кнопкой «Устойчиво ли?», которая отмечает блокирующие пары красным. Подсказки показывают, что компания каждого студента лежит между двумя его компаниями из Гейла–Шепли, и как перейти от одного устойчивого назначения к другому цепочкой спусков (ротацией); в конце объясняется, что так получаются все (Ирвинг и Лезер, 1986). Завершающий вопрос: когда предлагают студенты, что получает каждая компания? Свою худшую устойчивую пару; кто предлагает, тот выигрывает. В конце Нобелевская премия 2012 года и распределение врачей-ординаторов.
Задания для ученика
- Выполнить алгоритм, в котором заявки подают студенты: в каждом проходе алгоритма каждый студент подаёт заявку в самую интересную для него компанию из тех, что ему ещё не отказали, а вы решаете, какую заявку каждая компания пока оставляет за собой (остальным она отказывает).
- Повторить его, когда предлагают компании, и сравнить результаты.
- Найти третье устойчивое назначение с помощью ротации.
- Понять, какая сторона выигрывает.
Зал 24 · Полярный круг
Доминошки и ромбы, выбранные наугад. Часть A: ацтекский бриллиант AD(n) (ряды по 2, 4, …, 2n, 2n, …, 4, 2 клетки) и его замощения доминошками, которые являются совершенными паросочетаниями. Ученик вручную строит 8 замощений AD(2) (с подсказкой и кнопкой «Больше не нахожу»), по числам 2, 8 и 64 находит, сколько замощений у AD(4) (2^(n(n+1)/2), Элкис–Куперберг–Ларсен–Пропп, 1992), и предсказывает, что получится, если выбрать наугад одно замощение большого бриллианта. Затем показывается точный выбор алгоритмом domino shuffling (уничтожить, сдвинуть, создать) с запуском, паузой, регулировкой скорости, пошаговым режимом и размером до n = 150: появляются четыре одноцветные области, а между ними — вписанный круг (теорема об арктическом круге, Джокуш–Пропп–Шор, 1995). Часть B: шестиугольник со сторонами a, b, c на треугольной решётке и его замощения ромбами (совершенные паросочетания сот), которые при трёх оттенках выглядят как стопки кубиков в коробке a×b×c. Ученик переворачивает вершины (добавляя или убирая кубик), выясняет, что от пустой коробки до полной нужно abc переворотов (8 для 2×2×2), что ромбов каждого оттенка всегда a·b, b·c и a·c (15 тёмных в 3×4×5), и предсказывает форму неупорядоченной области большого шестиугольника. На последней доске полная коробка «тает» под случайными переворотами (динамика Глаубера), пока не появится круг (вписанный эллипс, если a, b, c различны; Кон–Ларсен–Пропп, 1998). В конце — общая идея: всё это совершенные паросочетания, выбранные наугад.
Задания для ученика
- Построить 8 замощений AD(2).
- Вывести, что у AD(4) 1024 замощения.
- Предсказать форму неупорядоченной области случайного замощения бриллианта.
- Посмотреть, как бриллиант растёт с domino shuffling вплоть до арктического круга.
- Переворачивать вершины шестиугольника из ромбов и найти наименьшее число переворотов от пустой коробки до полной (8).
- Сосчитать ромбы одного оттенка в шестиугольнике 3, 4, 5 (15 тёмных).
- Посмотреть, как коробка тает до вписанного эллипса.
Залы для показа
Самые наглядные для показа и обсуждения в классе.