سوال ۶
۱۳۸۵ نفر روی محور اعداد ایستاده‌اند، به طوری که نفر $i$اُم ($۱ \le i \le ۱۳۸۵$) روی نقطه به طول $i$ قرار گرفته است. هر کدام از این افراد یک سنگ دارد و در یک لحظه همه با هم سنگ‌شان را به طرف مثبت پرتاب می‌کند. برد سنگ $i$اُم را با $f(i)$ نشان می‌دهیم. بدین ترتیب سنگ نفر $i$اُم بعد از پرتاب در محل $i+f(i)$ قرار می‌گیرد. می‌دانیم به ازای هر $x$٬ $f(x)$ برابر است با تعداد «صفرها» در نمایش مبنای دوی $x$ (سمت چپ‌ترین رقم در نمایش مبنای دو همواره یک است). به عنوان مثال، $f(۱۳)$ برابر است با ۱، زیرا نمایش مبنای دوی ۱۳ به صورت «۱۱۰۱» می‌باشد. که سه عدد «۱» و یک عدد «۰» دارد.
بعداز اینکه همه سنگ خود را پرتاب کردند، دورترین سنگ کجا می‌افتد؟ ( بزرگ‌ترین مکانی که در آن حدّاقل یک سنگ قرار می‌گیرد کجاست؟)
- ۱۳۸۵
- ۱۳۸۶
- ۱۳۹۰
- ۱۳۹۱
- ۱۳۹۵
پاسخ
گزینه‌ی (۳) درست است.
عدد 1385 در مبنای دو معادل 10101101001 است. از آن‌جایی که این عدد 11 رقمی است و 5 رقم صفر دارد کافیست 5 عدد کوچک‌تر از آن را بررسی کنیم که از مقدار 1385 + 5 بیش‌تر خواهند شد یا خیر. زیرا تنها در صورتی که یکی از این 5 عدد تعداد صفرهای بیش‌تری نسبت به 1385 داشته باشد و اختلافش از 1385 کم‌تر از تعداد صفرهای بیش‌تر آن باشد، مقدار $K + f(K)$ بیش‌تر خواهد بود. برای چک کردن این 5 عدد نیز با استفاده از تفریق باینری به راحتی می‌توان دریافت که 1390 بزرگ‌ترین عددی است که می‌تواند وجود داشته باشد و جواب گزینه ج خواهد بود
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
