سعی کنید سوالات را با کمترین راهنمایی حل کنید.

سوال دوم (۱۸ نمره)

در یک زندان، ۳۲ نفر با اسامی متمایز در ۳۲ سلول زندانی هستند. زندان‌بانِ زندان عوض شده و زندان‌بان جدید می‌خواهد لیستی از اسامی ۳۲ زندانی تهیه کند. او برای این کار با زندانی‌ها توافق می‌کند که این بازی را انجام دهند:

آیا زندان‌بان در هر شرایطی (به ازای تمام عملکردهای ممکن زندانی‌ها) مى‌تواند در حداکثر ۱۰۲۴ روز، لیستی از اسامی همه‌ی زندانى‌ها را تهیه کند؟

توضیح: اگر پاسخ شما برای این سوال «بله» است، باید روشی برای زندان‌بان ارائه کنید که در حداکثر ۱۰۲۴ روز، لیست اسامی زندانی‌ها را تهیه کند. هم‌چنین اگر پاسخ شما برای این سوال «خیر» است، باید اثبات کنید به ازای هر الگوریتمِ زندان‌بان، حالتی وجود دارد که او به هدفش نرسد.

راهنمایی

روی یکی از زندانیانی که زندان بان در روز اول او را نمیبیند، فکر کنید.