Всесиб 2023, 10 класс, задача 5

Ответ. Восемь.

Решение. Приведём два различных примера выбора восьми -х элементных подмножеств во множестве из восьми элементов, удовлетворяющих условию задачи. Оба примера строятся, как геометрические объекты.

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

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

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