۱۶ کامپیوتر مطابق شکل به هم ارتباط داده شدهاند.
هر کامپیوتر میتواند در هر ثانیه یک فایل اطلاعاتی را به
فقط یکی از کامپیوترهایی که به آن مربوط است، منتقل کند.
برای این که یک فایل اطلاعاتی جدید که فقط در یکی از کامپیوترها موجود
است، به تمام کامپیوترها منتقل شود، حداقل چند ثانیه وقت لازم است؟
پاسخ
گزینه (۲) درست است.
در انتهای ثانیههای اول٬ دوم و سوم به ترتیب حداکثر ۴٬۲ و ۸ کامپیوتر میتوانند فایل اطلاعاتی جدید را دارا باشند. پس برای اینکه همهی کامپیوترها٬ فایل اطلاعاتی جدید را دارا باشند حداقل ۴ ثانیه وقت لازم است. ثابت میکنیم در ۴ ثانیه این کار عملی است. برای این منظور فایل اطلاعاتی جدید را بر روی کامپیوتر A1 فرض میکنیم. این فایل در انتهای ثانیههای اول تا چهارم به ترتیب زیر منتقل خواهند شد:
ثانیه چهارم ثانیه سومثانیه دوم ثانیه اول
A1⟶A2A1⟶A3A1⟶A4A1⟶A5A2⟶A9A2⟶A6A2⟶A8A3⟶A10A3⟶A7A9⟶A12A9⟶A15A4⟶A11A6⟶A13A10⟶A14A12⟶A16
A1 میتواند هر کدام از کامپیوترهای موجود باشد. به عنوان مثال یک نمونه از شمارهگذاری کامپیوترها در زیر آمده است: