سوال ۱۲
ده توپ با شماره‌های $1$ تا $10$ به ترتیب دور یک دایره قرار دارند. در هر مرحله می‌توان دو توپ مجاور مانند $A$ و $B$ در نظر گرفت و آن‌ها را به همان ترتیب در میان دو توپ مجاور دیگر قرار داد. برای مثال با برداشتن توپ‌های $1$ و $3$ و گذاشتن آن‌ها در میان دو توپ $5$ و $7$ می‌توان از شکل سمت چپ به شکل سمت راست رسید:
از میان $9!$ جایگشت دوری که این توپ‌ها دارند، به چند جایگشت می‌توان رسید؟ (تعداد گام‌ها اهمیتی ندارد.)
- $9!$
- $\frac{9!}{2}$
- $\frac{9!}{6}$
- $8!$
- $9!-8!$
پاسخ
گزینه (۱) درست است.
ادعا می‌کنیم به هر جایگشتی می‌توان رسید. کافی است ثابت کنیم دو عنصر مجاور را با تعدادی گام می‌توان جابه‌جا کرد؛ طوری که ترتیب بقیه به هم نریزد. فرض کنید $a, b, c$ سه عنصر متوالی باشند. با انجام گام‌های زیر می‌توان $a$ را دو واحد جلو برد: $$a, b, c \rightarrow c, a, b \rightarrow b, c, a$$ حال فرض کنید $a, b$ دو عنصر مجاور باشند. $b$ را ۴ بار دو واحد به جلو ببرید. به پشت $a$ می‌رسد و عملن $a, b$ جابه‌جا شده و حکم اثبات می‌شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
