====== سوال ۲۸ ======
{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۷:287.png |}}
در شکل روبه‌رو چند مسیر از $A$ به $B$ وجود دارد که از $C$ می‌گذرد ولی از $D$ نمی گذرد؟(در طول مسیر فقط می‌توان به سمت راست یا بالا حرکت کرد.)

  - ۵۱
  - ۱۵۰
  - ۱۸۰
  - ۴۵۰
  - ۵۴۰

<پاسخ>
گزینه (۵) درست است.

در یک شبکه $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$$

</پاسخ>
  * [[سوال ۲۹|سوال بعد]]
  * [[سوال ۲۷|سوال قبل]]