سوال ۷
مهدی عدد مخفی $x$ از مجموعه‌ی اعداد $1$ تا $53$ را انتخاب می‌کند. مریم می‌خواهد با تعدادی سؤال از عدد $x$ آگاه شود. مریم در هر مرحله دو عدد $a$ و $b$ را با فرض $1 \le a < b \le 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$ یکی از سه عدد ۹٬۷ یا ۱۱ می‌باشد که مهدی آن را اعلام می‌کند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
