Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

مجموعه‌ی اعداد یک تا 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)(nm2)


ابزار صفحه