المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

می خواهیم از نقطه‌ي $A$ در شکل مقابل به یکی از نقاطی برویم که با دایره‌ي بزرگ مشخص شده اند. با فرض اینکه فقط می‌توانیم به سمت راست یا بالا حرکت کنیم، چند مسیر مختلف وجود دارد؟

  1. $۲^۶$
  2. $\left(\frac{۱۲!}{۲\times ۶!\times ۶!}\right)$
  3. $۲^۵$
  4. $\left(\frac{۱۰!}{۲\times ۵!\times ۵!}\right)$
  5. $\left(\frac{۱۲!}{۶!\times ۶!}\right)$

پاسخ

گزینه‌ی ۱ درست است.

هر مسیر از نقطه‌ی $A$ به نقاط بزرگ را می‌توان با یک رشته‌ی دودویی به طول ۶ متناظر ساخت (صفر در رشته به معنی حرکت به سمت راست و یک به معنی حرکت به سمت بالا خواهد بود).

به این نکته توجه کنید که در هر نقطه از مسیر دقیقا دو انتخاب داریم و طول مسیر هم دقیقا ۶ می‌باشد. در نتیجه تعداد کل حالات برابر است با: $2^6$.


ابزار صفحه