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