المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۶:سوال ۴

جای‌گشت نقره‌ای

یک جای‌گشت٬ ترتیبی از اعداد ۱ تا $n$ است که هر عدد دقیقاً یک بار در آن ظاهر شده است. مثلاً «۴ ۱ ۵ ۲ ۳» یک جای‌گشت از اعداد ۱ تا ۵ را نشان می‌دهد. فرض کنید عدد $\pi_n$ آخرین عدد جای‌گشت $\pi$ باشد. هر عمل وارون تعداد $\pi_n$ عنصر آخر $\pi$ را در دنباله معکوس می‌کند (به ترتیب عکس قرار می‌دهد) تا جای‌گشت $rev(\pi)$ به دست آید. مثلاً اگر عمل وارون را روی جای‌گشت بالا اعمال کنیم «۲ ۵ ۱ ۴ ۳» به دست می‌آید. گوییم $\pi$ یک جای‌گشت نقره‌ای است اگر $\pi$ =$rev(\pi)$ باشد. ثابت کنید با انجام متناهی بار عمل وارون روی هر جای‌گشت $\pi$ سرانجام یک جای‌گشت نقره‌ای به دست می‌آید.


ابزار صفحه