אסטרטגיית נצחון

[עריסטו]

אסטרטגיית נצחון

יש פס מחולק למשבצות. על חלק מהמשבצות יש מטבעות (מטבע אחד על כל משבצת).

משחקים שני אנשים. כל אחד בתורו לוקח מטבע ומזיז אותו מספר כלשהו של משבצות שמאלה. אסור שיהיו שני מטבעות באותה משבצת ואסור למטבע לדלג מעל מטבע אחר. המשחק מסתיים כאשר המטבעות נמצאים במשבצות השמאליות ואי אפשר להמשיך. מי שעשה את הצעד האחרון הוא המנצח. מה אסטרטגיית הנצחון?

 

[noale noale]

תשובה?

האסטרטגיה: לבחור להיות השני - כלומר לא זה שמתחיל את המשחק: ולמה? כי השני - לא יכול לדלג מעל הראשון. הראשון בסופו של דבר יאלץ להגיע למשבצת השמאלית ביותר. ואז השני יעביר את המטבע שלו צמוד אל המטבע של הראשון - והוא ניצח !

 

[עריסטו]

../images/Emo128.gif נראה לי שלא הבנת את החידה

מה זה "המטבע שלו" ו"המטבע של הראשון"? איפה כתוב שיש רק שני מטבעות, ושכל שחקן יכול להזיז רק אחד מהם?

 

[noale noale]

אופס .... צודק

ולמרות שהסתכלתי על הציור ובו יש לבטח יותר משני מטבעות - לא הפנמתי.. זה מה שקורה כשמנסים מהר מהר לגנוב שתי דקות באמצע העבודה

 

[1אברהם]

ניסיון

נמספר את המשבצות בסדר עולה משמאל לימין כשהמשבצת השמאלית ביותר היא 0 ומימינה 1 2 3 ..... המטבעות נמצאות על משבצות ..... a1 a2 a3 a4 (כאשר a1 מיקומה של המטבע השמאלית ביותר ). נגדיר את ההפרשים .... b1 b2 b3 בצורה הבאה: אם יש מספר זוגי של מטבעות אז: b1=a2-a1 b2=a4-a3 b3=a6-a5 .... אם יש מספר אי זוגי של מטבעות אז: b1=a1 b2=a3-a2 b3=a5-a4 .... כלומר חילקנו את המטבעות לזוגות עוקבים ומצאנו את המרחק בין כל זוג עוקב אסטרטגית הניצחון היא לעשות כל פעם מהלך שמאפס את ה XOR של כל ההפרשים ....b1 b2 b3

 

[עריסטו]

../images/Emo127.gif ובצורה פשוטה יותר...

במקום לחלק לשני מקרים - מספר את המטבעות מימין לשמאל

 

[עריסטו]

הסבר למעוניינים (יש כאלה?) ../images/Emo26.gif

זה בעצם Nim, כאשר הערימות הן הרווחים בין המטבע הימני למטבע השני מימין, בין המטבע השלישי לרביעי וכן הלאה. ההבדל היחיד הוא שכאן ניתן לפעמים "להגדיל את הערימות", אבל זה לא משנה את האסטרטגיה.

 

[1אברהם]

הערה

אם מספר המטבעות הוא אי זוגי, אז יוצא שלמטבע השמאלי ביותר אין בן זוג משמאלו שאליו יש למדוד את הרווח ולא ברור מהניסוח שלך איך לחשב את גודל "הערימה" האחרונה. במקרה זה "הערימה" האחרונה היא מרחקו של השמאלי ביותר מתחילת הלוח. זה הסיבה שראיתי צורך להפריד בין 2 המיקרים.

 

[גיאל]

מה זה NIM ?