======سوال ۹======
{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۳:9_23.jpg?200 |}}
مهشید قطعه ای از صفحه‌ي شطرنج را به شکل رو‌به‌رو بریده است. او می خواهد مهره‌ي شاه را از خانه‌ی $A$ به خانه‌ی $B$ ببرد به طوری که:
  * کمترین تعداد خانه را طی کند.
  * تعداد خانه های سیاه مسیر دوبرابر تعداد خانه های سفید آن باشد( خانه های $A$ و $B$ هم جزء مسیر هستند) .

مهره‌ی شاه در هر حرکت خود می تواند از یک خانه به خانه‌ی دیگر برود، به شرطی که این دو خانه در حداقل یک نقطه اشتراک داشته باشند. مثلا از خانه ی $A$ مستقیما می توان به خانه های راست و بالا-راست آن رفت. مهشید به چند طریق می تواند این کار را انجام دهد؟

  - ۸
  - ۰
  - ۱
  - ۱۶
  - ۳


<راهنمایی>
طول کوتاه‌ترین مسیری که مهره با طی کردن از خانه‌ی $A$ به خانه‌ی $B$ می‌رسد چند است؟
</راهنمایی>

<راهنمایی>
طبق نسبت بیان شده‌ی مسئله، مسیر مورد نظر چند خانه‌ی سفید باید داشته باشد؟
</راهنمایی>

<راهنمایی>
اگر دنباله‌ی حرکات مسیر را در نظر بگیریم، دنباله‌ی یک کوتاه‌ترین مسیر چه ویژگی‌‌ای دارد؟
</راهنمایی>

<راهنمایی>
در راستای راهنمایی پیشین، نشان دهید دنباله‌ی یک کوتاه ترین مسیر از دو بار حرکت به راست و سه بار حرکت به سمت بالا-راست تشکیل شده است.
</راهنمایی>

<راهنمایی>
تنها زمانی می‌توان خانه‌های سفید را دید که دقیقا یک حرکت به سمت راست کرده باشیم.
</راهنمایی>

<راهنمایی>
حالت بندی کنید اولین حرکت به سمت راست در چندمین مرحله‌ی حرکت شکل گیرد.
</راهنمایی>

<پاسخ>

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


تعداد خانه‌های مسیر ۶تا هستند در نتیجه باید دقیقا از ۲ خانه‌ی سفید بگذریم. در نتیجه هر زمان که به خانه‌ی سفید رسیدیم باید به خانه‌ی سفید بالا-راست آن برویم و سپس از خانه‌های سفید خارج شویم. پس تعداد روش‌های مختلف این کار ۳ حالت است (باتوجه به این که اولین بار به کدام خانه‌ی سفید رسیده‌ایم).

</پاسخ>
  * [[سوال ۱۰|سوال بعد]]
  * [[سوال ۸|سوال قبل]]