سوال ۸
جایگشتی از اعداد ۱ تا ۱۰ را درنظر بگیرید که میتوانیم عملیات زیر را به تعدادی دلخواه روی آن انجام دهیم:
در هر مرحله عددی دلخواه از جایگشت که تا به حال آن را انتخاب نکردهایم را از جایگشت حذف و سپس به انتهای آن اضافه میکنیم؛ برای مثال جایگشت زیر پس از انتخاب عدد ۹ (در صورتی که تا به حال انتخاب نشده باشد) بدین شکل تغییر مییابد: $$\langle 4, 1, 6, \underline{9}, 2, 3, 5, 10, 7, 8\rangle \rightarrow \langle 4, 1, 6, 2, 3, 5, 10, 7, 8, \underline{9}\rangle$$ تعداد جایگشتهای اولیهای که میتوان با انجام دقیقاً پنج مرحله آنها را تبدیل به یک جایگشت صعودی یا نزولی کرد چهقدر است؟
- ۶۰۲۲۸
- ۳۰۲۴۰
- ۳۰۴۹۲
- ۶۰۴۸۰
- ۱۵۱۲۰
پاسخ
گزینهی ۱ درست است.
فرض کنید هر عدد را که به انتهای جایگشت میبریم به رنگ آبی در بیاوریم. در این صورت همیشه تنها یک بازه در آخر جایگشت به رنگ آبی است و باقی اعداد بیرنگ هستند. همچنین از آنجایی که ۵ حرکت انجام دادهایم، حداکثر ۵ عدد آخر به رنگ آبی هستند که به این معنی است که ۵ عدد اول جایگشت نهایی بیرنگ هستند و ترتیبشان نسبت به هم عوض نشده است.
این ۵ عدد باید به ترتیب اعداد ۱ تا ۵ و یا ۱۰ تا ۶ باشند. پس در جایگشت ابتدایی یا باید اعداد ۱ تا ۵ به ترتیب صعودی و یا اعداد ۱۰ تا ۶ به ترتیب نزولی آمده باشند. همچنین با شروع از هر جایگشت به این صورت میتوان به حالتی مطلوب رسید. در نتیجه تعداد جایگشتهای مطلوب برابر است با: $$2\times\frac{10!}{5!} - \binom{10}{5} = 60228$$
| < سوال قبل | سوال بعد > |