المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

یک جدول $4 \times 4$ داریم که ابتدا تمام خانه‌های آن سفید است. دو خانه را مجاور می‌گوییم، اگر در یک ضلع مشترک باشند. قلمرو هر خانه عبارت است از خود آن خانه و تمامی خانه‌های مجاورش. بنابراین قلمرو هر خانه شامل حداکثر ۵ خانه است. در هر مرحله می‌توان تعدادی از خانه‌های قلمرو یک خانه را انتخاب کرد و رنگ آن‌ها را تغییر داد (از سفید به سیاه و برعکس). در حداقل چند مرحله می‌توان تمام خانه‌های جدول را سیاه کرد؟

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

پاسخ

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

در هر مرحله می‌توان رنگ حداکثر ۵ خانه را تغییر داد. از آن‌جایی که رنگ ۱۶ خانه باید تغییر کند، دست کم به $\lceil \frac{16}{۵} \rceil = 4$ مرحله نیاز است. شکل زیر نیز روشی با ۴ مرحله ارائه می‌دهد (در مرحله‌ی $i$ خانه‌های با شماره‌ی $i$ را تغییر رنگ می‌دهیم):

پس پاسخ برابر ۴ است.


ابزار صفحه