سوال ۳
می خواهیم از نقطه‌ي $A$ در شکل مقابل به یکی از نقاطی برویم که با دایره‌ي بزرگ مشخص شده اند. با فرض اینکه فقط می‌توانیم به سمت راست یا بالا حرکت کنیم، چند مسیر مختلف وجود دارد؟
- $۲^۶$
- $\left(\frac{۱۲!}{۲\times ۶!\times ۶!}\right)$
- $۲^۵$
- $\left(\frac{۱۰!}{۲\times ۵!\times ۵!}\right)$
- $\left(\frac{۱۲!}{۶!\times ۶!}\right)$
راهنمایی
طول دنباله‌های عملیات‌هایی که باید انجام شود تا به یکی از خانه‌های مقصد برسیم چند است؟
راهنمایی
آیا به غیر از طول، شرط دیگری بر دنباله‌ی عملیات‌ها وجود دارد؟
پاسخ
گزینه‌ی ۱ درست است.
هر مسیر از نقطه‌ی $A$ به نقاط بزرگ را می‌توان با یک رشته‌ی دودویی به طول ۶ متناظر ساخت (صفر در رشته به معنی حرکت به سمت راست و یک به معنی حرکت به سمت بالا خواهد بود).
به این نکته توجه کنید که در هر نقطه از مسیر دقیقا دو انتخاب داریم و طول مسیر هم دقیقا ۶ می‌باشد. در نتیجه تعداد کل حالات برابر است با: $2^6$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
