المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوال ۱۵

سوال ۱۵

جدولی $3 \times 3$ داریم که ۹ شیء مختلف در خانه‌های آن قرار گرفته‌اند. در هر مرحله می‌توان یکی از دو کار زیر را انجام داد:

  • یک خانه‌ی گوشه را در نظر بگیریم و شیء آن را با شیء یکی از دو خانه‌ی مجاورش جابه‌جا کنیم.
  • سطر وسط یا ستون وسط را در نظر بگیریم و ترتیب اشیاء در آن را وارون کنیم.

یک جدول را سلطانی گوییم، اگر بتوان آن را با دقیقن ۱۳۹۵ مرحله ساخت. چند جدول سلطانی مختلف داریم؟

  1. $9!$
  2. $\frac{8!}{2}$
  3. $4!4!2!2!$
  4. $\frac{8!}{3}$
  5. $8!$

راهنمایی

ابتدا دقت کنید که شیء قرارگرفته در سطر دوم و ستون دوم را نمی‌توان جابجا کرد.

راهنمایی

سعی کنید نشان دهید اگر تعداد اعمال در مسئله مهم نبود (یعنی با هر تعداد متناهی‌ای عمل اگر به شکل حاصله دست می‌یافتید، در پاسخ شمرده می‌شد) می‌توانستید به هر چینش دلخواهی (مجزا از عنصر واقع در سطر دوم و ستون دوم) برسید.

راهنمایی

به زوجیت تعداد گام‌های انجام شده در اعمال خود دقت کنید.

راهنمایی

دقت کنید تمام اعمال داده شده را می‌توان به تعداد جابجایی دو عنصر از جدول تبدیل کرد.

راهنمایی

بجای دید جدولی، خانه‌های جدول را در یک ردیف قرار دهید و جابجایی‌های داده شده‌ی مسئله را روی آن‌ها بررسی کنید.

راهنمایی

با جابجایی دو عنصر از یک جایگشت، تعداد نابجایی‌ها چه مقدار تغییر می‌کند؟

پاسخ

گزینه‌ی ۲ درست است.

در یک جایگشت از اعداد، هر گاه عدد $A$ قبل از عدد $B$ آمده باشد، امّا $A>B$ باشد، گوییم یک وارونگی رخ داده است.

بدون از دست دادن کلیت مسئله فرض کنید اشیاء برابر اعداد ۱، ۲، $\ldots$ و ۹ بوده و در ابتدا به ترتیب زیر در جدول قرار گرفته باشند:

عدد ۵ هم‌واره سر جای خود باقی می‌ماند. هم‌چنین اگر با گذاشتن سطرهای جدول به دنبال هم، عناصر جدول را به شکل یک جایگشت ببینیم (که در ابتدا برابر جایگشت مرتّب شده است)، زوجیّت تعداد وارونگی‌ها تغییر می‌کند (بررسی گام‌ها و تغییرات تعداد وارونگی‌ها به خواننده واگذار می‌شود). از آن‌جایی که تعداد وارونگی‌ها در ابتدا زوج و تعداد مراحل فرد است، در انتها باید تعداد وارونگی‌ها فرد باشد. پس به حداکثر $\frac{8!}{2}$ جدول مختلف می‌توانیم برسیم.

حال ثابت می‌کنیم به هر جدولی که تعداد وارونگی‌های‌ش فرد باشد، می‌توان رسید. هر دو عنصر در جدول (به جز ۵) را می‌توان با حداکثر پنج گام جابه‌جا کرد، طوری که ترتیب بقیه‌ی عناصر با هم نریزد. پس می‌توان با حداکثر هشت جابه‌جایی عنصر (یعنی حداکثر $8 \times 5$ مرحله) از جایگشت ابتدایی به هر جایگشت دل‌خواه رسید. با توجه به فرد بودن تعداد وارونگی‌های جایگشت مقصد، تعداد مراحل طی شده تا رسیدن به آن جایگشت با الگوریتم گفته شده، فرد است. پس از رسیدن به جایگشت دل‌خواه، دو عنصر قابل جابه‌جایی با گام نوع ۱ در نظر گرفته و مرتّبن آن‌ها را جابه‌جا می‌کنیم تا ۱۳۹۵ مرحله انجام شود. تعداد مراحل انجام این قسمت زوج است، پس عملن پس از پایان کار، مراحل این قسمت تغییری در جایگشت ایجاد نمی‌کند. پس در انتها به جایگشت مورد نظر می‌رسیم.

پس پاسخ برابر $\frac{8!}{2}$ است.


ابزار صفحه