سوال ۲۳
رشید به تازگی با دو نوع دستگاه به نام های کفگیر و سقفگیر آشنا شده است که به صورت زیر عمل می کنند:
- دستگاه کفگیر عدد $x$ را به عنوان ورودی گرفته و $\lfloor x/۲ \rfloor$ را به عنوان خروجی بر میگرداند.
- دستگاه سقفگیر عدد $x$ را به عنوان ورودی گرفته و $\lceil x/۲ \rceil$ را به عنوان خروجی بر میگرداند.
رشید ۱۳۹۱ دستگاه در یک ردیف پشت سر هم قرار داده است به طوریکه دستگاه $i$ام کفگیر است اگر $i$ عددی اول باشد و در غیر این صورت سقفگیر است. برای مثال دستگاه اول و چهارم سقفگیر هستند و دستگاه دوم و سوم کفگیر هستند.
حال رشید یک عدد طبیعی به عنوان ورودی به دستگاه اول می دهد٬ سپس خروجی این دستگاه وارد دستگاه دوم میشود٬ خروجی دستگاه دوم وارد دستگاه سوم میشود و به همین ترتیب تا دستگاه ۱۳۹۱ام که خروجی نهایی را تولید میکند. به ازای چند عدد به عنوان ورودی دستگاه اول٬ خروجی نهایی برابر با یک میشود؟
- ۱۳۹۰
- ۱۹۳۳۴۹۰
- $۲^ {۱۳۹۱}$
- $۲^ {۱۳۹۰}$
- ۱۳۹۱
راهنمایی
فرض کنید عدد $x$ را داشته باشیم و یک بار از دستگاه سقفگیر استفاده کنیم تا به عدد $y$ برسیم. بر حسب $y$ چند مقدار متفاوت برای $x$ وجود خواهد داشت؟
راهنمایی
راهنمایی یک را برای دستگاه کفگیر هم اجرا کنید.
راهنمایی
اعمال را به طور برعکس دنبال کنید. فرض کنید در نهایت به عدد ۱ رسیده باشیم. در گام قبل چند عدد مختلف ممکن است به دستگاه داده شده باشند؟
راهنمایی
بنا بر دو راهنمایی اول، از لحاظ تعداد حالات، آیا تفاوتی میکند در دنبال کردن برعکس فرآیند ساخت عدد ۱، دستگاه بعدی سقفگیر است یا کفگیر؟
پاسخ
گزینه‌ی ۳ درست است.
مستقل از اینکه دستگاه‌ها کفگیر باشند یا سقفگیر، همیشه تعداد اعداد $2^{1391}$ خواهد بود.
در واقع تعداد اعدادی که پس از $i$ مرحله به ۱ ختم می‌شوند، $2^i$تا است.
اگر پس از یک سقفگیر به عدد $x$ برسیم، عدد قبلی $2x-1$ یا $2x$ بوده است.
اگر پس از یک کفگیر به عدد $x$ برسیم، عدد قبلی $2x+1$ یا $2x$ بوده است.
نکته‌ی دیگر این است که در هر مرحله مجموعه‌ی جواب‌ها یک بازه است که در مرحله‌ی بعد این بازه دو برابر میشود (با استقرا ثابت کنید).
در نتیجه پس از ۱۳۹۱ مرحله $2^{1391}$ عدد مختلف خواهیم داشت.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
