משחק

[CodeGuru]

שני אנשים משחקים את המשחק הבא: ערימה של אסימונים מונחת על השולחן. בכל תור אחד השחקנים מוריד מספר טבעי כלשהו של אסימונים מהערימה. מי שלא יכול לשחק – מפסיד.

קל מאוד לנצח בחוקים הללו: הראשון לוקח הכל. לכן נוסיף תנאי שלראשון אסור לקחת הכל.

עדיין קל מאוד לנצח (גם עם החוק החדש): השני לוקח הכל. לכן נוסיף תנאי נוסף שלכל שחקן אסור לקחת יותר מכפליים ממה שלקח קודמו.

עכשיו זה כבר לא טריוויאלי.

השאלה: עבור אילו גדלי ערימות ינצח השחקן השני?

[Gil]

מתחלקים ב3?

[CodeGuru]

לא – עבור ערימות בגודל 1,2,3 מנצח השני; עבור 4 יכול הראשון לנצח; …

[Gil]

בפיבונאצ'ים גדולים או שווים ל2 השני מנצח, בשאר הראשון
אגב, המשחק לא מוגדר עבור מספר אסימונים שווה 1.

[CodeGuru]

0. תשובה נכונה, כל הכבוד.

1. השני מנצח גם במקרה של אסימון יחיד – הוא חייב לקחת ואסור לו לקחת הכל ולכן הוא לא יכול לשחק ומכאן שהוא מפסיד  ולכן השני מנצח (בכל מספרי פיבונאצ'י – אם תרצו גם בגודל ערימה של אפס אסימונים).

2. איך מוכיחים את התשובה?

[מאת]

תגובות