سوال ۲۸
یک نوار به طول $n$ به صورت روبه‌رو و یک مهره موجود است.
دو نفر این بازی را روی نوار انجام می‌دهند: در ابتدا٬ مهره در سمت چپ‌ترین خانه‌ی نوار قرار دارد. هر بازی‌کن در نوبت خود باید یکی از دو حرکت زیر را انجام دهد:
(الف) به شرط این که تا آخر نوار (سمت راست‌ترین خانه) حداقل $i$ خانه‌ی خالی وجود داشته باشد٬ مهره را به $i$ خانه جلوتر انتقال دهد. البته $i$ حتماً باید یکی از اعداد ٬۱ ۲ یا ۵ باشد.
(ب) مهره را دست نزند و نوبت را به نفر بعدی واگذار کند.
اگر نفر قبلی در نوبت خود حرکت (ب) را انجام داده باشد٬ بازی‌کن فعلی حق ندارد حرکت (ب) را انجام دهد. به عبارت دیگر٬ هیچ‌گاه دو حرکت (ب) متوالی در بازی انجام نخواهد شد. برنده کسی است که در نوبت خود٬ مهره را به آخرین خانه‌ی نوار انتقال دهد.
برای چه تعداد از مقادیر $n$ از میان اعداد {٫۱۰ ٫۳۴ ٫۵۱ ٫۶۷ ۸۱} نفر اول برنده است؟
- ۱
- ۲
- ۳
- ۴
- ۵
پاسخ
گزینه‌ی (5) درست است.
ادعا می کنیم برای هر $n$، نفر اول برندهی بازی است.
۶ خانه‌ی پایانی(سمت راست) نوار را(در صورت وجود) در نظر می‌گیریم. درصورتی‌که مهره در هرکدام از خانه‌های سیاه قرار گرفت، نفر اول حرکت می کند و مهره را به خانه‌ی $n$ام می‌برد. در غیر این‌صورت نوبت را به نفر دوم واگذار می‌کند. چون نمی‌توانیم دوبار عمل واگذاری داشته باشیم نفر دوم مجبور به حرکت است و بالاخره مهره را در یکی از خانه‌های سیاه قرار می‌دهد و نفر اول برنده می‌شود.
