Processing math: 17%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۴

جای‌گشت ۱۲۳۴۵۶ را در نظر بگیرید. در یک حرکت می‌توانیم جای دو عدد i و j را باهم عوض کنیم اگر|ij|2. پس از انجام چند حرکت به‌ جای‌گشت π=p_1p_2p_3p_4p_5p_6 میرسیم. \pi کدام‌یک از گزینه‌های زیر می‌تواند باشد؟

  1. ۶۵۴۳۲۱
  2. ۲۱۳۴۵۶
  3. ۴۳۱۲۶۵
  4. ۳۲۴۶۱۵
  5. تمام گزینه‌‌های فوق می‌تواند باشد.

پاسخ

گزینه (۵) درست است.

کافی است ثابت کنیم جای هر دو عدد مانند x و y را می‌توانیم عوض کنیم٬ بدون آن که جای بقیه اعداد عوض شود:

  • اگر |x-y|\geq2 آن‌گاه جای آن دو عدد را باهم عوض می‌کنیم.
  • اگر|x-y|<2 آن‌گاه عددی مانند وجود دارد به طوری که |x-z|\geq2 و |y-z|\geq2.

در این صورت جای x را با z سپس جای z را با y عوض می‌کنیم که در این صورت فقط جای دو عدد x و y باهم عوض خواهد شد.


ابزار صفحه