سوال ۱۰
یک جایگشت از اعداد ۱، ۲، $\ldots$ و ۹ داریم. در هر مرحله می‌توان جایگشت را به دو تکه از عناصر متوالی تقسیم کرد و ترتیب عناصر هر تکه را وارون کرد. برای مثال، جایگشت $\langle 1,2,3,4,5,6,7,8,9\rangle$ می‌تواند به جایگشت $\langle2,1,9,8,7,6,5,4,3\rangle$ تبدیل شود. توجه کنید تکه‌ها می‌توانند تهی باشند. یک جایگشت را مطلوب گوییم، اگر بتوان با شروع از آن و انجام چند مرحله، به جایگشت مرتب شده (از کوچک به بزرگ) رسید. چند جایگشت مطلوب داریم؟
- ۷۲
- ۲۴۰
- ۱۲۰
- ۱۸
- ۹
راهنمایی
جایگشت $\langle 1,2,3,4,5,6,7,8,9\rangle$ را در نظر بگیرید. چند عملیات روی آن اجرا کنید. آیا الگویی در جایگشت‌هایی که به آن‌ها می‌رسید یافت می‌کنید؟
راهنمایی
در راستای راهنمایی پیشین، جایگشت‌هایی که پس از اعمال تعداد زوجی عمل به آن‌ها رسیده‌اید را جداگانه بررسی کنید.
راهنمایی
در راستای راهنمایی‌های پیشین، اعضای جایگشت را دور یک دایره قرار دهید. اعضای جایگشت پس از یک عمل را نیز دور دایره قرار دهید. چه تشابهی میان این دو دایره وجود دارد؟
راهنمایی
دقت کنید پس از زوج عمل، اعضای جایگشت به ترتیب اولیه دور دایره قرار می‌گیرند و پس از فرد عمل، به ترتیب عکس.
راهنمایی
آیا می‌توان هر عدد دلخواه را به ابتدای جایگشت برد؟
پاسخ
گزینه‌ی ۴ درست است.
اگر اعداد را دور دایره ببینیم، ترتیب‌شان تنها وارون می‌شود. پس ترتیب دوری عناصر باید مرتّب شده از کوچک به بزرگ یا بزرگ به کوچک باشد. انتخاب نقطه‌ی شروع جایگشت از روی دایره نیز ۹ حالت دارد. پس $2 \times 9=18$ حالت داریم. دقّت کنید تمام این جایگشت‌های ذکر شده قابل ساختن نیز هستند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
