یک سؤال جالب ترکیبیات

amir.ekhlasi · 1390/10/17

فرض کنید

$n\geqslant k\geqslant3$

،

$X=\{1,...,n\}$

و

$F$

خانواده ای از زیرمجموعه های

$k$

عضوی

$X$

باشد که هر دو مجموعه از آن حداکثر

$k-2$

عضو مشترک دارند. ثابت کنید زیرمجموعه ای از

$X$

مانند

$Y$

با حداقل

$[\log_2n]+1$

عضو وجود دارد که هیچ کدام از مجموعه های

$F$

زیرمجموعه آن نیستند.

mahanmath · 1390/10/17

پاسخ : یک سؤال جالب

همه مجموعه‌های

$t= \left \lfloor \log_2 n \right \rfloor +1$

عضوی رو در بخش

$X$

و همهٔ اعضای خانواده

$F$

رو در بخش

$Y$

از گراف ۲ بخشی

$G= X \cup Y$

در نظر بگیرید . یه عضو خانواده رو به یه مجموعه

$t$

عضوی وصل می‌کنیم اگه زیر مجموعش باشه . هدف اینه که ثابت کنیم یک راس تنها در بخش

$Y$

هست . پس با توجه به اینکه درجه هر راس

$X$

$\binom{n-k}{t-k}$

است ، کافیه داشته باشیم :

$\left | F \right | . \binom{n-k}{t-k} < \binom{n}{t}$

از طرفی‌ با توجه به فرض مساله داریم :

$\left | F \right | \leq \frac{\binom{n}{k-1}}{k}$

پس بعد از جایگذاری و ساده کردن اون نابرابری بالا (خیلی‌ ساده می‌شه :4

کافیه ثابت کنیم :

$n-k+1 >\binom{t}{k}$

اینم که با یه استقرا ساده ثابت می‌شه .:157:

erfan_ashorion · 1390/10/19

پاسخ : یک سؤال جالب ترکیبیات

میدونم لینک دادن کار بدیه!!ولی خب چند تا سوال خیلی شبیه به این»AoPS Forum - A subset of X with at least root 2n elements • Art of Problem Solving

یک سؤال جالب ترکیبیات

amir.ekhlasi

New Member

mahanmath

New Member

erfan_ashorion

New Member