2014 dxdy logo

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

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




 
 Помогите разобраться (найти максимум подмножеств)
Сообщение02.10.2013, 12:31 
Задача.
Пусть $M= {M_1, . . . ,M_s}$ — произвольная совокупность, состоящая из трехэлементных подмножеств $n$-элементного множества, причём $|M_i  \bigcap M_j | \ne 1$ для любых i, j. Найдите максимум $s$, при котором это возможно.

Решение.
Всего трехэлементных подмножеств $n$-элементного множества равно $C_n^3$. Насколько я понимаю, теперь необходимо вычеркнуть минимальное количество подмножеств, так, чтобы из оставшихся подмножеств каждые два либо не пересекались, либо имели 2 общих элемента.

Не совсем понятно, как вычеркнуть эти подмножества. Может подскажете, что почитать можно?

 
 
 
 Re: Помогите разобраться
Сообщение02.10.2013, 16:35 
Аватара пользователя
 i  Название исправил на более содержательное.

Здесь можно решить руками: $|M_i \bigcap M_j | \ne 1$ и $|M_i|=3$ означает, что либо $M_i, M_j$ не пересекаются, либо $|M_i \bigcap M_j |=2$. Значит произвольная совокупность $M$ распадается на классы множеств, элементы которых не пересекаются, либо имеют общее для всех пересечение мощности 2. Получаем общее описание $M$, из него находим оптимальное.

 
 
 
 Re: Помогите разобраться
Сообщение02.10.2013, 16:45 
Аватара пользователя
Не совсем так. Три множества могут пересекаться по-другому. Например, $\{1,2,3\},\{2,3,4\},\{1,2,4\}$

 
 
 
 Re: Помогите разобраться
Сообщение02.10.2013, 16:48 
Есть еще вариант $\{123\}$; $\{234\}$; $\{124\}$; $\{134\}$

-- Ср окт 02, 2013 17:52:34 --

Сопоставляя всё вышесказанное, при $n=4m$ мы получим, что $s=n$, при других тоже сложностей не должно возникнуть.

 
 
 
 Re: Помогите разобраться (найти максимум подмножеств)
Сообщение03.10.2013, 00:40 
А откуда взялось, что при $n=4m$ $s=n$?

 
 
 
 Re: Помогите разобраться (найти максимум подмножеств)
Сообщение03.10.2013, 01:06 
Аватара пользователя
Gaary_P в сообщении #770152 писал(а):
А откуда взялось, что при $n=4m$ $s=n$?

В этом случае множесто можно разбить на четверки элементов. А для каждой четверки прстроить 4 множества, как указал Cash. Значит, множеств будет столько же, сколько элементов. В остальных случаях множеств будет меньше, чем элементов.

 
 
 
 Re: Помогите разобраться (найти максимум подмножеств)
Сообщение03.10.2013, 18:27 
Так а как тогда доказать, что не может быть случая, когда множеств $M_i$ не может быть больше чем $n$?

 
 
 
 Re: Помогите разобраться (найти максимум подмножеств)
Сообщение03.10.2013, 18:34 
Аватара пользователя
Рассмотрите другие классы множеств. Кроме "четверных" все остальные будут иметь тот вид, про который сказал Deggial, то есть все подмножества класса будут иметь 2оющих элемента. Сколько будет в таком классе элементов и подмножеств?

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group