سوال ۲۶
کیوان و پیمان به نوبت با هم بازی می‌کنند. آن‌ها در ابتدا یک کیسه شامل $n$ سنگ‌ریزه دارند. بازی را کیوان شروع می‌کند. کیوان در هر نوبت‌ش می‌تواند ۰، ۱ یا ۲ سنگ‌ریزه از کیسه خارج کند، در حالی که پیمان در هر نوبت‌ش می‌تواند ۱، ۲ یا ۳ سنگ‌ریزه بردارد. برنده‌ی بازی کسی است که آخرین سنگ‌ریزه را از کیسه خارج کند. اگر هر دو نفر به صورت بهینه بازی کنند، به ازای $n=10$، $n=1395$ و $n=2016$ به ترتیب چه کسی بازی را می‌برد؟
- کیوان، پیمان، کیوان
- پیمان، کیوان، پیمان
- پیمان، پیمان، پیمان
- کیوان، کیوان، کیوان
- پیمان، پیمان، کیوان
راهنمایی
بازی را برای $n=3$ اجرا کنید.
راهنمایی
در راستای راهنمایی پیشین، سعی کنید نتیجه را به تمام اعداد مضرب ۳ گسترش دهید.
راهنمایی
برای $n=10$ سعی کنید $n$ را به عنوان نفر دوم، به مضرب ۳ کاهش دهید.
پاسخ
گزینه‌ی ۳ درست است.
به استقرا روی $n$ ثابت می‌کنیم به ازای هر $n \ge 3$ پیمان بازی را می‌برد. برای پایه‌ی استقرا به ازای $n=3, 4, 5$ پیمان بازی را می‌برد (بررسی حالات به خواننده واگذار می‌شود). حال به ازای هر $n \ge 6$ اگر کیوان $k$ سنگ‌ریزه برداشت، پیمان $3-k$ سنگ‌ریزه برمی‌دارد. گویی بازی به ازای $n-3$ سنگ‌ریزه از ابتدا آغاز شده است که پیمان طبق فرض استقرا استراتژی برد دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
