سؤال ۸
آرش و آرمین باهم این بازی را انجام می‌دهند: آرش یک عددِ $x$ بین ۱ و ۱۳۸۴ انتخاب می‌کند و آرمین سعی می‌کند این عدد را حدس بزند. در هر مرحله آرمین یک عدد می‌گوید و آرش رابطه‌ی این عدد را نسبت به $x$ (بزرگ‌تر، کوچک‌تر با مساوی) را مشخص می‌کند. اگر عدد آرمین از $۲x$ کوچک‌تر و بزرگ‌تر یا مساویِ $x$ باشد، آرمین برنده است. می‌خواهیم بدانیم کم‌ترین تعداد مرحله‌ی بازی که آرمین مطمئن است $x$ هر چه که باشد، در این تعداد مرحله او بازی را خواهد برد، چند تاست؟
- ۶۹۲
- ۱۰
- ۹
- ۴
- ۳
پاسخ
گزینه (؟) درست است.
ابتدا اعداد از ۱ تا ۱۳۸۴ را به ۱۱ بازه تقسیم‌بندی زیر افراز می‌کنیم:
$[1,2),[2,3),[3,6),[6,11),[11,22),[22,44),[44,87),[87,174),[174,347),[347,693),[693,1384)$
ابتدا آرمین عدد ۲۲ را پیشنهاد می‌دهد که اگر رمز در بازه مربوط به آن باشد برنده می‌شود و اگر رمز در آن بازه نبوده و بزرگ‌تر از ۲۲ و یا کوچک‌تر از آن باشد توسط آرش اعلام می‌شود. در سمت راست بازه مربوط به ۲۲ فقط ۵ بازه در سمت چپ آن نیز ۵بازه وجود دارد به این معنا که اگر عدد مورد نظر آرش بزرگ‌تر از ۲۲ و در خارج بازه مربوطه به آن بوده با آن بوده با این که کمتر از ۲۲ باشد برای اطمینان از یافتن جواب مراحل یکسانی لازم است. بنابراین فرض می‌کنیم جواب آرش بزرگ‌تر باشد.
آرمین عدد ۱۷۴ را به عنوان دومین عدد پیشنهاد می‌دهد که اگر برنده نشود متناسب با بزرگ‌تر و یا کوچک‌تر گفتن آرش به ترتیب یکی از دو عدد ۳۴۷ و یا ۴۴ را به عنوان عدد سوم پیشنهاد خواهد داد که اگر در این مرحله نیز برنده نشود در مورد اول عدد ۶۹۳ و در مورد عدد دوم عدد ۸۷ را پیشنهاد داده و یقینا برنده خواهد شد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
