سوال 8
2004 خانه‌ی خالی با شماره‌های 1 تا 2004 به‌ترتیب و در جهت ساعت‌گرد دور دایره‌ای قرار دارند. در خانه‌ی شماره‌ی1 ٬ یک مهره قرار می‌دهیم.امین و شایان شروع به بازی می‌کنند. در ابتدا امین مهره را یک خانه به جلو می‌برد و در خانه‌ی شماره 2 قرار می‌دهد. از این به بعد٬هر نفر در نوبت خود مهره را در جهت ساعت‌گرد تعدادی خانه به جلو می‌برد٬ به این ترتیب که اگر یک نفر در نوبت خود مهره را $i$ خانه به جلو حرکت دهد٬ نفر بعد باید مهره را $i$ یا $i+1$ خانه به جلو حرکت دهد. اگر کسی مهره را وارد خانه‌ی 1382ام کند بازی را می‌برد. دقت کنید که ممکن است مهره از روی خانه‌ی 1382 بپرد(در این صورت بازی ادامه می‌يابد).کدام گزینه صحیح است؟
- شایان می‌تواند طوری بازی کند که بپرد.
- امین می‌تواند طوری بازی کند که بپرد.
- امین می‌تواند طوری بازی کند که نبازد.
- شایان می‌تواند طوری بازی کند که نبازد.
- گزینه‌های 3 و 4 صحیح‌اند.
پاسخ
گزینه (؟) درست است.
فرض کنید بازیکنی در نوبت خود قادر باشد به تعداد $k$ و یا $k+1$ خانه حرکت کند. اگر با حرکت $k$ خانه او٬ بازیکن دیگر بتواند برنده شود(معلوم است که در این حالت بازیکن دوم مهره را $k$ و یا $k+1$ خانه جابه‌جا کرده است)٬ آن‌گاه آن بازیکن به جای $k$ خانه٬ $k+1$ خانه مهره راجا‌به‌جا می‌کند و نمی‌گذارد بازیکن دوم برنده شود زیرا در این حالت بازیکن دوم مهره را $k+1$ خانه و یا $k+2$ خانه جابه‌جا می‌کند که در هر حال از خانه مورد نظر می‌گذرد و در آن خانه متوقف نمی‌شود. و در حالتی که با حرکت $k+1$ خانه توسط بازیکن اول٬ بازیکن دوم بتواند برنده شود بازکن اول حرکت خود را به جای $k+1$ حرکت به $k$ حرکت تغییر می‌دهد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
