المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:تئوری:سوال ۶

مجموعه‌ی تکراری

مجموعه‌ی اعداد یک تا $n$ را در نظر بگیرید. $b(m,n)$ را تعریف می‌کنیم، کم‌ترین تعداد زیرمجموعه‌های $m$ عضوی این مجموعه، به طوری که اگر هر جایگشت $p$ روی اعداد ۱ تا $n$ بدهیم و به جای هر $i$ در همه‌ی زیرمجموعه‌ها $p(i)$ را جایگزین کنیم، باز یکی از زیرمجموعه‌های اولیه تکرار شود. به عنوان مثال اگر $m=1$ و $n=3$ باشد، زیرمجموعه‌های $\{1\},\{2\}$ این خاصیت را دارند (مثلا جایگشت $(3,1,2)$‌ را در نظر بگیرید، این جایگشت زیرمجموعه‌ها را به $\{3\},\{1\}$ تبدیل می‌کند و زیرمجموعه‌ی $\{1\}$ تکرار می‌شود). ثابت کنید:

$$b(m,n) \leq \binom{n}{\lceil \frac{m}{2}\rceil}$$


ابزار صفحه