المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۳۶

سوال ۳۶

در شکل مقابل با حرکت به سمت بالا و سمت راست بر روی پاره‌خط‌ها از $A$ به $B$ می‌رویم و در طول حرکت حرف‌های بر روی پاره‌خط‌ها را به ترتیب کنار هم می‌نویسیم. به این ترتیب٬ هر حرکت از $A$ به $B$ یک رشته تولید می‌کند.

تعداد رشته‌های متفاوتی که به این طریق تولید می‌شوند چندتا است؟

  1. ۶
  2. ۷
  3. ۸
  4. ۹
  5. ۱۰

پاسخ

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

تعداد کل مسیر‌های اشاره شده برابر $\binom{5}{2}$ یعنی ۱۰ که هر یک برای خود دنباله‌ای را تولید می‌کنند که دنباله‌های $abefc ،abcbc$ و $abeaa$ هر یک دو بار تولید می‌شوند. بنابراین تعداد کل دنباله‌های متمایز تولید شده برابر $10-3$ یعنی ۷ خواهد شد.


ابزار صفحه