یک ساختمان چهار طبقه به شکل عجیبی ساخته شده است. طبقات با شماره‌های صفر (هم کف) تا ۳ شماره‌گذاری شده‌اند. در هر طبقه ۸ اتاق با شماره‌های صفر تا ۷ (به ترتیب از چپ به راست) قرار دارند و در هر یک از اتاق‌های طبقات ۱ تا ۳، یک نفر قرار دارد. اتاق‌ها از طریق کانال‌های «مستقیم» و یا «کج» مطابق شکل زیر به اتاق‌های طبقه‌ی پایین راه دارند.

۱) فرض کنید که یک توپ در اتاق شماره‌ی $i$ از طبقه‌ی سوم قرار دارد ($0≤i≤7$). بر روی این توپ عدد $i$ نوشته شده است ($0≤i≤7$). می‌خواهیم این توپ را از طریق کانال‌های موجود به اتاق شماره‌ی $j$ از طبقه‌ی هم کف بفرستیم. این کار توسط افرادی که در اتاق‌ها هستند بدین‌صورت انجام می‌شود که هر فرد با دریافت توپ و تنها براساس شماره‌ی اتاق و شماره‌ی طبقه‌ای که در آن قرار دارد و نیز عدد $j$ که بر روی توپ نوشته شده است تصمیم می‌گیرد که توپ را از طریق یکی از کانال‌های مستقیم یا کج به اتاق طبقه‌ی پایین ارسال کند (توپ هیچ‌گاه به طبقه‌ی بالا نمی‌رود). مشخص کنید که این افراد براساس چه الگوریتمی می‌توانند این کار را انجام دهند. توجه کنید که لازم است کلیه‌ی افراد براساس یک الگوریتم واحد تصمیم بگیرند. احتیاج به نوشتن برنامه نیست ولی لازم است که اثبات کنید که الگوریتم شما درست عمل می‌کند.

۲) ثابت کنید که مسیر توپ در بند فوق برای هر $i$ و $j$ یکتاست.

۳) فرض کنید که $n$ ($1 \lt n \le 8$) عدد توپ در $n$ اتاق از طبقه‌ی سوم قرار دارند و از سمت چپ به راست بر روی این توپ‌ها شماره‌های صفر تا $n-1$ نوشته شده است. اثبات کنید که اگر افراد موجود در اتاق‌ها همگی براساس الگوریتم بند فوق عمل کنند، توپی که بر روی آن شماره‌ی $i$ نوشته شده است در انتها به اتاق شماره‌ی $i$ در طبقه‌ی هم کف می‌رسد و در این مدت هیچ‌گاه بیش از یک توپ وارد یک اتاق نمی‌شود.

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