المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:ترکیبیات:سوال ۲

سوال ۲

می‌گوییم مجموعه ‎$A$‎ توسّط رنگ‌آمیزی ‎$c$‎، مختلف رنگ شده‌است اگر ‎$|c(A)| = |A|$‎؛ به‌عبارت دیگر برای هر ‎$x \neq y \in A$‎ داشته باشیم ‎$c(x) \neq c(y)$‎.

فرض کنید ‎$\cal F$‎ یک خانواده‌ی ‎$r$‎-منتظم از مجموعه‌هایی از نقاط باشد. ثابت کنید یک رنگ‌آمیزی برای نقاط وجود دارد که حداقل ‎$(\frac{(r-1)!}{r^{r-1}})|{\cal F}|$‎ از مجموعه‌های موجود در ‎$\cal F$‎ را به‌طور مختلف رنگ می‌کند.


ابزار صفحه