====== سوال ۲۶ ======




کیوان و پیمان به نوبت با هم بازی می‌کنند. آن‌ها در ابتدا یک کیسه شامل $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$
سنگ‌ریزه از ابتدا آغاز شده است که پیمان طبق فرض استقرا استراتژی برد دارد.

</پاسخ>

  * [[سوال ۲۵|سوال قبل]]
  * [[سوال ۲۷|سوال بعد]]