حداقل چند خانه ممکن است در روز اول آلوده بوده باشند؟

Question

در یک شهر $n^2$خانه به شکل یک مربع $n×n $وجود دارد و در یک روز تعدادی از خانه‌ها آلوده به یک نوع ویروس شده‌اند. فرض کنید این ویروس به صورت زیر گسترش می یابد: هر خانه وقتی آلوده به ویروس می‌شود که لااقل دو تا از همسایه‌های دیوار به دیوارش در روز قبل آلوده بوده باشند. در صورتی که در نهایت تمام خانه‌ها آلوده شوند، حداقل چند خانه ممکن است در روز اول آلوده بوده باشند؟

Answer 1

جواب $n$ حانه است. ابتدا نشان میدهیم که این جواب درسته(یعنی با $n$ خانه آلوده کل خانه ها آلوده می شوند) سپس نشان می دهیم که با تعداد کمتر امکان پذیر نیست. اگر قطر اصلی را در نظر بگیریم و در روز اول خانه های روی این قطر آلوده شده باشند آنگاه در روز بعد قطرهای مجاور قطر اصلی آلوده میشوند(مثال را نگاه کنید خانه های قرمز آلوده هستند) و پس از هر روز قطرهای بعدی و به این صورت کل خانه ها آلوده می شوند.

دو خانه آلوده زمانی میتوانند بیشترین خانه را آلوده کنند که روی قطر باشند و مجاور برای هر تعداد خانه آلوده هم با کمی دقت بیشترین کارایی زمانی است که روی یک قطر باشند در این حالت هر $m$ خانه میتواند مربعی به طول $m \times m$ را آلوده کند.

همچنین اگر منطقه ای آلوده باشد و بخواهیم خانه ای را به عنوان آلوده انتخاب کنیم که بیشترین کارایی را داشته باشد باید این خانه روی قطر ناحیه باشد با توجه به آنچه گفته شد حداقل $ n $ خانه لازم است.