سوال ۱۷
یک رشته به طول ۱۰ از حروف $A$٬ $B$ و $C$ را در نظر بگیرید. به دو حرف متوالی یکسان در این رشته «توالی یکسان» می‌گوییم. رشته‌ای که دقیقاً سه «توالی یکسان» داشته باشد یک رشته «خوب» است. برای مثال $AAAABCABCB$ و $CABBCCABCC$ دو رشته‌ي «خوب» هستند. تعداد رشته‌های «خوب» به طول ۱۰ چندتاست؟
- $۲۱ \times ۳ \times ۲^۸$
- $۳۵ \times ۳ \times ۲^۶$
- $۳۵ \times ۳ \times ۲^۷$
- $۱۵ \times ۳ \times ۲^۸$
- $۲۱ \times ۳ \times ۲^۷$
پاسخ
گزینه‌ی (۱) درست است.
برای یافتن تعداد رشته‌های خوب از ابتدای رشته شروع می‌کنیم:
حرف اول ۳ حالت دارد و پس از آن در جایگاه‌هایی که توالی یکسان وجود دارد ۱ حالت برای پر کردن آن خانه داریم و در غیر این صورت ۲ حالت (متمایز با قبلی) داریم. از طرفی باید سه جایگاه را که در آن‌ها توالی یکسان خواهیم داشت را انتخاب کنیم. به‌جز جایگاه اول بقیه می‌توانند انتخاب شوند. پس جواب نهایی برابر است با: $\binom{9}{3}×2^6×3=21×3×2^8$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
