المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

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

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

پاسخ

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

به مانند استدلال قسمت قبل دست کم $\lceil \frac{16}{۳} \rceil = 6$ مرحله لازم است. در زیر نیز روشی با ۶ مرحله ارائه شده است (در مرحله‌ی $i$ خانه‌های با شماره‌ی $i$ را تغییر رنگ می‌دهیم):

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


ابزار صفحه