خانواده‌ی آقای محسنی در ساوه زندگی می کنند و باغ انار دارند. حسن٬ پسر کوچک خانواده٬ می خواهد به دیدن دوستش حسین که در اصفهان زندگی می کنند برود. آن ها قرار می گذارند که به محض رسیدن حسن٬ بازی زیر را انجام دهند:
در ابتدا حسین یک عدد طبیعی بزرگتر از صفر و کوچکتر از ۱۰ در ذهنش انتخاب می کند. سپس در هر مرحله حسن می تواند:
هر وقت حسن یک سوال نوع اول را بپرسد و حسین جواب «بله» بدهد٬ حسن برنده می شود و حسین به او یک جعبه گز سوغاتی می دهد. حسن حداقل چند انار باید با خودش به اصفهان ببرد که مطمئن باشد حتما و در هر شرایطی می تواند به جعبه‌ی گز برسد؟ دقت کنید که حسن پس از شنیدن جواب بله برنده می شود و این که عدد حسین را فهمیده باشد کافی نیست.
پاسخ
گزینه‌ی «۵» درست است.
ابتدا لازم است لمی کاربردی را ثابت کنیم. می‌خواهیم ثابت کنیم که در این‌گونه سوالات که می‌توان با پرسیدن یک سوال محدوده جواب را به دو قسمت تقسیم کرد، کارآمد ترین روش، روش باینری سرچ است.
به این طریق که ابتدا با پرسیدن یک سوال بازه جواب را نصف می‌کنیم و سپس در نصفه باقی‌مانده نیز همین کار را می‌کنیم الی آخر که در نهایت با پرسش $logn$ سوال در پایه ی دو به جواب می‌رسیم. اثبات این هم بسیار راحت است چراکه اولا تعداد پرسش ها با توجه به $n$ صعودی است ثانیا اگر ما با پرسشمان بازه جواب را به دو نصف تقسیم نکنیم یکی از بازه ها حتما بزرگتر از $\frac{n}{2}$ می‌شود پس تعداد پرسش ها حتما بیش‌تر مساوی باینری سرچ می‌شود.
حال می‌رویم سراغ حل این سوال. فرض کنید پرسش نوع دو انجام ندهیم پس باید 9 پرسش در بدترین حالت انجام دهیم، حال فرض کنید پرسش نوع دو هم انجام دهیم، از آن‌جا که گفتیم اگر پرسش نوع دویی انجام شود باید حتما روی عنصر وسطی انجام شود پس با این پرسش 3 انار از دست می‌دهیم و در بدترین حالت بازه‌ی 4 تایی حذف می‌شود. حال حالت برای جواب مانده و ما اگر بهترین پرسش نوع دو را انجام دهیم در بدترین حالت 2 تا از حالت‌ها حذف می‌شوند!! پس بهتر است پرسش نوع دویی انجام ندهیم! بنابراین در بدترین حالت با پرسیدن 8 سوال به جواب می‌رسیم.