فهرست مندرجات
سوالات ۳۲ و ۳۳
کامبیز کفش های جدیدی خریده است. این کفش ها ویژگی جالبی دارند و آن اینکه بعد از پیمودن اولین گام٬ اگر طول گام قبلی‌ای که با این کفش برداشته شده است $x$ باشد در گام بعدی او فقط می تواند گامی یا به طول $۲x$ یا به طول $\frac x۲$ بردارد. به دلیل وزن زیاد کامبیز٬ کامبیز نمی تواند گامی با طول کوچکتر از یک بردارد! هم چنین او نمی تواند هرگز جهت حرکتش را تغییر بدهد و همواره مستقیم پیش می رود.
در ابتدای کار کامبیز در خانه‌ي صفرم یک ۱-در-بی نهایت قرار دارد. در اولین مرحله٬ کامبیز با برداشتن یک گام به طول یک از خانه‌ي صفرم به خانه‌ي یکم می رود. هدف کامبیز این است که با پیمودن تعدادی گام به یک نقطه‌ي مشخص شده برسد. مثلا یک دنباله حرکات قابل قبول برای رسیدن به خانه‌ي سیزده می تواند به این صورت باشد: $$0 \to 1 \to 3 \to 7 \to 9 \to 10 \to 12 \to 13$$
یک خانه را «خوب» می گوییم اگر کامبیز بتواند با اتخاذ یک سیاست گام برداشتن به آن خانه برسد. به طور مشابه٬ یک خانه را «بد» می گوییم اگر کامبیز هرگز نتواند با هر ترتیبی به آن برسد. برای مثال ۱۳ یک خانه‌ي خوب و ۲ یک خانه‌ی بد است.
با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید:
سوال ۳۲
کدام گزینه صحیح است؟
- ۱۳۹۰ یک خانه‌ی خوب و ۲۰۱۲ یک خانه‌ی بد است.
- ۲۰۰۰ یک خانه‌ی خوب و ۱۴۰۰ یک خانه‌ی بد است.
- ۱۴۰۰ یک خانه‌ی خوب و ۲۰۰۰ یک خانه‌ی بد است.
- ۱۳۹۱ یک خانه‌ی خوب و ۲۰۱۳ یک خانه‌ی بد است.
- ۲۰۱۲ یک خانه‌ی خوب و ۱۳۹۰ یک خانه‌ی بد است.
پاسخ
گزینه‌ی «۱» درست است.
بهتر است در این سوال به‌جای تلاش برای ساختن یکی از گزینه‌ها برای حالت کلی مسئله تلاش کنیم.
برای حل این سوال بیایید حالت‌های کوچک را بررسی کنیم مثلا کدام اعداد را می‌شود ساخت؟
$1, 3, 4, 6, 7, 9, 10, …$
شاید بگویید ما تنها از پرش‌های 1و 2 استفاده می‌کنیم و همان طور که می‌بینید به خانه‌های 3$k+2$ نمی‌توان رفت و با این حرکات هم فقط به آن خانه‌ها نمی‌توان رفت. پس به نظر مسئله حل شده اما گفته ما اثباتی برای این مسئله نیست پس بیایید حدس خود را اثبات کنیم. فرض کنید ثابت کرده‌ایم برای اعداد 1 تا n حکم را ثابت کرده ایم. حال می‌گوییم برای رسیدن به عدد $n+1$ یا با پرشی به طول $3k+1$ آمده‌ایم یا $3k+2$. به نظر با این فرض نمی‌توان چیزی را اثبات کرد! بیایید فرض را قوی تر کنیم و بگوییم برای رسیدن به خانه های $3k$ باید آخرین پرشی که انجام داده‌ایم طولش $3p+2$ بوده و برای $3k+1$ ها هم طول آخرین پرشمان $3p+1$ بوده. حکم برای حرکت اول که برقرار است. برای سایر حرکات هم برقرار می‌شود چرا که می‌گوییم برای رسیدن به خانه ی $3x+2$ از هیچ خانه‌ی دیگری نمی‌توانیم استفاده کنیم! همچنین برای $3x+1$ ها و $3x$ ها باید از $3p$ و $3p+1$ آمده باشیم! پس حکم قوی‌تر را اثبات کردیم!
حال با توجه به این قضیه به راحتی می‌توان بگوییم که گزینه‌ای که یک عدد 3$k+2$ را بد و یک عدد دیگر را خوب گفته درست است(۱۳۹۰ خوب و ۲۰۱۲ بد).
سوال ۳۳
فرض کنید تمام خانه های خوبی که با حداکثر ۱۰۰ حرکت می توان به آن رسید را با شروع از یک٬ در دنباله‌ای مرتب پشت سر هم نوشته ایم. این دنباله به شکل $\langle 1,3,4,6,...\rangle$ است. ۲۰۱۲ اٌمین عدد این دنباله کدام است؟
- ۲۰۱۳
- ۴۰۲۴
- ۳۰۱۸
- ۲۰۱۲
- ۳۰۱۹
پاسخ
گزینه‌ی «۳» درست است.
با توجه به قضیه بالا و اینکه می‌توانیم هرکدام از اعداد را با شروع از بزرگ‌ترین توان دو آن‌ها و ساختن سایر ارقام آن‌ها در مبنای دو در حرکات بسیار کمی بسازیم پس کافیست با کنار گذاشتن اعداد 3$k+2$، ۲۰۱۲ امین عدد را که همان $\frac{3\times2012}{2} = 3018$ است را از گزینه‌ها انتخاب کنیم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
