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