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