سوال ۱۵
اعداد ۱ تا $n$ را به ترتیب لغت‌نامه‌‌ای مرتب کرده‌ایم. جای‌گاه عدد $k$ ($1 \le k \le n$) را با $Q_{n,k}$ نمایش می‌دهیم. به عنوان نمونه $n$ را برابر ۱۳ قرار می‌دهیم و اعداد به صورت زیر مرتب می‌شوند (از چپ به راست): $$1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9$$
لذا $Q_{۱۳,۱۰} = ۲$ و $Q_{۱۳,۲} = ۶$ می‌باشد. کوچک‌ترین $n$ را بیابید که $Q_{n,۱۲۳} = ۲۰۰$ شود.
- ۱۱۶۹
- ۱۱۷۱
- ۱۱۷۳
- ۱۱۷۵
- امکان‌پذیر نیست
پاسخ
گزینه (۲) درست است.
به سادگی معلوم می‌شود که کوچک‌ترین $n$ برای رسیدن به منظور٬ عددی است چهار رقمی. تا قبل از ۱۲۳ باید ۱۹۹ عدد قرار گیرد. در بین اعداد یک رقمی فقط یک عدد(عدد ۱)٬ در بین اعداد دو رقمی فقط سه عدد(اعداد ۱۱٬۱۰ و ۱۲)و بالاخره در بین اعداد سه رقمی فقط بیست‌‌وسه عدد(اعداد ۱۰۰ تا ۱۲۲) قبل از ۱۲۳ قرار می‌گیرند که تعداد کل آن‌ها ۲۷ می‌شود. بنابراین باید عدد چهار رقمی $n$ چنان باشد که قبل از ۱۲۳ به تعداد ۲۷-۱۹۹ یعنی ۱۷۲ عدد قرار گیرد. معلوم است که همه اعداد از ۱۰۰۰ تا ۱۲۲۹ که تعداد آن‌ها ۲۳۰تا می‌باشد قبل از ۱۲۳ قرار می‌گیرند که یکصدوهفتادو دومین آن‌ها ۱۱۷۱ می‌باشد. بنابراین اگر $n$ را برابر ۱۱۷۱ قرار دهیم به جواب خواهیم رسید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
