المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۴

جای‌گشت ۱۲۳۴۵۶ را در نظر بگیرید. در یک حرکت می‌توانیم جای دو عدد $i$ و $j$ را باهم عوض کنیم اگر$|i-j|≥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$ باهم عوض خواهد شد.


ابزار صفحه