در یک شبکه‌ی کامپیوتری، $2^k$ کامپیوتر با شماره‌های ۱ تا $2^k$ وجود دارد. هر یک از این کامپیوترها با یک کد یکتا، که یک دنباله‌ی $k$ تایی از عددهای صفر و یک است، مشخص می‌شود. دو کامپیوتر به صورت مستقیم به هم متصل هستند اگر و فقط اگر کد مربوط به آن‌ها دقیقا در یک رقم با هم تفاوت داشته باشند. برای مثال اگر $k=4$ باشد، کامپیوتری که دارای کد ۰۱۰۰ است مستقیما به کامپیوترهایی با کدهای ۱۱۰۰، ۰۰۰۰، ۰۱۱۰، و ۰۱۰۱ متصل است.

در ابتدای کار، هر یک از کامپیوتر‌ها، دارای یک پیام است. پیامی که در ابتدا در کامپیوتر شماره‌ی $(1\leq i\leq 2^k)i$ وجود دارد. باید در نهایت به کامپیوتر $(1\leq p_i\leq 2^k)p_i$ برسد. فرض کنید که در بین $p_i$ ها عدد تکراری وجود ندارد. یعنی در نهایت هر کدام از کامپیوترها باید یک پیام دریافت کنند.

در هر مرحله، هر کدام از کامپیوتر‌ها می‌تواند پیغامی که دارد را به یکی از کامپیوترهایی که مستقیما به آن متصل است بدهد؛ به شرطی که هر کامپیوتری پس از پایان آن مرحله بیش از یک یپام نداشته باشد. (یعنی اگر در یک مرحله، کامپیوتر $a$ پیام خود را به کامپیوتر $b$ بدهد، کامپیوتر $b$ هم باید پیامی که قبل از این مرحله داشته است را در همین مرحله به یک کامپیوتر بدهد. همچنین هیچ کامپیوتر دیگری غیر از $a$ نمی‌تواند پیام خود را در همین مرحله به $b$ بدهد.)

ثابت کنید که در حداکثر $2^k-1$ مرحله، کامپیوترها می‌توانند همه‌ی پیام‌ها را با توجه به شرط فوق به مقصدشان برسانند.

• سوال بعد
• سوال قبل