المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

جایگشت $a_1, a_2, \cdots, a_6$ از اعداد ۱ تا ۶ را در نظر بگیرید. در ابتدا یک عدد را به دل‌خواه انتخاب می‌کنیم و سپس در هر مرحله اگر عدد $a_i$ انتخاب شده بود در مرحله‌ی بعد به ازای $a_i \neq 6$ عدد $a_{a_i+1}$ و برای $a_i=6$ عدد $a_1$ انتخاب می‌شود. به ازای چند جایگشت مختلف می‌توان عدد اول را به گونه‌ای انتخاب کرد که بعد از تعدادی مرحله، همه‌ی اعداد جایگشت حداقل یک‌بار انتخاب شده باشند؟

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

پاسخ

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

برای هر جایگشت می‌توان یک نوع دیگر گراف جایگشت ساخت به طوری که از هر عدد به عدد بعدی یک یال جهت‌دار رسم کرد حالا ما می‌خواهیم گراف جایگشت یک دور به طول ۶ باشد که برای این کار $5!$ حالت وجود دارد.


ابزار صفحه