معمای شماره ۱۹

تعداد صد کامپیوتر در یک ساختار شبکه ای 10\times10 همانند شکل زیر به هم متصل شده‌اند. در آغاز، دقیقا ۹ تا از آنها گرفتار یک ویروس کامپیوتری هستند. این ویروس کامپیوتری به این صورت منتقل می‌شود: هر کامپیوتری که به طور مستقیم به دو کامپیوتر آلوده متصل باشد نیز آلوده این ویروس خواهد شد.

آیا این ویروس خواهد توانست تمام این یکصد سیستم کامپیوتری را آلوده کند؟
(کامپیوترهای آلوده با رنگ قرمز مشخص شده‌اند)

نمایش راه حل

پاسخ مساله خیر خواهد بود.
ممکن است شروع به رنگ کردن نمادهای دایره ای کنید تا به پاسخ برسید، اما راه حل کلی تری هم وجود دارد. در اینجا با مفهوم محیط آلودگی آشنا می شویم. یک کامپیوتر می تواند روی آلودگی ۴ کامپیوتر تاثیر داشته باشد، پس محیط آلودگی برای یک کامپیوتر ۴ خواهد بود.

محیط آلودگی ۹ کامپیوتر حداکثر ۳۶ خواهد بود ( 4\times9=36) البته وقتی صحبت از حداکثر می کنیم منظور ما حالتی است که در آن هیچیک از کامپیوتر های آلوده بهم متصل نباشند( یا به اصطلاح همسایه هم نباشند)
به عنوان مثال اگر ۹ کامپیوتر روی یک خط راست باشند، در این صورت محیط آلودگی ۲۰ خواهد بود.
نکته مساله در این است که اگر تعداد کامپیوترهای آلوده بیشتر شود محیط آلودگی هرگز تغییری نمی کند. در شکل A محیط آلودگی ۸ می باشد. در شکل B کامپیوتر جدیدی آلوده می شود، اما محیط آلودگی همچنان ۸ خواهد بود. در شکل C کامپیوتر دیگری آلوده می شود اما باز هم محیط آلودگی ۸ باقی می ماند.

پس وقتی محیط آلودگی ۹ کامپیوتر حداکثر ۳۶ می باشد، و این محیط آلودگی بیشتر نخواهد شد. یعنی هرگز به ۴۰ نخواهد رسید ، آلودگی در بین تمام کامپیوترها گسترش نخواهد داشت. ( وقتی تمام کامیپوترهای شکل آلوده شوند محیط آلودگی ۴۰ خواهد بود و نه ۳۶)

پاسخ دهید

*