سوال ۲۲

گزینه‌ی ۳ درست است.

ابتدا روشی با چهار مرحله ارائه می‌دهیم. روزبه در ابتدا یک دور به طول پنج انتخاب می‌کند. چه پاسخ خیر باشد و چه بله، رأس‌های کاندید برای گنج در یک دور به طول پنج هستند. حال روزبه یک دور به طول پنج انتخاب می‌کند که شامل دو رأس مجاور از پنج رأس کاندید باشد.

• اگر جواب خیر باشد، سه رأس کاندید برای گنج می‌ماند. حال یک دور به طول پنج انتخاب می‌کنیم که شامل دو رأس مجاور از این سه رأس باشد. اگر جواب خیر باشد با یک پرسش دیگر (دوری که شامل یکی از دو رأس کاندید باشد) مسئله حل می‌شود و اگر هم جواب بله باشد که گنج پیدا شده‌ است.
• اگر جواب بله باشد با یک پرسش دیگر (دوری که شامل یکی از دو رأس کاندید باشد) مسئله حل می‌شود.

حال ثابت می‌کنیم روشی با بهتر از چهار مرحله وجود ندارد. در ابتدا ۱۰ رأس کاندید برای گنج داریم. در هر مرحله رأس‌های کاندید به دو دسته‌ی $X$ (درون دور انتخاب شده) ‌و $Y$ (خارج دور انتخاب شده) تقسیم می‌شوند. ممکن است در هر مرحله پاسخ طوری باشد که تعداد خانه‌های کاندید بیش‌تری باقی بماند. پس دست کم $\lceil log_2 10 \rceil = 4$ مرحله نیاز است.