المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۹

روز دیگر محمد به بازی «اسنیپ» پرداخت. این بازی شبیه دامبلدور است. در این بازی ۱۰ سنگ ۱ تا ۱۰ به صورت دایره‌ای شکل قرار گرفته‌اند. محمد روی سنگ ۱ قرار دارد. او در حرکت $i$ام باز هم روی $i-۱$ سنگ به صورت یک-پا و سپس روی سنگ بعدی جفت-پا می‌پرد. اما فرق مهم این دو بازی در این است که در این بازی هرگاه محمد به صورت جفت-پا روی سنگ ۱ بپرد، جهت پریدنش را عوض می‌کند. مثلاً تصور کنید پس از حرکت سوم او روی سنگ ۷ قرار دارد. او در حرکت چهارم به صورت یک-پا به ترتیب روی سنگ های ۸، ۹ و ۱۰ خواهد پرید و سپس به صورت جفت-پا روی سنگ ۱ می‌پرد. حال جهت حرکتش عوض می‌شود و در حرکت پنجم، به صورت یک-پا از روی سنگ های ۱۰، ۹، ۸، و ۷ خواهد گذشت و به صورت جفت-پا روی سنگ ۶ می‌پرد. مشخص کنید پس از حرکت ۲۰۰۳ام او روی کدام سنگ خواهد بود؟

  1. ۱ یا ۲
  2. ۳ یا ۴
  3. ۵ یا ۶
  4. ۷ یا ۸
  5. ۹ یا ۱۰

پاسخ

گزینه (۴) درست است.

چند حرکت ابتدایی مشخص است. شماره سنگ‌هایی که پست از حرکات اول٬ دوم٬ سوم و چهارم بر روی آن‌ها به صورت جفت‌پا پریده می‌شود به ترتیب ۷٬۴٬۲ و ۱۱ (همان ۱) می‌باشد که از سنگ ۱ به ترتیب ۱ واحد٬ $(2+1)$ واحد٬ $(3+2+1)$ واحد و بالاخره $(4+3+2+1)$ واحد فاصله دارند. دراین لحظه جهت عوض می‌شود و بعد از حرکت $n$ام دوباره به صورت جفت پا به روی شماره ۱ پریده خواهد شد که درآن $n$ اولین عدد است که $5+6+7+...+n$ مضرب ۱۰ باشد و این نیز موقعی برقرار است که $1+2+3+...+n$ یا $\frac{n(n+1)}{2}$ مضرب ۱۰ و یا $n(n+1)$ مضرب ۲۰ باشد که اولین $n$ بعد از ۴ برای برآورده کردن آن شرط٬ $n=15$ می‌باشد. و بعد از ۱۵ نیز اعداد ۱۹ و ۲۰ آن شرط را برآورده می‌کنند. از حرکت بیستم تا حرکت سی‌ونهم کاملا شبیه حرکت صفرم تا نوزدهم می‌باشد؛ یعنی سلسله حرکات دوره تناوبی به طول ۲۰ دارد٬ لذا حرکت ۲۰۰۳ در مکانی قرار داریم که در انتهای حرکت سوم داشته‌ایم٬ بنابراین بعد از آن حرکت بر روی سنگ هفتم به صورت جفت پا پریده خواهد شد.


ابزار صفحه