المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۱

دنباله‌ی $a_0 , a_1 ,..., a_n$ «متنوع» است٬ اگر $n=0$ باشد یا هر دو عنصر متوالی دنباله متفاوت باشند و دنباله‌ی $a_0 ,a_2,a_4,...,a_{2[\frac{n}{2}]}$ هم متنوع باشد.

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

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

پاسخ

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

با توجه به تعریف دنباله‌ی متنوع معلوم می‌شود که شرط لازم برای متنوع بودن دنباله‌ی $a_0,a_1,a_2,a_3,a_4,a_5,a_6$ آن است که دنباله‌ی $a_0,a_2,a_4,a_6$ و به دنبال آن دنباله‌ی $a_0,a_4$ متنوع باشند. چون هر دو عضو متوالی یک دنباله متمایز هستند پس عدد $a_0$ را به ۳ طریق و عدد $a_4$ را به دو طریق از بین اعداد ۱٬۰ و ۲ می‌توان انتخاب کرد یعنی ۶ نوع دنباله‌ی متنوع متمایز به صورت $a_0,a_4$ وجود دارد. در دنباله‌ی $a_0,a_2,a_4,a_6$ پس از معلوم شدن $a_0$ و $a_4$ عضو $a_2$ به یک طریق (چون در وسط قرار گرفته است) و عضو $a_6$ به دو طریق (متمایز با $a_4$ ) مشخص می‌شوند. چون ۶ نوع دنباله‌ی متمایز $a_0,a_4$ ایجاد شده بنابراین طبق اصل ضرب $6\times1\times2$ یعنی ۱۲ دنباله‌ی متنوع به صورت $a_0,a_2,a_4,a_6$ می‌توان ایجاد کرد. چون در دنباله‌ی اولیه هر یک از اعضای $a_2،a_1$ و $a_3$ بین دو عضو دیگر قرار گرفته‌اند پس هر یک از آن‌ها به صورت منحصر به فرد مشخص خواهند شد٬ بنابراین جواب مورد نظر ۱۲ می‌باشد.


ابزار صفحه