Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۱

دنباله‌ی a0,a1,...,an «متنوع» است٬ اگر n=0 باشد یا هر دو عنصر متوالی دنباله متفاوت باشند و دنباله‌ی a0,a2,a4,...,a2[n2] هم متنوع باشد.

چند دنباله‌ی متنوع برای n=6 از اعداد ۱٬۰ و ۲ وجود دارد؟ (x یعنی بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی x)

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

پاسخ

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

با توجه به تعریف دنباله‌ی متنوع معلوم می‌شود که شرط لازم برای متنوع بودن دنباله‌ی a0,a1,a2,a3,a4,a5,a6 آن است که دنباله‌ی a0,a2,a4,a6 و به دنبال آن دنباله‌ی a0,a4 متنوع باشند. چون هر دو عضو متوالی یک دنباله متمایز هستند پس عدد a0 را به ۳ طریق و عدد a4 را به دو طریق از بین اعداد ۱٬۰ و ۲ می‌توان انتخاب کرد یعنی ۶ نوع دنباله‌ی متنوع متمایز به صورت a0,a4 وجود دارد. در دنباله‌ی a0,a2,a4,a6 پس از معلوم شدن a0 و a4 عضو a2 به یک طریق (چون در وسط قرار گرفته است) و عضو a6 به دو طریق (متمایز با a4 ) مشخص می‌شوند. چون ۶ نوع دنباله‌ی متمایز a0,a4 ایجاد شده بنابراین طبق اصل ضرب 6×1×2 یعنی ۱۲ دنباله‌ی متنوع به صورت a0,a2,a4,a6 می‌توان ایجاد کرد. چون در دنباله‌ی اولیه هر یک از اعضای a2،a1 و a3 بین دو عضو دیگر قرار گرفته‌اند پس هر یک از آن‌ها به صورت منحصر به فرد مشخص خواهند شد٬ بنابراین جواب مورد نظر ۱۲ می‌باشد.


ابزار صفحه