====== سوال ۱۸ ======

{{path.png?150 }}
در شکل مقابل می‌خواهیم از نقطه‌ی $A$ به نقطه‌ی $B$ برویم، طوری که از نقطه‌ی $M$ بگذریم. در هر مرحله می‌توان یک واحد در یکی از چهار جهت (چپ، راست، بالا و پایین) حرکت کرد. هم‌چنین از هر نقطه اجازه داریم حداکثر یک بار عبور کنیم.
به چند طریق این کار ممکن است، طوری که دقیقا ۱۰ گام برداریم؟


  - ۸
  - ۱۰
  - ۱۶
  - ۱۸
  - ۲۰

<راهنمایی>
یا حرکات A به M در هشت مرحله انجام می شود و سپس حرکات M به B دو مرحله طول می کشد
و یا A به M شش مرحله و M به B چهار مرحله طول‌می کشد
</راهنمایی>
<پاسخ>
گزینه‌ی ۴ درست است.

حرکت به دو قسمت تقسیم می‌شود:


  * حرکت از $A$ به $M$ (بخش یکم حرکت)
  * حرکت از $M$ به $B$ (بخش دوم حرکت)



تعداد حرکات هر یک از دو بخش باید زوج باشد، پس تنها دو حالت زیر را داریم:

  * بخش یکم شامل ۸ حرکت و بخش دوم شامل ۲ حرکت باشد؛ در این صورت بخش دوم حرکت (با بررسی مسیر از انتها) ۲ حالت دارد. با مشخص شدن بخش دوم حرکت، دو گام آخر بخش یکم نیز به صورت یکتا مشخص می‌شود. بدون از دست دادن کلیت مسئله فرض کنید ۴ گام آخر به شکل زیر سمت راست باشد. با حالت‌بندی نیز می‌توان دید ۶ گام ابتدای مسیر ۵ حالت دارد.

  * بخش یکم شامل ۶ حرکت و بخش دوم شامل ۴ حرکت باشد؛ در این صورت بخش دوم حرکت (با بررسی مسیر از انتها) ۲ حالت دارد. با مشخص شدن بخش دوم حرکت، دو گام آخر بخش یکم نیز به صورت یکتا مشخص می‌شود. بدون از دست دادن کلیت مسئله فرض کنید ۶ گام آخر به شکل زیر سمت چپ باشد. در این صورت ۴ گام ابتدای مسیر $\binom{4}{1}$ حالت دارد.

{{path3.png?150 }}
{{path2.png?150 }}
   
پس کل کار به 
$2 \times 5 + 2 \times 4 = 18$
حالت قابل انجام است.
</پاسخ>

  * [[سوال ۱۹|سوال بعد]]
  * [[سوال ۱۷|سوال قبل]]