Комбинаторные блок-дизайны и системы Штейнера: Искусство планирования
Как организовать круговой турнир по теннису, чтобы каждый игрок сыграл с каждым ровно один раз, причем матчи шли параллельно без накладок? Как засеять поля разными экспериментальными удобрениями так, чтобы любые два удобрения встретились на одном участке одинаковое число раз для чистоты статистики? Ответы на эти сугубо практические вопросы дает изящный и глубокий раздел дискретной математики — теория комбинаторных блок-дизайнов (или схем).
Математически блок-дизайн — это распределение элементов некоторого конечного множества по подмножествам (называемым блоками) таким образом, что выполняются жесткие условия симметрии и инцидентности. Самым изучаемым классом таких структур являются t-(v, k, λ)-схемы. Расшифровка этих параметров означает следующее: у нас есть множество из v элементов. Мы разбиваем его на блоки размера ровно k элементов. И мы требуем, чтобы любые t элементов вместе встречались ровно в λ блоках.
Если параметры t=2 и λ=1 (то есть любая пара элементов встречается вместе ровно в одном блоке), такая структура называется Системой Штейнера (в честь швейцарского математика Якоба Штейнера). Самый известный частный случай — тройки Штейнера, когда размер каждого блока равен 3 (k=3). Построение троек Штейнера сродни решению судоку на максимальной сложности, и математики доказали, что такие тройки существуют только если количество элементов v дает остаток 1 или 3 при делении на 6.
Еще одной удивительной структурой в этом разделе является Конечная проективная плоскость. Самая маленькая из них — плоскость Фано. В ней всего 7 точек и 7 прямых (включая одну нарисованную в виде окружности). На каждой прямой лежат ровно 3 точки, и через каждую точку проходят ровно 3 прямые. Любые две прямые обязательно пересекаются в одной точке (здесь нет параллельных линий), а через любые две точки проходит ровно одна прямая.
Кажется, что это просто математические игры разума, но комбинаторные дизайны имеют колоссальное значение для IT. Они являются математическим ядром для создания кодов, исправляющих ошибки (Error-correcting codes). Матрицы инцидентности, построенные на основе блок-дизайнов, обладают великолепными свойствами распределения нулей и единиц, что позволяет телекоммуникационному оборудованию восстанавливать поврежденные пакеты данных, переданные с космических зондов. Также структуры Штейнера активно применяются в криптографии для создания распределенных схем разделения секрета и протоколов безопасного многостороннего вычисления.
