زیر مجموعه ها با اشتراک ناتهی

Aref · 1390/10/27

فرض کنید

$A_1,A_2,\dots,A_m\subset \{1,2,...,n\}$

که

$A_i\nsubseteq A_j$

و داشته باشیم:

$|A_i|\le \frac{n}{2}$

و نیز

$|A_i\cap A_j|\neq 0$

.
ثابت کنید

$\sum_{i=1}^{m}\frac{1}{\binom{n-1}{|A_i|-1}}\le 1$

لطفا راه حل رو همین جا بزارید.
ممنون

goodarz · 1390/10/27

پاسخ : زیر مجموعه ها با اشتراک ناتهی

راهنمایی: مشابه اثبات قضیه Erdos-Ko-Rado عمل کنین. به ازای هر

$A_i$

که روی یه دایره اومده باشه عدد

$\frac{1}{|A_i|}$

رو یادداشت کنین.

پ.ن: یادش بخیر دوره پارسال استاد منصوری اینارو کردن تو حلقمون.....:4: