المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۹

سوال ۹

مهشید قطعه ای از صفحه‌ي شطرنج را به شکل رو‌به‌رو بریده است. او می خواهد مهره‌ي شاه را از خانه‌ی $A$ به خانه‌ی $B$ ببرد به طوری که:

  • کمترین تعداد خانه را طی کند.
  • تعداد خانه های سیاه مسیر دوبرابر تعداد خانه های سفید آن باشد( خانه های $A$ و $B$ هم جزء مسیر هستند) .

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

  1. ۸
  2. ۰
  3. ۱
  4. ۱۶
  5. ۳

راهنمایی

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

راهنمایی

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

راهنمایی

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

راهنمایی

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

راهنمایی

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

راهنمایی

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

پاسخ

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

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


ابزار صفحه