Высшая проба 2026, 11 класс, задача 6

Ответ. .

Решение. Пример. Покажем, как открыть карточек так, чтобы гарантированно восстановить значения каждого из чисел.

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

Докажем, что можно для каждой клетки однозначно определить, какое число в ней записано.

Если в строке или в столбце неизвестно значение только одного числа, то оно восстанавливается однозначно как единственное отсутствующее в соответствующей строке или соответствующем столбце.

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

Предположим, что однозначно восстановить числа все же нельзя. Тогда невозможно восстановить значение ни одной из закрытых клеток, находящихся не в последней строке. Заметим, что каждая такая клетка находится на пересечении строки, в которой не хватает всего двух чисел, а также столбца, в котором не хватает всего двух чисел. Если пары недостающих чисел для какой-то клетки различны, то число в данной клетке определяется однозначно как единственное число, присутствующее в обеих парах. Значит, для каждой закрытой клетки (не из последней строки) в строке, ее содержащей, и в столбце, ее содержащем, не хватает одной и той же пары чисел. Более того, в силу расположения закрытых клеток, это означает, что во всех столбцах, кроме самого правого, и во всех строках, кроме самой нижней, не хватает одной и той же пары чисел. Назовем эти числа и . Заметим, что число в каждой из первых строк окажется в закрытой клетке. Значит, в самом правом столбце число может находиться только в самой нижней клетке. Но по той же причине и число может находиться только в самой нижней клетке правого столбца. Приходим к противоречию.

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

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

Построим полный двудольный граф с вершинами в каждой доле. Сопоставим каждой строке вершину из левой доли, каждому столбцу — вершину из правой доли, а каждой клетке — ребро, которое соединяет вершины, соответствующие строке и столбцу, на пересечении которых она находится. Тогда каждому ребру можно сопоставить число, записанное в соответствующей клетке. Если числа в каждой строке таблицы не повторяются и числа в каждом столбце таблицы не повторяются, то в графе это равнозначно тому, что всем ребрам, входящим в любую вершину, сопоставлены различные числа.

Предположим, что хотя бы

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

Рассмотрим подграф построенного графа, состоящий только из ребер, соответствующих закрытым карточкам. В нем вершины и ребер, а значит, в нем точно найдется цикл. Если длина этого цикла строго меньше , то мы нашли искомый цикл.

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

подряд идущих вершин, каждая из которых имеет степень . Иными словами, все эти вершины смежны только с ребрами цикла. Удалим из подграфа какие-нибудь таких вершины и все смежные с ними ребра (их, как показано выше, будет ). В графе останется вершин и ребер, откуда в нем снова найдется цикл, на этот раз, длины не более (так как вершин всего ), что и требовалось.

Назовем найденный цикл закрытым. В силу того, что наш граф двудольный, любой цикл в нем имеет четную длину. Каждому второму ребру закрытого цикла сопоставим число , а остальным ребрам сопоставим число . Так как закрытый цикл имеет длину меньше, чем , то рассмотрим произвольный цикл, проходящий через все вершины, не входящие в закрытый цикл (это можно сделать, так как закрытый цикл имеет четную длину, меньшую, чем , а значит, в нем не более вершин, и оставшихся вершин будет четное число и хотя бы ), и тоже сопоставим каждому второму его ребру число , а остальным — число . Этот цикл назовем дополнительным. Теперь у нас из каждой вершины выходит ровно одно ребро с числом и ровно одно ребро с числом .

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

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

Лемма . Если в двудольном графе с равными долями у всех вершин степени равны , то в нем найдется совершенное паросочетание.

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

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

Доказывать будем по индукции.

База тривиальна. Если в двудольном графе с равными долями каждая вершина имеет степень , то если каждому ребру сопоставить число , получим требуемое.

Шаг: пусть утверждение верно для . Докажем его для . Для этого заметим, что по лемме в данном графе найдется совершенное паросочетание. Сопоставим всем ребрам этого паросочетания число и рассмотрим подграф, содержащий все ребра, кроме данного паросочетания. По предположению индукции, ребрам этого подграфа можно сопоставить числа от до так, чтобы числа на ребрах, выходящих из каждой вершины, не повторялись. Тогда, совмещая ребра паросочетания и расстановку чисел на ребрах подграфа, полученную по предположению индукции, получим требуемую раскраску всего графа.

Применим лемму к нашему графу, чтобы показать, что искомая раскраска существует. Тем самым мы доказали требуемое.

Способ (набросок). Доказать данный факт можно и без использования теоремы Холла.

Построим явно подходящую расстановку. Для этого перейдем обратно от графа к таблице и рассмотрим несколько случаев. Также введем координаты в формате (строка, столбец), причем строку пронумеруем начиная с сверху вниз, а столбцы — начиная с слева направо. Для целого и натурального обозначим за остаток от деления на : целое число от до такое, что делится на .

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

Переставим строки и столбцы так, чтобы в первой и четвертой частях таблицы на главных диагоналях (соединяющих левые верхние углы этих частей и правые нижние углы этих частей) стояло число , а в клетках на диагоналях непосредственно под главными и в правых верхних углах стояло число . Больший из двух циклов окажется при этом в первой части, а меньший — в четвертой.

Разберем несколько случаев.

Случай . Длина закрытого цикла равна , .

Рассмотрим клетку с координатами . Если она лежит в первой или четвертой частях, то поставим в нее число , а в противном случае поставим в нее число . Первая и четвертая части будут представлять из себя латинские квадраты с числами от до , а вторая и третья — латинские квадраты с числами от до . Из этого следует, что все числа в каждой строке и в каждом столбце окажутся разными.

Случай . и нечетное.

Начнем заполнять квадрат с четвертой части. В клетку с координатами запишем число . Тогда часть будет латинским квадратом с числами от до .

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

Рассмотрим вторую часть таблицы. В строке под номером числа от до занимают клетки с координатами

где принимает значения от до . Значения в этих клетках равны

Используем это при заполнении второй части. Впишем в клетку с координатами число

Легко видеть, что во всех строках с номерами не больше теперь стоят все числа. Осталось лишь показать, что в столбцах с по числа не повторяются. Все числа от до уже стоят в части. Для этого заметим, что для любого фиксированного и числа , пробегающего все значения от до , числа также принимают все значения от до в силу того, что нечетное, и следовательно, взаимно простое с .

Аналогичным образом заполним третью часть: в клетку с координатами запишем число . Уникальность чисел в каждой строке и в каждом столбце доказывается аналогично второй части.

Случай . четное.

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

Для того чтобы решить эту проблему, разрежем вторую часть горизонтальным отрезком пополам. Нижнюю половину разрежем на горизонтальные доминошки и внутри каждой доминошки поменяем числа местами. Аналогично, разрежем третью часть на две равные части вертикальным разрезом, правую часть разрежем на доминошки и внутри каждой доминошки поменяем числа местами. Заметим, что в первых строках и столбцах поменялся только порядок чисел, а значит, числа в них по-прежнему не повторяются, а в остальных строках появились недостающие числа и исчезли лишние. Значит, теперь все числа расставлены правильно.

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

Вернемся к доказательству основного утверждения.

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

Это означает, что однозначно восстановить расположение чисел под закрытыми карточками невозможно, что и требовалось