المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۰

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

  1. $A$ به خانه‌ی مجاورش که خالی است برود.
  2. اگر مهره‌ی $A$، مهره‌ی $B$ و خانه‌ی خالی به همین ترتیب و در یک راستا(سطری٬ ستونی یا قطری) باشند٬ و رنگ $B$ مخالف رنگ $A$ باشد٬ $A$ می‌تواند با پریدن از روی $B$ به مکان خالی برود.

با حداقل چند حرکت می‌توان جای مهره‌های سیاه و سفید را عوض کرد؟

  1. ۶
  2. ۷
  3. ۸
  4. ۹
  5. ۱۰

پاسخ

گزینه (۳) درست است.

بهترین حرکت به شکل زیر است که ۸ مرحله طول می‌کشد:

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


ابزار صفحه