Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

به یک جایگشت از اعداد 1,2,,2n1 دلواپس گوییم؛ هرگاه تمام اعداد سمت چپ 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,,2n1 دلواپس است؟


ابزار صفحه