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

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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


ابزار صفحه