المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

با خواندن کلمات ‎۹‎ حرفی از حروفِ ‎$a$‎ و ‎$b$‎ از چپ به راست، با دیدن هر ‎$a$‎ دو گلوله در کاسه‌ای می‌اندازیم و با دیدن هر ‎$b$‎ ، یک گلوله از کاسه برمی‌داریم. در شروع کار کاسه خالی است. به‌ازای چند کلمه از کلمات ‎۹‎ حرفی پس از خواندن حرف نهم، کاسه خالی خواهد بود؟ (اگر در هنگام خواندن کلمه‌ای به حرف ‎$b$‎ برسیم و گلوله‌ای در کاسه نباشد تا آن را برداریم، آن کلمه در این شمارش محسوب نخواهد شد).

  1. ۳
  2. ۹
  3. ۱۱
  4. ۱۲
  5. ۱۵

پاسخ

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

تعداد ‎$a$‎ها بربر ۳ و تعداد $b$ها برابر ۶ بوده و شروع هر یک از دنباله‌ها با $a$ و پایان آن دنباله‌ها با دو عدد $b$ می‌باشد که به شکل زیر می‌باشند:

$aaabbbbbb \quad\quad\quad\quad\quad aabbbbabb \quad\quad\quad\quad\quad ababbbabb \\ aababbbbb \quad\quad\quad\quad\quad abaabbbbb \quad\quad\quad\quad\quad abbaabbbb \\ aabbabbbb \quad\quad\quad\quad\quad abababbbb \quad\quad\quad\quad\quad abbababbb \\ aabbabbb \quad\quad\quad\quad\quad ababbabbb \quad\quad\quad\quad\quad abbabbabb$


ابزار صفحه