====== محاکمه‌ی جاسوسان ======

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


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


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

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

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



  * [[سوال ۲|سوال قبل]]