Задача про симметрическую разность и 100 подмножеств

[glaz]

Имеется конечное множество $\{0,1,...9\}$, выбирается некоторая сотня его подмножеств. Требуется показать что среди этой сотни обязательно найдется пара таких подмножеств, мощность симметрической разности которых не превосходит 2.
Моя идея решения состоит в том чтобы показать, что если мы для этой сотни будем выбирать только подмножества, которые попарно имеют мощность разности больше 2, то их окажется меньше 100. Для того чтобы упростить решение, я нахожу "оценку сверху" таким образом: рассмотрим подмножества мощности $i$, будем по отдельности находить максимальное количество множеств мощности $i$, которые мы можем отобрать для нашей сотни, т.е: отдельно число попарно непересекающихся, пересекающихся по одному элементу, итд до i-2. Тот факт, что мощность симметрической разности между этими типами может быть меньше 3 игнорируем, так как у нас оценка сверху.
Например $i=3$, тогда попарно непересекающихся можно взять макс $[10/3]=3$, а пересекающихся по одному элементу $[9/2]=4$.
Затем просто сложим все полученные значения для всех мощностей, опять проигнорировав то, что вообще говоря мы не учли "взаимодействия" между множествами разной мощности.
Формула в итоге вот такая получилась $\sum^{10}_{i=0}${\sum^{i-2}_{k=0}{[\frac{10-k}{i-k}]}}$
Если посчитать получится около 70, вроде.

Честно говоря, данное решение совсем не внушает мне доверия, я так же пробовал считать пары множеств но там совсем ничего не вышло
Вообщем хочется узнать имеет ли вообще подобное решение право на жизнь, ну и как решать правильно если нет

[provincialka]

Рассуждение для подсчета числа пересекающихся подмножеств не приведено и оно, видимо, неверно. Например, вы утверждаете, что трехэлементных множеств, попарно пересекающихся по одному элементу, может быть не более 4. Вы, видимо, имеете в виду, подмножества типа $012,034,056,078$. Но ведь к ним можно добавить, например, $135, 246$, уж не говоря о $689$.
.

[ИСН]

Задача была бы приятнее для глаза в своих родных терминах. Что-то в духе "не существует 10-битного кода на 100 слов с минимальным расстоянием 3".

[provincialka]

ИСН, а в таком виде решение известно? Пока задача выглядит скорее как олимпиадная.

[nikvic]

Шар единичного радиуса состоит из 11 точек, каковых всего 1024.

[provincialka]

Ага, понятно. Только ТС куда-то пропал.
получается, что в этой задаче число 2 существенно, для 1 или 3 такое решение не подходит (?)

[glaz]

provincialka
Рассуждал просто: зафиксируем один элемент по которому будет пересекаться и возьмем из n-1 элемента по i-1, ну теперь конечно очевидно, что это совсем не верно.
А вот намеков ИСН и nikvic не совсем понял, можно поподробнее?

[nikvic]

Я среагировал на переформулировку ИСН. Она и есть почти решение.

[provincialka]

glaz, наши собеседники представляют каждое подмножество как точку в десятимерном бинарном пространстве. Для этого можно представить каждое подмножество строкой нулей и единиц, $\{1, 5, 9\}\to 0100010001$. Ноль означает, что соответствующего элемента нет в подмножестве, а единица - что есть. Между этими строками можно ввести расстояние Хэмминга: число различий компонент. Как в терминах этого расстояния будет формулироваться задача?

[glaz]

nikvic
Так, относительно переформулировки я понял,каждому подмножеству мы можем поставить в соответствие 10-битный код (элемент либо входит либо нет) и надо найти количество кодов с мин расстоянием 3. Дальше пока не успел подумать

[provincialka]

Ага, мы пишем одновременно. Небольшая подсказка. Если от кода $a$ до кодов $b, c$ расстояние 1, то каким может быть расстояние от $b$ до $c$?

[glaz]

provincialka
наверное двум, если $b(i)\ne a(i)$ и $c(k)\ne a(k)$, то $b(k)\ne c(k)$ и $b(i)\ne c(i)$ при различных i и k

[provincialka]

Для этой метрики выполняется обычное неравенство треугольника, так что расстояние будет не больше 2. Вы же пытаетесь построить контрпример, в котором все расстояния больше 2. Вот и подумайте, что можно сказать о точках, находящихся вблизи одного центра:

nikvic в сообщении #853397 писал(а):

Шар единичного радиуса состоит из 11 точек

[glaz]

provincialka
понятно,что если шар едничного радиуса состоит из 11 точек, то на каждую точку имеем 11 "не годных" и сотню мы так не наберем, но как появилось число 11 пока не понятно(

-- 23.04.2014, 22:30 --

provincialka
А ну да, есть код из 10 бит, для расстояния один нужно поменять один бит, итого 10 кодов +исходный
Спасибо, получается задача решена)

[provincialka]

glaz в сообщении #853537 писал(а):

то на каждую точку имеем 11 "не годных"

Я бы сформулировала это по-другому: Рассмотрим множество из 100 точек (строк) и все шары радиуса один с центрами в них. Могут ли они перескаться, если все расстояния больше 2? Сколько будет в них всего точек?