צריך עזרה
- פותח הנושא בוזו
- פורסם בתאריך
לא לשחק באש
הפתרון נעוץ בעובדה שתמיד יכול שחקן להשלים ל-4 את מספר הגפרורים שהוציא השחקן השני בתורו האחרון. מטרת המשחק היא להשאיר גפרור אחד ליריב, כלומר להיפטר מ-20 גפרורים. מספר זה מתחלק ב-4, ולכן במשחק זה קיימת אסטרטגיה מנצחת לשחקן השני - כל שעליו לעשות בתורו הוא להשלים ל-4 את מספר הגפרורים שהוציא השחקן הראשון. לאחר חמישה סיבובים יוותר גפרור אחד, אותו יהיה חייב השחקן הראשון לקחת. והנה משחק דומה, אך יותר קשה לפיצוח: ישנן חמש ערימות של דגים - דג אחד, שני דגים, שלושה דגים, ארבעה דגים וחמישה דגים. על כל שחקן בתורו להוציא מספר כלשהו של דגים (לפחות אחד) מערימה מסוימת (אחת בלבד). השחקן שמוציא את הדג האחרון מנצח. לאיזה מהשחקנים קיימת אסטרטגיה מנצחת, ומהי?
הפתרון נעוץ בעובדה שתמיד יכול שחקן להשלים ל-4 את מספר הגפרורים שהוציא השחקן השני בתורו האחרון. מטרת המשחק היא להשאיר גפרור אחד ליריב, כלומר להיפטר מ-20 גפרורים. מספר זה מתחלק ב-4, ולכן במשחק זה קיימת אסטרטגיה מנצחת לשחקן השני - כל שעליו לעשות בתורו הוא להשלים ל-4 את מספר הגפרורים שהוציא השחקן הראשון. לאחר חמישה סיבובים יוותר גפרור אחד, אותו יהיה חייב השחקן הראשון לקחת. והנה משחק דומה, אך יותר קשה לפיצוח: ישנן חמש ערימות של דגים - דג אחד, שני דגים, שלושה דגים, ארבעה דגים וחמישה דגים. על כל שחקן בתורו להוציא מספר כלשהו של דגים (לפחות אחד) מערימה מסוימת (אחת בלבד). השחקן שמוציא את הדג האחרון מנצח. לאיזה מהשחקנים קיימת אסטרטגיה מנצחת, ומהי?
גירסה של נים, הא?
ובכן, אני הכרתי גירסה דומה, עם מספר כלשהו של דגים בשלוש ערמות... ואז קראו לזה נים. לדעתי גם למשחק הזה פתרון דומה לפתרון של נים. נבצע XOR בין הייצוגים הבינאריים של המספרים שב5 הערמות לדוגמא, במצב ההתחלתי, זה יהיה XOR בין 1, 10, 11, 100, 101, והתוצאה היא 1. השחקן הראשון (בעל האסטרטגיה המנצחת) ינסה להביא את הXOR ל0 (כי זה המצב הסופי שאליו הוא שואף להגיע). כלומר, מהלך ראשון מנצח יהיה לקחת דג אחד מהערמה הראשונה. השחקן השני, לא משנה מה יעשה, ישנה את הXOR למשהו שונה מאפס, ואז השחקן הראשון יוכל שוב ע"י בחירת מהלך בקפידה, להחזירו לאפס, ובסופו של דבר לנצח. אני מקווה שזה נכון. לא בדקתי את זה... אם לא, נחשוב על משהו אחר
ובכן, אני הכרתי גירסה דומה, עם מספר כלשהו של דגים בשלוש ערמות... ואז קראו לזה נים. לדעתי גם למשחק הזה פתרון דומה לפתרון של נים. נבצע XOR בין הייצוגים הבינאריים של המספרים שב5 הערמות לדוגמא, במצב ההתחלתי, זה יהיה XOR בין 1, 10, 11, 100, 101, והתוצאה היא 1. השחקן הראשון (בעל האסטרטגיה המנצחת) ינסה להביא את הXOR ל0 (כי זה המצב הסופי שאליו הוא שואף להגיע). כלומר, מהלך ראשון מנצח יהיה לקחת דג אחד מהערמה הראשונה. השחקן השני, לא משנה מה יעשה, ישנה את הXOR למשהו שונה מאפס, ואז השחקן הראשון יוכל שוב ע"י בחירת מהלך בקפידה, להחזירו לאפס, ובסופו של דבר לנצח. אני מקווה שזה נכון. לא בדקתי את זה... אם לא, נחשוב על משהו אחר
i´ll give it a shot
1. אנחנו במצב זוגי. כל שינוי בערמה אחת גורר שינוי אחד לפחות באחת מהעמודות הבינאריות שלה. זה, אני מקווה, ברור מאליו, כי אם אין שינוי באף אחד מהעמודות הבינאריות שלה, המספר נשאר זהה. כעת באותה עמודה, מכיוון שאף אחת מהערמות האחרות לא השתנתנה, הXOR השתנה, וסיימנו. 2. נתבונן בXOR ונראה באילו עמודות הוא 1. נסתכל ספציפית על העמודה הכי שמאלית שבה הXOR הוא 1. נבחר ערימה שבה העמודה הזאת (שמקבילה לעמודת ה1הכי שמאלית בXOR), היא 1. חייבת להיות כזאת כי אחרת העמודה הזאת בXOR הייתה 0. כעת נוריד מהערימה הזאת מספר כלשהו של דגים שיסדר את כל הXOR. למה זה אפשרי? את זה אפשר להראות באינדוקציה על הביטים אם הXOR הוא חד-ספרתי (כלומר 1 בדיוק), אז הורדת דג אחד מהערמה שהביט הימני שלה דלוק יעבוד. אם זה נכון עבור כל הXORים שמספר הביטים שלהם קטן מאן, נראה שזה נכון עבור XOR אן-ספרתי. נפחית מערמה דגים עד שנגיע לערמה מהצורה 111..., כלומר חזקה של 2 פחות 1. לדוגמא אם הייתה לנו הערמה 101, והXOR הוא תלת-ספרתי, נוריד 2 דגים כדי לקבל 11. כעת מה קרה לXOR? לא ידוע מה קרה לשאר הספרות שלו, אבל ידוע שהספרה השמאלית ביותר שלו התנדפה לה, ונשארנו עם הנחת האינדוקציה. מקווה שצדקתי. המצאתי את זה בזמן הכתיבה
1. אנחנו במצב זוגי. כל שינוי בערמה אחת גורר שינוי אחד לפחות באחת מהעמודות הבינאריות שלה. זה, אני מקווה, ברור מאליו, כי אם אין שינוי באף אחד מהעמודות הבינאריות שלה, המספר נשאר זהה. כעת באותה עמודה, מכיוון שאף אחת מהערמות האחרות לא השתנתנה, הXOR השתנה, וסיימנו. 2. נתבונן בXOR ונראה באילו עמודות הוא 1. נסתכל ספציפית על העמודה הכי שמאלית שבה הXOR הוא 1. נבחר ערימה שבה העמודה הזאת (שמקבילה לעמודת ה1הכי שמאלית בXOR), היא 1. חייבת להיות כזאת כי אחרת העמודה הזאת בXOR הייתה 0. כעת נוריד מהערימה הזאת מספר כלשהו של דגים שיסדר את כל הXOR. למה זה אפשרי? את זה אפשר להראות באינדוקציה על הביטים
אם הXOR הוא חד-ספרתי (כלומר 1 בדיוק), אז הורדת דג אחד מהערמה שהביט הימני שלה דלוק יעבוד. אם זה נכון עבור כל הXORים שמספר הביטים שלהם קטן מאן, נראה שזה נכון עבור XOR אן-ספרתי. נפחית מערמה דגים עד שנגיע לערמה מהצורה 111..., כלומר חזקה של 2 פחות 1. לדוגמא אם הייתה לנו הערמה 101, והXOR הוא תלת-ספרתי, נוריד 2 דגים כדי לקבל 11. כעת מה קרה לXOR? לא ידוע מה קרה לשאר הספרות שלו, אבל ידוע שהספרה השמאלית ביותר שלו התנדפה לה, ונשארנו עם הנחת האינדוקציה. מקווה שצדקתי. המצאתי את זה בזמן הכתיבה נכון../images/Emo70.gif
האינדוקציה קצת מיותרת - ברגע שהבאת את הערימה הנבחרת לצורה 11..1, כל שצריך לעשות הוא להמשיך ולקחת את ה"1"ים מהעמודות שה-xor שלהם אי זוגי. (ברור לפי התהליך שהצגת שאין עמודה כזאת משמאל לעמודות אלה). ועוד נשאר לך להראות שמטענות 1 ו-2 נובע מה שברצוננו להוכיח.
האינדוקציה קצת מיותרת - ברגע שהבאת את הערימה הנבחרת לצורה 11..1, כל שצריך לעשות הוא להמשיך ולקחת את ה"1"ים מהעמודות שה-xor שלהם אי זוגי. (ברור לפי התהליך שהצגת שאין עמודה כזאת משמאל לעמודות אלה). ועוד נשאר לך להראות שמטענות 1 ו-2 נובע מה שברצוננו להוכיח.
חשבתי שעל זה ויתרת לי
מה שאנחנו רוצים להוכיח זה שהשחקן הראשון מנצח תמיד, נכון? לפני שאני עושה את זה, אני רוצה להציג צורה אינדוקטיבית לחשוב על משחקים. עשיתי פעם תוכנה ממש חמודה בסי פלוס פלוס שמשחקת משחק, שהוא משחק אחר, שתכף אציג אותו כאן, אבל בעזרת הריקורסיה הכי פשוטה, וזה פשוט יפה. בכל אופן, החשיבה האינדוקטיבית כאן מגדירה מצב מפסיד ומצב מנצח. מצב מנצח זה מצב שבו יש דג אחד במשחק, או מצב שבו קיים מהלך שמביא למצב מפסיד. מצב מפסיד זה מצב שבו אין דגים במשחק או מצב שבו לכל מהלך שתבצע, תגיע למצב מנצח. קצת קשה לחשוב על זה, אבל אם תחשבו תראו שזה עובד. עכשיו, ברור לנו שכל מצב מנצח הוא מצב אי-זוגי ולהפך. כי מצב שבו יש דג אחד במשחק הוא מצב אי-זוגי. ובהינתן מצב אי-זוגי, הראנו שקיים מהלך שמביא אותנו למצב זוגי. כלומר, באופן פורמלי, אם אני השחקן הראשון, ובמהלך הראשון שלי אני אביא את המשחק למצב זוגי (שהוא מפסיד, עבור השחקן השני שמקבל אותו עכשיו), וכל מהלך שהוא יעשה יביא אותו למצב אי-זוגי, שהוא בהכרח לא המצב הסופי של המשחק (כי הוא זוגי), ואז אני אוכל תמיד להחזיר את המשחק למצב זוגי, וכו´ וכו´, ברור לגמרי (בגלל שלכל משחק יש מספר סופי של צעדים) שאני אעשה את המהלך האחרון ואנצח. המשחק שדיברתי עליו, שהראו לנו אותו בתורת המשחקים, הולך ככה... יש לנו לוח מלבני, נניח n שורות וm עמודות. כל שחקן בתורו מוחק משבצת מהלוח, וברגע שהוא מוחק אותה, נמחקות גם כל המשבצות שנמצאות בשורה גדולה-או-שווה (למעלה זה גדול יותר) למשבצת שלנו ובטור גדול-או-שווה (ימינה זה גדול יותר) למשבצת שלנו... בעצם נמחק מלבן שלם שהפינה השמאלית-תחתונה שלו היא המשבצת שמחקנו, והפינה הימנית-עליונה שלו היא המשבצת הימנית עליונה של הלוח כולו. השחקן שמוחק את המשבצת האחרונה (הלא היא המשבצת השמאלית תחתונה בלוח, בהכרח) מפסיד. שימו לב שעבור לוח ריבועי קיים פתרון מיידי. מהו?
מה שאנחנו רוצים להוכיח זה שהשחקן הראשון מנצח תמיד, נכון? לפני שאני עושה את זה, אני רוצה להציג צורה אינדוקטיבית לחשוב על משחקים. עשיתי פעם תוכנה ממש חמודה בסי פלוס פלוס שמשחקת משחק, שהוא משחק אחר, שתכף אציג אותו כאן, אבל בעזרת הריקורסיה הכי פשוטה, וזה פשוט יפה. בכל אופן, החשיבה האינדוקטיבית כאן מגדירה מצב מפסיד ומצב מנצח. מצב מנצח זה מצב שבו יש דג אחד במשחק, או מצב שבו קיים מהלך שמביא למצב מפסיד. מצב מפסיד זה מצב שבו אין דגים במשחק או מצב שבו לכל מהלך שתבצע, תגיע למצב מנצח. קצת קשה לחשוב על זה, אבל אם תחשבו תראו שזה עובד. עכשיו, ברור לנו שכל מצב מנצח הוא מצב אי-זוגי ולהפך. כי מצב שבו יש דג אחד במשחק הוא מצב אי-זוגי. ובהינתן מצב אי-זוגי, הראנו שקיים מהלך שמביא אותנו למצב זוגי. כלומר, באופן פורמלי, אם אני השחקן הראשון, ובמהלך הראשון שלי אני אביא את המשחק למצב זוגי (שהוא מפסיד, עבור השחקן השני שמקבל אותו עכשיו), וכל מהלך שהוא יעשה יביא אותו למצב אי-זוגי, שהוא בהכרח לא המצב הסופי של המשחק (כי הוא זוגי), ואז אני אוכל תמיד להחזיר את המשחק למצב זוגי, וכו´ וכו´, ברור לגמרי (בגלל שלכל משחק יש מספר סופי של צעדים) שאני אעשה את המהלך האחרון ואנצח. המשחק שדיברתי עליו, שהראו לנו אותו בתורת המשחקים, הולך ככה... יש לנו לוח מלבני, נניח n שורות וm עמודות. כל שחקן בתורו מוחק משבצת מהלוח, וברגע שהוא מוחק אותה, נמחקות גם כל המשבצות שנמצאות בשורה גדולה-או-שווה (למעלה זה גדול יותר) למשבצת שלנו ובטור גדול-או-שווה (ימינה זה גדול יותר) למשבצת שלנו... בעצם נמחק מלבן שלם שהפינה השמאלית-תחתונה שלו היא המשבצת שמחקנו, והפינה הימנית-עליונה שלו היא המשבצת הימנית עליונה של הלוח כולו. השחקן שמוחק את המשבצת האחרונה (הלא היא המשבצת השמאלית תחתונה בלוח, בהכרח) מפסיד. שימו לב שעבור לוח ריבועי קיים פתרון מיידי. מהו?
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.