به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
84 بازدید
سوال شده در دبیرستان توسط
ویرایش شده توسط

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

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط
انتخاب شده توسط
 
بهترین پاسخ

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

enter image description here

enter image description here

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

enter image description here

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

enter image description here

به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...