المپدیا

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

ابزار کاربر

ابزار سایت


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

دلواپسان کجایند؟

به یک جایگشت از اعداد $1, 2, \ldots, 2n-1$ دلواپس گوییم؛ هرگاه تمام اعداد سمت چپ $n$ از آن کوچک‌تر یا تمام اعداد سمت چپ $n$ از آن بزرگ‌تر باشند. برای مثال جایگشت‌های $<1, 3, 4, 6, 5, 7, 2>$، $<5, 4, 1, 2, 7, 6, 3>$ و $<4, 3, 7, 6, 1, 2, 5>$ دلواپس هستند؛ اما جایگشت $<1, 6, 4, 3, 7, 5, 2>$ دلواپس نیست! به چه احتمالی یک جایگشت از اعداد $1, 2, \ldots, 2n-1$ دلواپس است؟


ابزار صفحه