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

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

1 پاسخ

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

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

enter image description here

enter image description here

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

enter image description here

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

enter image description here

سال نو مبارک!


حمایت مالی


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