المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۲۳

سوال ۲۳

رشید به تازگی با دو نوع دستگاه به نام های کفگیر و سقفگیر آشنا شده است که به صورت زیر عمل می کنند:

  • دستگاه کفگیر عدد $x$ را به عنوان ورودی گرفته و $\lfloor x/۲ \rfloor$ را به عنوان خروجی بر میگرداند.
  • دستگاه سقفگیر عدد $x$ را به عنوان ورودی گرفته و $\lceil x/۲ \rceil$ را به عنوان خروجی بر میگرداند.

رشید ۱۳۹۱ دستگاه در یک ردیف پشت سر هم قرار داده است به طوریکه دستگاه $i$ام کفگیر است اگر $i$ عددی اول باشد و در غیر این صورت سقفگیر است. برای مثال دستگاه اول و چهارم سقفگیر هستند و دستگاه دوم و سوم کفگیر هستند.

حال رشید یک عدد طبیعی به عنوان ورودی به دستگاه اول می دهد٬ سپس خروجی این دستگاه وارد دستگاه دوم میشود٬ خروجی دستگاه دوم وارد دستگاه سوم میشود و به همین ترتیب تا دستگاه ۱۳۹۱ام که خروجی نهایی را تولید میکند. به ازای چند عدد به عنوان ورودی دستگاه اول٬ خروجی نهایی برابر با یک میشود؟

  1. ۱۳۹۰
  2. ۱۹۳۳۴۹۰
  3. $۲^ {۱۳۹۱}$
  4. $۲^ {۱۳۹۰}$
  5. ۱۳۹۱

پاسخ

گزینه‌ی ۳ درست است.

مستقل از اینکه دستگاه‌ها کف‌گیر باشند یا سقف‌گیر، همیشه تعداد اعداد $2^{1391}$ خواهد بود.

در واقع تعداد اعدادی که پس از $i$ مرحله به ۱ ختم می‌شوند، $2^i$تا است.

اگر پس از یک سقفگیر به عدد $x$ برسیم، عدد قبلی $2x-1$ یا $2x$ بوده است.

اگر پس از یک کفگیر به عدد $x$ برسیم، عدد قبلی $2x+1$ یا $2x$ بوده است.

نکته‌ی دیگر این است که در هر مرحله مجموعه‌ی جواب‌ها یک بازه است که در مرحله‌ی بعد این بازه دو برابر می‌شود (با استقرا ثابت کنید).

در نتیجه پس از ۱۳۹۱ مرحله $2^{1391}$ عدد مختلف خواهیم داشت.


ابزار صفحه