مهدی عدد مخفی x از مجموعهی اعداد 1 تا 53 را انتخاب میکند. مریم میخواهد با تعدادی سؤال از عدد x آگاه شود. مریم در هر مرحله دو عدد a و b را با فرض 1≤a<b≤53 انتخاب میکند. اگر x=a یا x=b، مهدی مقدار x را به مریم میگوید و کار تمام است. در غیر این صورت مهدی یکی از سه جواب زیر را به مریم میدهد که عدد انتخابی او کوچکتر از a، بین a و b، یا بزرگتر از b است. مریم با چند سؤال حتماً میتواند عدد مهدی را پیدا کند؟
پاسخ
گزینه (۱) درست است.
ابتدا مریم دو عدد ۱۸ و ۳۶ را انتخاب میکند. اگر x=18 یا x=36 که مسئله حل است و اگر غیر این باشد x در یکی از بازههای [19,35]،[1,17] یا [37,53] قرار دارد که هر یک از آن بازهها دارای ۱۷ عضو بوده و شرایط یکسانی دارند. فرض میکنیم مهدی وجود x را در بازهی اول اعلام کند٬ در این صورت مریم دو عدد ۶ و ۱۲ را انتخاب میکند. اگر x=6 یا x=12 که مسئله حل است و اگر غیر این باشد x در یکی از بازههای [7,11]،[1,5] یا [13,17] قرار دارد که هر یک از آن بازهها دارای ۵ عضو بوده و شرایط یکسانی دارند. فرض میکنیم مهدی وجود x را در بازهی دوم اعلام کند٬ در این صورت مریم دو عدد ۸ و ۱۰ را انتخاب کرده و x را مییابد زیرا اگر x=8 یا x=10 که مسئله حل است و اگر غیر این باشد x یکی از سه عدد ۹٬۷ یا ۱۱ میباشد که مهدی آن را اعلام میکند.