المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۷

سؤال ۷

یک جدول ۲ بعدی نامتناهی را در نظر بگیرید که در ابتدا تمام خانه‌های آن سفید است. در مرحله‌ی اول یکی از خانه‌های آن را به‌دل‌خواه سیاه می‌کنیم (شکل مقابل). از مرحله دوم به بعد، در هر مرحله کلیه‌ی خانه‌هایی که ۱، ۲ و ۳ همسایه سیاه دارند را مشخص می‌کنیم و سپس همه‌ی آن‌ها را سیاه و بقیه‌ی خانه‌ها را سفید می‌کنیم. (دو خانه مجاورند اگر ضلع مشترکی داشته باشد).

بزرگ‌ترین $k$ای را پیدا کنید که خانه‌ای که در مرحله‌ی اول سیاه شده بود در مرحله‌ی $k$ام هم سیاه شود.

  1. ۱
  2. ۷
  3. ۸
  4. ۱۶
  5. $k$هرقدرمی‌تواند بزرگ باشد.

پاسخ

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

در مرحله دوم خانه مورد نظر سفید و هر چهار خانه مجاور آن سیاه هستند٬ بنابراین در مرحله سوم نیز آن خانه سفید باقی خواهد ماند. در حقیقت در هر مرحله هر چهار خانه مجاور آن خانه یا سفید هستند و یا سیاه٬ بنابراین هرگز آن خانه سیاه نخواهد شد.


ابزار صفحه