You are not allowed to perform this action

سوال ۱۶

در شکل روبرو، جدولی ۵ × ۵ داریم که هر خانه‌ی آن با یکی از دو رنگ سیاه یا سفید رنگ‌آمیزی شده است. به تعدادی خانه از این جدول یک گروه می‌گوییم، اگر بتوان از هر کدام با پیمایش تعدادی خانه‌ی هم‌رنگ و مجاور ضلعی به دیگری رسید. همچنین، یک خانواده از جدول، گروهی از خانه‌هاست که نتوان خانه‌ی جدیدی به آن افزود به‌گونه‌ای که همچنان یک گروه باقی بماند. برای مثال، جدول روبرو از ۳ خانواده تشکیل شده است.

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

  1. ۶
  2. ۴
  3. ۵
  4. ۷
  5. ۳

پاسخ

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

با طی کردن مسیر راست، راست، راست، بالا، بالا، بالا، بالا، راست به این جواب می‌رسیم. می‌توان دید که بیشتر از این مقدار ممکن نیست. می‌دانیم رنگ خانه‌ی شروع در انتها سیاه است. بدون از دست دادن کلیت مسئله، فرض کنید در مرحله‌ی اول به خانه‌ی راست حرکت کرده‌ایم، اگر در مرحله‌ی بعد نیز به راست حرکت کرده باشیم، در بهترین حالت به جواب ۵ می‌رسیم. اگر هم به بالا حرکت کرده باشیم، در انتها حداکثر ۴ خانواده خواهیم داشت.