نتانیاهو $2^{2^n}$ جاسوس به سرزمین سلطان فرستاد و سلطان تمام آن‌ها را شناسایی و دست‌گیر کرد. سلطان در هر روز محاکمه می‌تواند تمام جاسوسان را به صف کرده و به ترتیب از آن‌ها بپرسد: «آیا دانش‌پژوهان دوره‌ی ۹۶ احمق هستند یا خیر؟» که پرسشی بدیهی با پاسخ واضح است! قبل از محاکمه، با بررسی‌ها‌ی زیاد سلطان متوجه موارد زیر شد:

• هر نفر از جاسوسان یا مبتدی است یا حرفه‌ای.
• هر یک از جاسوسان یک هم‌پیمان در میان جاسوسان دیگر دارد. رابطه‌ی هم‌‌پیمانی دوطرفه است.
• هم‌پیمان هر جاسوس مبتدی، یک جاسوس حرفه‌ای است و بالعکس.
• در هر روز محاکمه، هر جاسوس به این شکل پاسخ خواهد داد: اگر هم‌پیمان او زودتر در صف بوده و پاسخ داده باشد، فرد مذکور نیز مانند او پاسخ می‌دهد، در غیر این صورت اگر فرد مذکور مبتدی باشد پاسخ درست و در غیر این صورت پاسخ نادرست خواهد داد.

سلطان می‌خواهد مبتدی یا حرفه‌ای بودن هر یک از جاسوسان را بفهمد.

آ) ثابت کنید سلطان می‌تواند این کار را با یک محاکمه‌ی $n+1$ روزه انجام دهد. (۵۰ امتیاز)

ب) ثابت کنید سلطان نمی‌تواند به طور مطمئن کار خود را در یک محاکمه‌ی $n$ روزه انجام دهد. (۵۰ امتیاز)

• سوال قبل