Высшая проба 2026, 11 класс, задача 1
(13 баллов) Фокусник и его ассистент готовятся показать следующий фокус. У них есть колода из различных карт. Они сообщают зрителю натуральное число . Зритель выбирает произвольных карт из колоды, убирает их в конверт и заклеивает его. Затем ассистент выбирает карт из оставшихся и передает их зрителю. Тот перетасовывает эти карты как хочет и отдает фокуснику. Задача фокусника - отгадать карты, которые лежат в конверте. Для каких фокусник и ассистент могут договориться действовать так, чтобы фокус гарантированно удался?
Ответ. Для всех .
Решение . Покажем, что фокусник и ассистент могут придумать стратегию, согласно которой для всех фокус будет успешным. Обозначим . Пусть фокусник и ассистент договорятся о расположении карт по кругу. Получив остаток колоды, ассистент однозначно восстанавливает, какие карты забрал зритель. В случае четного и фокус очевидно всегда будет успешен, поэтому далее считаем, что . Предложим алгоритм для ассистента и фокусника для произвольного .
После того, как зритель выберет некоторые карты, ассистент сопоставит каждой из карт некоторую другую карту в соответствии с алгоритмом, предложенным ниже.
Покрасим все карты, выбранные зрителем, в красный цвет. Теперь выберем каждую красную карту, для которой следующая по часовой стрелке красной не являются. Каждой такой карте сопоставим следующую за ней, покрасим сопоставленную карту в синий цвет и удалим все такие пары из круга. Будем повторять данные действия до тех пор, пока в круге не закончатся красные карты, после чего отдадим фокуснику все синие карты.
Для восстановления карт зрителя фокусник ищет синие карты, следующие за которыми против часовой стрелки синими не являются, красит их в красный цвет и удаляет из круга, после чего называет все красные карты выбранными зрителем.
Покажем, что алгоритм работает. Для этого достаточно показать, что на каждом шаге алгоритм фокусника и алгоритм ассистента составляют один и тот же набор пар красных и синих карт. Заметим, что если ассистент на некотором шаге сопоставил некоторой красной карте синюю, то следующая за этой красной картой по часовой стрелке не является красной. Но тогда и следующая против часовой стрелки карта за синей не будет синей, а значит, на том же этапе алгоритма фокусник сопоставит этой синей карте красную. Аналогично, если фокусник некоторой синей карте сопоставит красную, то ассистент сопоставит этой красной карте синюю, а значит, они составят один и тот же набор пар карт, что и требовалось.
Решение . Зафиксируем и рассмотрим двудольный граф, вершинами одной доли которого являются всевозможные комбинации из зрительских карт, а второй долей являются всевозможные комбинации из ассистентских карт (эти доли идентичны и по существу являются всевозможными наборами из различных карт колоды), а ребра проведены между вершинами разных долей, если соответствующие наборы карт не пересекаются. По вершине, соответствующей набору зрительских, ассистент должен выдать набор карт, соответствующей смежной вершине.
Степени всех вершин в этом графе равны
так как каждой вершине одной доли сопоставляются всевозможные наборы из карт из остатка колоды размером . Это двудольный граф с равными по размерам долями, в котором степени всех вершин равны, поэтому согласно следствию из леммы Холла в этом графе существует паросочетание, покрывающее все вершины обеих долей (совершенное паросочетание). Для каждого фокусник и ассистент договариваются о выборе конкретного паросочетания, поэтому по картам ассистента всегда можно будет восстановить карты зрителя
Любое верное решение.
А1. В решении через лемму Холла не проверяются явно ее условия, но указано, что степени всех вершин равны.
А2. Решение состоит из ссылки на лемму Холла без указания регулярности графа и проверки ее условия, или же с неверной проверкой условия.
А3. Задача переформулирована в терминах доказательства существования паросочетания в двудольном графе, дальнейших продвижений нет.
Б1. В решении через расстановку карт по кругу сформулирован алгоритм за ассистента. Возможно сформулирован алгоритм за фокусника. Обоснование, почему фокусник восстановит именно карты зрителя, отсутствует или неверно.
Б2. В круговом решении алгоритм за ассистента сформулирован неоднозначно.
Б3. Алгоритм за ассистента не сформулирован явно и не обоснована его корректность, но из контекста сам алгоритм можно восстановить.
Б4. Присутствует только идея поставить числа по кругу и, возможно, сдвигать блоки подряд идущих, если этому ничего не мешает; обоснования отсутствуют или неверны.
Решение не соответствует ни одному из критериев выше.
Баллы за разные критерии не суммируются.