المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۹

تعداد رشته‌هایی از صفر و یک به طول ۷ که شامل ۱۰۱۰۱ باشند چندتاست؟

  1. ۸
  2. ۱۰
  3. ۱۱
  4. ۱۲
  5. هیچ‌کدام

پاسخ

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

رشته‌های مورد نظر به سه صورت $10101x_1y_1$ یا $x_2y_210101$ و یا $x_310101y_3$ می‌باشندد. چون برای هر کدام از $x_i$ و $y_i$ دو حالت ۰ و ۱ را می‌توانیم اختصاص دهیم پس برای هر کدام از حالات فوق $2\times2=4$ رشته می‌توانیم بسازیم که در مجموع ۱۲ رشته می‌شود ولی در یک مورد رشته‌های ساخته شده در دو حالت اول باهم یکی می‌شوند و آن موقعی است که حالت زیر اتفاق بیفتد:

$$x_1y_1=01 \quad and \quad x_2y_2=10$$

که با کسر این حالت تعداد رشته‌های مورد نظر ۱۱ رشته خواهد بود.


ابزار صفحه