Задача за множества.

[Baronov]

Нека Х е множество с n елемента и нека сме взели фамилия от m негови същински подмножества със свойството, че всяка двойка от елементи на Х принадлежи на точно едно от подмножествата от фамилията. Да се докаже, че [tex]m \geq n[/tex].

[martin123456]

имаме n елемента, значи [tex]\frac{(n-1)n}{2}[/tex] двойки. всяка двойка е някое множество, чиито брой допускаме че е [tex]\leq n-1[/tex] и значи има множество с поне [tex]s=[\frac{n}{2}][/tex] елемента. нека това е [tex]X_1=\{x_1,x_2,\ldots,x_s\}[/tex].
за [tex]x_{s+1}[/tex] [tex]\exist X_{i+1}[/tex], че [tex]\{x_{s+1},x_{i}\} \subset X_i[/tex], [tex]i \in I_s[/tex], понеже не е възможно [tex]x_i \in X_1[/tex] за две различни [tex]i[/tex] да е в едно множество [tex]X_j[/tex] с [tex]x_{s+1}[/tex], иначе тези [tex]x_i[/tex] са в още едно множество, освен [tex]X_1[/tex]. това добавя още [tex]s[/tex] множества.
за [tex]x_{s+2}[/tex] имаме 2 възможности:
1) то е в [tex]X_2[/tex] заедно с [tex]x_1[/tex] и [tex]x_{s+1}[/tex]. тогава то не може да е в [tex]X_3, \ldots, X_{s+1}[/tex], понеже [tex]x_{s+1},x_{s+2}[/tex] ще участва в повече от едно множество. значи следват още следните множества [tex]X_{s+i}=\{x_{s+2}, x_i\, \ldots}[/tex], [tex]i=2,\ldots,s[/tex], т.е. още [tex]s-1[/tex]. общо множествата стават [tex]2s[/tex]
2) то не е в [tex]X_i[/tex], [tex]i \in I_{s+1}[/tex]. значи се добавят следните множества [tex]X_{s+i}=\{x_{s+2},x_i,\ldots\}[/tex], [tex]i \in I_s[/tex], т.е. още [tex]s[/tex] множества. общо множествата стават [tex]2s+1[/tex].
Но [tex]2s=2[\frac{n}{2}] \geq n[/tex]. Противоречие.
Равенство при: [tex]X_1=\{x_1,x_2,\ldots,x_{n-1}\}[/tex], [tex]X_i=\{x_n,x_i\}[/tex], [tex]i \in I_{n-1}[/tex].

[Baronov]

имаме n елемента, значи [tex]\frac{(n-1)n}{2}[/tex] двойки. всяка двойка е някое множество, чиито брой допускаме че е [tex]\leq n-1[/tex] и значи има множество с поне [tex]s=[\frac{n}{2}][/tex] елемента. нека това е [tex]X_1=\{x_1,x_2,\ldots,x_s\}[/tex].

Този момент не ми харесва. Надолу решението иначе е ясно. Едно подмножество с к елемента "покрива" [tex]\frac{k*(k-1)}{2}[/tex] двойки от елементи, а не к, както ми се струва, че ти си мислиш.

Както и да е, аз успях да я реша. Отне ми повече от час да осъзная, че задачата е еквивалентна на една доста известна задача. Решението ми не използва горната идея, така че ще се радвам да видя друго решение.

[martin123456]

имаме n елемента, значи [tex]\frac{(n-1)n}{2}[/tex] двойки. всяка двойка е [tex]{\bf B}[/tex] някое множество, чиито брой допускаме че е [tex]\leq n-1[/tex] и значи има множество с поне [tex]s=[\frac{n}{2}][/tex] елемента. нека това е [tex]X_1=\{x_1,x_2,\ldots,x_s\}[/tex].

- от дирихле

[Baronov]

Ясно, че от Дирихле, ама пак си мисля, че не е вярно. Нека имаме[tex]k\leq n-1[/tex] множества и най голямото е с s елемента. Тогава [tex](n-1)\frac{s(s-1)}{2}\geq\frac{ks(s-1)}{2} \geq \frac{n(n-1)}{2}[/tex] тоест [tex]s(s-1) \geq n[/tex], което е доста по-слабо от това, което ти получаваш и използваш.

[martin123456]

да, прав си
и все пак мисля че "решението" ми може да се продължи. ама става мн дълго и не мога да извадя адекватни предположения. мисля че на всяка стъпка се добавят поне s-i, i=0,1,2,.... провах за 0,1,2