المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۵:سوال ۱۰

سؤال ۱۰

دو نفر این بازی را انجام می‌دهند: هر نفر در نوبت خود، یک رقم از مجموعه‌ی {۵، ۴، ۳، ۲، ۱} را بر روی کاغذ می‌نویسد و بازی پس از نوشتن رقم $n$ام خاتمه می یاید. نفر دوم قصد دارد کاری کند که در انتها مجموع ارقام نوشته‌شده بر ۹ بخش‌پذیر باشد. ولی نفر اول می‌خواهد از این کار جلوگیری کند. به ازای چه مقدار $n$ نفر دوم می‌تواند حتماً به هدف خود برسد؟

  1. ۱۳۸۲
  2. ۱۳۸۳
  3. ۱۳۸۴
  4. ۱۳۸۶
  5. ۱۳۸۸

پاسخ

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

  • برای آن‌که نفر دوم در مرحله‌ی $n$ام برنده شود باید در مرحله $n-1$ نفر اول به یکی از باقی‌مانده‌های ۷٬۶٬۵٬۴ و ۸ رسیده باشد٬ زیرا اگر در آن مرحله٬ نفر اول به یکی از باقی‌مانده‌های ۲٬۱٬۰ و یا ۳ رسیده باشد٬ نفر دوم مکملی برای آن باقی‌مانده(از بین اعداد مجموعه داده شده) نخواهد یافت.
  • برای آن‌که در مرحله‌ی $n-1$ نفر به ناچار به یکی از باقی‌مانده‌های ۷٬۶٬۵٬۴ و یا ۸ برسد باید نفر دوم در مرحله‌ی $n-2$ به باقی‌مانده ۳ برسد.
  • برای آن‌که در مرحله $n-2$ نفر دوم بتواند به باقی‌مانده‌ ۳ برسد باید نفر اول در مرحله $n-3$ به یکی از باقی‌مانده‌های ۸٬۰٬۱٬۲ و یا ۷ رسیده باشد که او بتواند ۴٬۳٬۲٬۱ و یا ۵ اضافه کرده و باقی‌مانده عدد حاصل بر ۹ را برابر ۳ کند.
  • برای ‌آن‌که در مرحله $n-3$ نفر اول به ناچار به یکی از باقی‌مانده‌های ۸٬۰٬۱٬۲ و یا ۷ برسد باید نفر دوم در مرحله‌ی $n-4$ به باقی‌مانده‌ ۶ برسد.
  • برای آن‌که در مرحله $n-4$ نفر دوم بتواند به باقی‌مانده ۶ برسد لازم است نفر اول در مرحله $n-5$ به یکی از باقی‌مانده‌های ۴٬۳٬۲٬۱ و یا ۵ رسیده باشد.
  • برای آن‌که در مرحله‌ی $n-5$ نفر اول به یکی از باقی‌مانده‌های ۴٬۳٬۲٬۱ و یا ۵ برسد لازم است نفر دوم در مرحله‌ی $n-6$ به باقی‌مانده صفر برسد.

باتوجه به توضیحات فوق معلوم می‌شود که شرط لازم و کافی برای آن‌که نفر دوم بتواند در مرحله $n$ام برنده شود٬ آن است که بتواند در مرحله $n-6$ام برنده شود. و چون عدد صفر مضرب ۹ است؛ یعنی در مرحله‌ی صفرام نفر دوم برنده است او می‌تواند در مراحل ۱۸٬۱۲٬۶،…،۱۳۸۶٬۱۳۸۰،… برنده شود.


ابزار صفحه