Подмножества

[Teftel]

Имеется $100$ некоторых подмножеств множества ${0,1,2,...,9}$. Необходимо доказать, что найдётся два подмножества, у которых симметрическая разность имеет мощность не более двух.
Т.е. что найдутся два таких подмножества, которые будут отличаться не более чем двумя элементами.
Это ведь делается не перебором?
Изначально была идея, посчитать сколько всего пар подмножеств и у скольких пар симметрическая разность не более двух, но, кажется мне, есть способ лучше и адекватней.

[Foxer]

Это задача из вступительного экзамена в ШАД 2013 года. Хорошение решение предполагается следующим.
На множестве всех подмножеств $\{0,1, 2, \dots, 9\}$ введем метрику - мощность симметрической разности. Например, если у нас множества $\{1, 2, 3\}, \{2, 3, 9\}$, то симметрическая разность между ними будет $\{1, 9\}$, а расстояние, соответственно, 2.
Далее, у нас есть $100$ множеств (точки в метрическом пространстве). Возьмем вокруг каждой точки шар радиуса $1$ относительно введенной метрики. Заметим, что для любой точки найдется хотя бы $11$ точек, расстояние до которых не превышает $1$.
Остается лишь добавить, что $11 \times 100 = 1100 > 1024$, значит какие-то два из этих шаров пересекутся, и, соответственно, по неравенству треугольника, расстояние между их центрами будет не более чем $2$.

[mihailm]

(Оффтоп)

Foxer в сообщении #870001 писал(а):

...Хорошение решение предполагается следующим...

Новояз из опечатки) хорошее решение - хорошение

[ИСН]

post853207.html

[Teftel]

Спасибо большое за ответы!
Наконец-то всё стало понятно!