المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۸

در شکل روبه‌رو چند مسیر از $A$ به $B$ وجود دارد که از $C$ می‌گذرد ولی از $D$ نمی گذرد؟(در طول مسیر فقط می‌توان به سمت راست یا بالا حرکت کرد.)

  1. ۵۱
  2. ۱۵۰
  3. ۱۸۰
  4. ۴۵۰
  5. ۵۴۰

پاسخ

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

در یک شبکه $m\times n$ برای رفتن از گوشه‌ی سمت چپ و پایین به گوشه سمت راست و بالا با شرایط مسئله(جهت حرکت فقط به سمت راست یا بالا)$\frac{(m+n)!}{m!n!}$ مسیر وجود دارد. زیرا اگر حرکت به سمت بالا را با $U$ و حرکت به سمت راست با $R$ نمایش دهیم تعداد مسیرها برابر با تعداد حالات چیدن $m$ عدد $U$ و $n$ عدد $R$ در پیش ‌هم‌دیگر می‌باشد که برابر با $\frac{(m+n)!}{m!n!}$ می‌باشد. در این مسئله از $C$ به $B$ مجموعا $\frac{11!}{4!7!}$ مسیر و از $A$ به $C$ مجموعا $\frac{3!}{2!1!}$ مسیر وجود دارد. همین‌طور تعداد مسیرهای موجود بین $C$ و $D$ برابر با $\frac{6!}{2!4!}$ و تعداد مسیر بین $D$ و $B$ برابر با $\frac{5!}{2!3!}$ می‌باشد. لذا تعداد مسیرها با شرایط مسئله برابر خواهد بود با:

$$\frac{3!}{2!1!} \times [\frac{11!}{4!7!}-\frac{5!}{2!3!} \times \frac{6!}{2!4!}]=540$$


ابزار صفحه