المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۶:سوال ۱۰

سوال ۱۰

یک جدول $۸\times ۸$ داریم که ۳۲ خانه‌‌ی ۴ ستون اولش سیاه و ۳۲ خانه‌‌ی دیگرش سفید هستند. در هر حرکت می‌توانیم رنگ دو خانه‌ی مجاور را با هم عوض کنیم (در صورتی که هم‌رنگ باشند تغییری در رنگشان رخ نمی‌دهد.) دو خانه مجاورند اگر و فقط اگر ضلع مشترک داشته باشند. کم‌ترین تعداد حرکت لازم برای شطرنجی کردن جدول چند است؟ جدولی شطرنجی است که رنگ هیچ دو خانه‌ی مجاوری در آن یکی نباشد.

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

پاسخ

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

مسئله مانند آن است که بعضی از خانه‌های موجود در چهار ستون اول را چنان منتقل کنیم که در نهایت صفحه شطرنجی شود. در هر انتقال هر خانه‌ی سیاه فقط قادر است به خانه سفید مجاورش (در صورت وجود) منتقل شود. هر انتقال یک حرکت محسوب می‌شود. بهترین حالت آن است که سیاه‌های موجود در ستون چهارم به ستون‌های هشتم و هفتم٬ سیاه‌های موجود در ستون سوم به ستون‌های ششم و پنجم٬ سیاه‌های موجود در ستون دوم به ستون‌های چهارم و سوم و بالاخره سیاه‌های موجود در ستون اول به ستون‌های دوم و اول منتقل شوند. تعداد حرکات در این مورد در جدول مقابل نشان داده شده‌اند که در مجموع ۶۴ می‌شود.


ابزار صفحه