سوال ۱۹
یک دنباله‌ی $a_0,a_1,a_2,...,a_n$ متنوع نامیده می‌شود. اگر این شرایط برقرار باشند:
- برای هر $a_i , ( 0 \leq i \leq n)i$ و $a_{i+1}$ متفاوت باشند.
- اگر $n>1$ ، دنباله $a_0, a_2,...,a_{2[\frac{n}{2}]}$ نیز یک دنباله‌ي متنوع باشد.($[x]$ یعنی بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی با $x$)
برای مثال $A,B,C,A,D,C$ یک دنباله‌ي متنوع است.
اگر $a_i \in \{A,B,C\}$ ، آیا دنباله‌ي متنوع $a_0,a_1,...,a_{1374}$ وجود دارد به طوری که دنباله‌ی $a_0,a_3,a_6,...,a_{1374}$ نیز متنوع باشد؟
پاسخ
بدون این‌که به کلیت مسئله لطمه‌ای وارد شود $a_0$ را $A$و $a_1$ را $B$ در نظر می‌گیریم. $a_2$ نمی‌تواند $B$ باشد(شرط اول)٬ $A$ نیز نمی‌تواند باشد(زیرا در غیر این صورت $a_0$ و $a_2$ متفاوت نمی‌شوند)٬ پس $a_3.a_2=C$ نمی‌تواند $A$ باشد(چون $a_3 ،...$ و $a_0$ باید متنوع باشد)٬ $C$ نیز نمی‌تواند باشد(شرط اول)٬ پس $A_4.a_3=B$ نمی‌تواند $B$ باشد(شرط اول) $C$ نیز نمی‌تواند باشد(چون $a_2$ و $a_4$ طبق شرط دوم باید متنوع باشد) واما $A ، a_4$ نیز نمی‌تواند باشد زیرا دراین صورت دنباله‌ی $a_0,a_2,a_4,...$ به صورت $A,C,A,...$ در می‌آید که اگر آن را به صورت $b_0,b_1,b_2,...$ در نظر بگیریم چون $b_0=b_2$ می‌شود٬ پس متنوع نیست.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
