المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوالات ۲۹ و ۳۰ و ۳۱

سوالات ۲۹ و ۳۰ و ۳۱

یک جایگشت از اعداد ۱ تا $n$ یک لیست از اعداد ۱ تا $n$ است که هر عدد $\underline{ دقیقا}$ یک بار در آن ظاهر شده است. برای مثال <۱٬۵٬۳٬۴٬۲> یک جایگشت از اعداد ۱ تا ۵ است.

رنگ آمیزی معتبر برای یک جایگشت٬ رنگ‌آمیزی است که شرایط زیر را داشته باشد:

  • دو عدد مجاور هم در جایگشت هم رنگ نباشند.
  • دو عدد که اختلاف آنها برابر با ۱ است هم رنگ نباشد.

عدد رنگی یک جایگشت برابر است با حداقل تعداد رنگ های متفاوتی که برای رنگ آمیزی معتبر اعداد آن جایگشت لازم است.

با توجه به توضیحات بالا به ۳ سوال زیر پاسخ دهید:

سوال ۲۹

عدد رنگی جایگشت <۱٫۵٫۲٫۴٫۶٫۳> چند است؟

  1. ۴
  2. ۱
  3. ۲
  4. ۵
  5. ۳

پاسخ

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

سه عدد ۱، ۲ و ۵ باید رنگ‌آمیزی متفاوتی داشته باشند (۱ با ۵ و ۵ با ۲ مجاور است و اختلاف ۱ و ۲ یک واحد است). با سه رنگ نیز به ترتیب زیر می‌توان به هدف رسید.

سوال ۳۰

در میان تمام جایگشت های اعداد ۱ تا ۶ عدد رنگی چند جایگشت برابر با ۲ است؟

  1. ۶۲۵
  2. ۳۶
  3. ۰
  4. ۱۲۵
  5. ۷۲

پاسخ

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

در صورتی عدد رنگی جایگشت ۲ خواهد بود که اعداد زوج به یک رنگ و اعداد فرد به رنگ دیگر باشند. در این صورت باید در جایگاه‌های زوج و در جایگاه‌های فرد رنگ‌های متمایزی باشند. در نتیجه اعداد زوج در یکی از این جایگاه‌ها و اعداد فرد در جایگاه دیگر باشند. پس تعداد این حالات برابر خواهد بود با:

$$2×(3!)^2=72$$

سوال ۳۱

بیشترین عدد رنگی بین همه جایگشت های اعداد ۱ تا ۷ چند است؟

  1. ۲
  2. ۳
  3. ۶
  4. ۴
  5. ۵

پاسخ

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

اگر به ترتیب از ابتدای جایگشت رنگ‌آمیزی کنیم، هر عدد یک همسایه قبل از خود دارد و دو عدد که با آن حداکثر یک واحد اختلاف دارند. پس اگر ۴ رنگ داشته باشیم، همواره می‌توان اعداد را رنگ کرد.

برای مثال زیر نیز حداقل ۴ رنگ مورد نیاز است:

$$<2,4,1,3,5,6,7>$$


ابزار صفحه