Матрицы помогают в олимпиадных задачах29.02.2024 15:30

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

Задача 1 (ШАД). В ШАД поступили всего студентов. Кураторы решили ограничить число доступных курсов и придумали набор простых правил:

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

Какое максимальное число курсов можно прочитать по новым правилам?

Переведём условие на язык множеств. Пусть $A=\{1,\ldots,n\}$ (n=10) — множество студентов, $A_1,\ldots,A_m\subseteq A$ — подмножества студентов, записанных на курсы $1,\ldots,m$ . Нужно найти максимальное число подмножеств в , мощности которых нечётны, а мощности попарных пересечений чётны.

Начнём с комбинаторных соображений. Несложно построить пример с одноэлементными подмножествами. При чётном подходит и система из подмножеств из n-1 элементов. Можно построить и другие системы из подмножеств. Но можно ли построить больше подмножеств? Приведём набросок комбинаторного рассуждения. Будем выбирать подмножества последовательно. Подмножество A_1 может быть любым подмножеством из нечётного числа элементов. Всего таких

$C_n^1+C_n^3+C_n^5+\ldots=2^{n-1}.$

Пусть подмножество A_1 выбрано и состоит из n_1 элементов. Тогда A_2 будем строить по частям: $A_2\cap A_1$ и $A_2\cap \overline{A_1}$ (чертой мы обозначаем дополнение до всего множества ). В качестве $A_2\cap A_1$ можно взять любое подмножество в A_1 чётной мощности — всего таких

$C_{n_1}^0+C_{n_1}^2+C_{n_1}^4+\ldots=2^{n_1-1}.$

Аналогично, множеством $A_2\cap \overline{A_1}$ может быть любое подмножество в $\overline{A_1}$ нечётной мощности — всего таких $2^{n-n_1-1}$ . Итого, множество A_2 можно выбрать

$2^{n_1-1}\cdot 2^{n-n_1-1} =2^{n-2} \;\;\text{способами.}$

Попробуем действовать дальше аналогично. Множество A_3 тоже будем строить «по кускам», выбирая подмножества в $A_1\cap A_2$ , $A_1\cap \overline{A_2}$ , $\overline{A_1}\cap A_2$ , $\overline{A_1}\cap \overline{A_2}$ .

Первое может быть любым из $2^{|A_1\cap A_2|}$ подмножеств, а для каждого из остальных уже есть ограничение на чётность мощности (в зависимости от чётности мощности выбранного подмножества в $A_1\cap A_2$ ). Казалось бы, надо вычитать 1 три раза и в итоге получим

$2^{|A_1\cap A_2|} \cdot 2^{|A_1\cap \overline{A_2}|-1}\cdot 2^{|\overline{A_1}\cap A_2|-1}\cdot 2^{|\overline{A_1}\cap \overline{A_2}|-1}=2^{n-3}.$

Вроде бы ясно, что для -го подмножества будет $2^{n-n}=1$ вариант. Однако аккуратно дожать эту идею не так просто. Ошибка возникает уже на третьем шаге. Дело в том, что если подмножества A_1 и A_2 взаимно дополняют друг друга, то есть $A_2=\overline{A_1}$ , то подмножество A_3 выбрать нельзя вовсе: оно должно пересекаться по чётному числу элементов как с A_1 , так и с A_2 , а тогда его мощность чётна. Ошибка в рассуждении выше в том, что количество подмножеств из чётного числа элементов в -элементном равна $2^{k-1}$ , кроме случая k=0 .

На помощь приходят матрицы. Напрашивается рассматривать матрицы над полем $\mathbb Z_2=\{0,1\}$ классов вычетов по модулю 2 ( 1+1=0 в $\mathbb Z_2$ ).
Рассмотрим матрицу

$B=(b_{ij})\in \mathbb M_{m\times n}(\mathbb Z_2),;b_{ij}=1\iff j\in A_i.$

Условие, Все множества A_i имеют нечётную мощность, а их попарные пересечения имеют чётную мощность'' равносильно условию $B B^\top=E\in \mathbb M_m(\mathbb Z_2)$ , откуда следует, что $m\leq n$ , так как $m=rk\; E=rk \;(BB^\top)\leq rk\; B\leq \min(m,n)$ .

Итак, в случае студентов ответ: .

Задача 2 (фольклор). Квадратная таблица размера $n\times n$ , где — чётное число, заполнена буквами и так, что любые две строки отличаются ровно в половине позиций. Докажите, что столбцы таблицы обладают тем же свойством.

Начнём с примеров. При n=2 условию удовлетворяют в точности таблицы, в которых ровно одна буква , либо ровно одна буква . Например,

$\begin{pmatrix} a & b \\ b & b \end{pmatrix}.$

Очевидно, для них утверждение задачи выполнено. При n=4 перебор уже гораздо более трудоёмкий. Вот общее соображение, помогающее его сократить. Если какая-то таблица удовлетворяет условию, то к ней можно применять перестановки и инверсии строк и столбцов (инверсия строки — замена в этой строке всех букв на и наоборот).
Можно показать, что с точностью до таких преобразований есть ровно одна подходящая таблица:

$\begin{pmatrix} a & a & a & a \\ a & a & b & b \\ a & b & a & b \\ a & b & b & a \end{pmatrix}.$

Очевидно, она симметричная (относительно главной диагонали), так что её столбцы тоже удовлетворяют условию.

При больших перебор уже становится невозможным. Более того, описать все , при которых такая матрица существует, — открытая проблема!

Матрицы, о которых идёт речь, только с числами $\pm 1$ вместо букв и , называются матрицами Адамара. Не очень сложно показать, что порядок такой матрицы кратен 4, Гипотеза Адамара состоит в том, что для любого , кратного 4, матрица Адамара существует.
Для $n\leq 2000$ она подтверждена, кроме 12 значений , для которых ответ неизвестен.
Существуют рекуррентные способы построения матриц Адамара для всех n=2^k .

Матрицы Адамара широко применяются в математике и технике, в частности, в теории кодирования, ЕСС-памяти, в рентгеновских телескопах.

Вернёмся к задаче и решим её в одну строчку. Условие задачи на строки матрицы из $\pm 1$ равносильно попросту ортогональности строк относительно стандартного скалярного произведения в $\mathbb R^n$ :

$(X,Y)=X^\top Y=x_1y_1+\ldots x_ny_n,\;\;X=(x_1,\ldots,x_n)^\top\in \mathbb R^n,\, Y=(y_1,\ldots,y_n)^\top\in \mathbb R^n \text{ – столбцы}.$

С учётом того, что все строки имеют скалярный квадрат , получаем матричное равенство $AA^\top =nE$ . Но хорошо известно, что для квадратных матриц

$AB=E \implies BA=E. \;\;\;\;\; (1)$

Применяя это к матрицам $\dfrac{1}{\sqrt{n}}A$ и $\dfrac{1}{\sqrt{n}}A^\top$ , заключаем, что $A^\top A=nE$ , откуда столбцы матрицы ортогональны, что и требовалось доказать. Итак, всё решение основано на известном факте (1) .

Модифицируя эту идею попробуйте решить следующую задачу.

Задача 3 (олимпиада кафедры алгебры мехмата МГУ, 2010). В таблице $2010\times 2010$ расставлены элементы поля $\mathbb Z_3$ . Известно, что разность любых двух столбцов есть столбец, содержащий поровну элементов 0, 1 и 2. Докажите, что разность любых двух строк является строкой, содержащей поровну элементов 0, 1 и 2.

Автор статьи: Андрей Канунников, к. ф.-м. н., преподаватель ШАД Хелпер.
Статья подготовлена при поддержке ШАД Хелпер