المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

تعریف: مجموعه‌ی ‎$A_n=\{1,2,\ldots n\}$‎ داده شده است. هر زیر مجموعه‌ی سه عضوی از آن را به یکی از دو رنگ آبی یا قرمز رنگ می‌کنیم. ‌به ‎$B \subset A_n$‎ خوب می‌گوییم اگر تمام زیر مجموعه‌های سه عضوی آن هم‌رنگ باشند‎. ‎

  1. ثابت کنید برای هر دو عدد طبیعی همانند ‎$a,b$‎ ، ‎$n$‎ای وجود دارد که در ‎$A_n$‎ یا زیرمجموعه‌ی ‎$a$‎تایی خوبه به رنگ آبی و یا ‎$b$‎تایی خوب به رنگ قرمز وجود دارد. (کوچکترین ‎$n$‎ با این خاصیت را ‎$R_3(a,b)$‎ می‌نامیم‎.)
  2. ثابت کنید:

‎$$R_3(a,b) \geq (a-1) \times (R_3(a‎, ‎\lfloor \frac{b}{2} \rfloor‎ ) -‎1)‎ ~ + ~ ‎1$$


ابزار صفحه