Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

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

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

راهنمایی

دست کم به 16۵=4 مرحله نیاز است

پاسخ

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

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

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


ابزار صفحه