المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۷

سوال ۷

مهدی عدد مخفی ‎$x$‎ از مجموعه‌ی اعداد ‎$1$‎ تا ‎$53$‎ را انتخاب می‌کند. مریم می‌خواهد با تعدادی سؤال از عدد ‎$x$‎ آگاه شود. مریم در هر مرحله دو عدد ‎$a$‎ و ‎$b$‎ را با فرض ‎$1 \le a < b \le 53$‎ انتخاب می‌کند. اگر ‎$x=a$‎ یا ‎$x=b$‎، مهدی مقدار ‎$x$‎ را به مریم می‌گوید و کار تمام است. در غیر این صورت مهدی یکی از سه جواب زیر را به مریم می‌دهد که عدد انتخابی او کوچک‌تر از ‎$a$‎، بین ‎$a$‎ و ‎$b$‎، یا بزرگ‌تر از ‎$b$‎ است. مریم با چند سؤال حتماً می‌تواند عدد مهدی را پیدا کند؟

  1. ‎۳
  2. ۴
  3. ۵
  4. ۶
  5. ۷‎

پاسخ

گزینه (۱) درست است.

ابتدا مریم دو عدد ۱۸ و ۳۶ را انتخاب می‌کند. اگر $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$ یکی از سه عدد ۹٬۷ یا ۱۱ می‌باشد که مهدی آن را اعلام می‌کند.


ابزار صفحه