2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача про симметрическую разность и 100 подмножеств
Сообщение22.04.2014, 23:50 


22/04/14
6
Имеется конечное множество $\{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, вроде.

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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 01:47 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 13:08 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 15:09 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
ИСН, а в таком виде решение известно? Пока задача выглядит скорее как олимпиадная.

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 15:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 18:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:03 


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:14 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:28 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:29 


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 20:44 


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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 21:03 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Для этой метрики выполняется обычное неравенство треугольника, так что расстояние будет не больше 2. Вы же пытаетесь построить контрпример, в котором все расстояния больше 2. Вот и подумайте, что можно сказать о точках, находящихся вблизи одного центра:
nikvic в сообщении #853397 писал(а):
Шар единичного радиуса состоит из 11 точек

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 21:20 


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

-- 23.04.2014, 22:30 --

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

 Профиль  
                  
 
 Re: Задача про симметрическую разность и 100 подмножеств
Сообщение23.04.2014, 21:37 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
glaz в сообщении #853537 писал(а):
то на каждую точку имеем 11 "не годных"
Я бы сформулировала это по-другому: Рассмотрим множество из 100 точек (строк) и все шары радиуса один с центрами в них. Могут ли они перескаться, если все расстояния больше 2? Сколько будет в них всего точек?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group