سوال ۱۹
یک دنباله‌ی a0,a1,a2,...,an متنوع نامیده می‌شود. اگر این شرایط برقرار باشند:
- برای هر ai,(0≤i≤n)i و ai+1 متفاوت باشند.
- اگر n>1 ، دنباله a0,a2,...,a2[n2] نیز یک دنباله‌ي متنوع باشد.([x] یعنی بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی با x)
برای مثال A,B,C,A,D,C یک دنباله‌ي متنوع است.
اگر ai∈{A,B,C} ، آیا دنباله‌ي متنوع a0,a1,...,a1374 وجود دارد به طوری که دنباله‌ی a0,a3,a6,...,a1374 نیز متنوع باشد؟
پاسخ
بدون این‌که به کلیت مسئله لطمه‌ای وارد شود a0 را Aو a1 را B در نظر می‌گیریم. a2 نمی‌تواند B باشد(شرط اول)٬ A نیز نمی‌تواند باشد(زیرا در غیر این صورت a0 و a2 متفاوت نمی‌شوند)٬ پس a3.a2=C نمی‌تواند A باشد(چون a3،... و a0 باید متنوع باشد)٬ C نیز نمی‌تواند باشد(شرط اول)٬ پس A4.a3=B نمی‌تواند B باشد(شرط اول) C نیز نمی‌تواند باشد(چون a2 و a4 طبق شرط دوم باید متنوع باشد) واما A،a4 نیز نمی‌تواند باشد زیرا دراین صورت دنباله‌ی a0,a2,a4,... به صورت A,C,A,... در می‌آید که اگر آن را به صورت b0,b1,b2,... در نظر بگیریم چون b0=b2 می‌شود٬ پس متنوع نیست.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
