Мы разберём несколько красивых комбинаторных задач, которые решаются элементарно — стоит перевести их условие на матричный язык. А как решать без матриц — непонятно. Вообще, теория матриц имеет огромную сферу применения в том числе в комбинаторике, теории графов.
Задача 1 (ШАД). В ШАД поступили всего студентов. Кураторы решили ограничить число доступных курсов и придумали набор простых правил:
На каждый курс должно быть записано нечётное число студентов;
Для любой пары курсов число студентов, записанных одновременно на оба, чётно.
Какое максимальное число курсов можно прочитать по новым правилам?
Переведём условие на язык множеств. Пусть – множество студентов, – подмножества студентов, записанных на курсы . Нужно найти максимальное число подмножеств в , мощности которых нечётны, а мощности попарных пересечений чётны.
Начнём с комбинаторных соображений. Несложно построить пример с одноэлементными подмножествами. При чётном подходит и система из подмножеств из элементов. Можно построить и другие системы из подмножеств. Но можно ли построить больше подмножеств? Приведём набросок комбинаторного рассуждения. Будем выбирать подмножества последовательно. Подмножество может быть любым подмножеством из нечётного числа элементов. Всего таких
Пусть подмножество выбрано и состоит из элементов. Тогда будем строить по частям: и (чертой мы обозначаем дополнение до всего множества ). В качестве можно взять любое подмножество в чётной мощности – всего таких
Аналогично, множеством может быть любое подмножество в нечётной мощности – всего таких . Итого, множество можно выбрать
Попробуем действовать дальше аналогично. Множество тоже будем строить "по кускам", выбирая подмножества в , , , .
Первое может быть любым из подмножеств, а для каждого из остальных уже есть ограничение на чётность мощности (в зависимости от чётности мощности выбранного подмножества в ). Казалось бы, надо вычитать 1 три раза и в итоге получим
Вроде бы ясно, что для -го подмножества будет вариант. Однако аккуратно дожать эту идею не так просто. Ошибка возникает уже на третьем шаге. Дело в том, что если подмножества и взаимно дополняют друг друга, то есть , то подмножество выбрать нельзя вовсе: оно должно пересекаться по чётному числу элементов как с , так и с , а тогда его мощность чётна. Ошибка в рассуждении выше в том, что количество подмножеств из чётного числа элементов в -элементном равна , кроме случая .
На помощь приходят матрицы. Напрашивается рассматривать матрицы над полем классов вычетов по модулю 2 ( в ).
Рассмотрим матрицу
Условие ,,Все множества имеют нечётную мощность, а их попарные пересечения имеют чётную мощность'' равносильно условию , откуда следует, что , так как .
Итак, в случае студентов ответ: .
Задача 2 (фольклор). Квадратная таблица размера , где – чётное число, заполнена буквами и так, что любые две строки отличаются ровно в половине позиций. Докажите, что столбцы таблицы обладают тем же свойством.
Начнём с примеров. При условию удовлетворяют в точности таблицы, в которых ровно одна буква , либо ровно одна буква . Например,
Очевидно, для них утверждение задачи выполнено. При перебор уже гораздо более трудоёмкий. Вот общее соображение, помогающее его сократить. Если какая-то таблица удовлетворяет условию, то к ней можно применять перестановки и инверсии строк и столбцов (инверсия строки – замена в этой строке всех букв на и наоборот).
Можно показать, что с точностью до таких преобразований есть ровно одна подходящая таблица:
Очевидно, она симметричная (относительно главной диагонали), так что её столбцы тоже удовлетворяют условию.
При больших перебор уже становится невозможным. Более того, описать все , при которых такая матрица существует, – открытая проблема!
Матрицы, о которых идёт речь, только с числами вместо букв и , называются матрицами Адамара. Не очень сложно показать, что порядок такой матрицы кратен 4, Гипотеза Адамара состоит в том, что для любого , кратного 4, матрица Адамара существует.
Для она подтверждена, кроме 12 значений , для которых ответ неизвестен.
Существуют рекуррентные способы построения матриц Адамара для всех .
Матрицы Адамара широко применяются в математике и технике, в частности, в теории кодирования, ЕСС-памяти, в рентгеновских телескопах.
Вернёмся к задаче и решим её в одну строчку. Условие задачи на строки матрицы из равносильно попросту ортогональности строк относительно стандартного скалярного произведения в :
С учётом того, что все строки имеют скалярный квадрат , получаем матричное равенство . Но хорошо известно, что для квадратных матриц
Применяя это к матрицам и , заключаем, что , откуда столбцы матрицы ортогональны, что и требовалось доказать. Итак, всё решение основано на известном факте .
Модифицируя эту идею попробуйте решить следующую задачу.
Задача 3 (олимпиада кафедры алгебры мехмата МГУ, 2010). В таблице расставлены элементы поля . Известно, что разность любых двух столбцов есть столбец, содержащий поровну элементов 0, 1 и 2. Докажите, что разность любых двух строк является строкой, содержащей поровну элементов 0, 1 и 2.
Автор статьи: Андрей Канунников, к. ф.-м. н., преподаватель ШАД Хелпер.
Статья подготовлена при поддержке ШАД Хелпер.