سوال ۱۸
در شکل مقابل می‌خواهیم از نقطه‌ی $A$ به نقطه‌ی $B$ برویم، طوری که از نقطه‌ی $M$ بگذریم. در هر مرحله می‌توان یک واحد در یکی از چهار جهت (چپ، راست، بالا و پایین) حرکت کرد. هم‌چنین از هر نقطه اجازه داریم حداکثر یک بار عبور کنیم.
به چند طریق این کار ممکن است، طوری که دقیقا ۱۰ گام برداریم؟
- ۸
- ۱۰
- ۱۶
- ۱۸
- ۲۰
راهنمایی
یا حرکات A به M در هشت مرحله انجام می شود و سپس حرکات M به B دو مرحله طول می کشد و یا A به M شش مرحله و M به B چهار مرحله طول‌می کشد
پاسخ
گزینه‌ی ۴ درست است.
حرکت به دو قسمت تقسیم می‌شود:
- حرکت از $A$ به $M$ (بخش یکم حرکت)
- حرکت از $M$ به $B$ (بخش دوم حرکت)
تعداد حرکات هر یک از دو بخش باید زوج باشد، پس تنها دو حالت زیر را داریم:
- بخش یکم شامل ۸ حرکت و بخش دوم شامل ۲ حرکت باشد؛ در این صورت بخش دوم حرکت (با بررسی مسیر از انتها) ۲ حالت دارد. با مشخص شدن بخش دوم حرکت، دو گام آخر بخش یکم نیز به صورت یکتا مشخص می‌شود. بدون از دست دادن کلیت مسئله فرض کنید ۴ گام آخر به شکل زیر سمت راست باشد. با حالت‌بندی نیز می‌توان دید ۶ گام ابتدای مسیر ۵ حالت دارد.
- بخش یکم شامل ۶ حرکت و بخش دوم شامل ۴ حرکت باشد؛ در این صورت بخش دوم حرکت (با بررسی مسیر از انتها) ۲ حالت دارد. با مشخص شدن بخش دوم حرکت، دو گام آخر بخش یکم نیز به صورت یکتا مشخص می‌شود. بدون از دست دادن کلیت مسئله فرض کنید ۶ گام آخر به شکل زیر سمت چپ باشد. در این صورت ۴ گام ابتدای مسیر $\binom{4}{1}$ حالت دارد.
پس کل کار به $2 \times 5 + 2 \times 4 = 18$ حالت قابل انجام است.