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